Re: [PATCH 3/5] tree-walk: micro-optimization in tree_entry_interesting

[Nguyen Thai Ngoc Duy <pclouds@gmail.com>]

On Wed, Mar 30, 2011 at 08:37:59PM -0500, Dan McGee wrote:
> In the case of a wide breadth top-level tree (~2400 entries, all trees
> in this case), we can see a noticeable cost in the profiler calling
> strncmp() here. Most of the time we are at the base level of the
> repository, so base is "" and baselen == 0, which means we will always
> test true. Break out this one tiny case so we can short circuit the
> strncmp() call.
> 
> This resulted in an ~11% improvement (43 to 38 secs) for a reasonable
> log operation on the Arch Linux Packages SVN clone repository, which
> contained 117220 commits and the aforementioned 2400 top-level objects:
>     git log -- autogen/trunk pacman/trunk/ wget/trunk/
> 
> Negligible slowdown was noted with other repositories (e.g. linux-2.6).
> 
> Signed-off-by: Dan McGee <dpmcgee@gmail.com>

Ack.

On my (slower) laptop, the same command with vanilla git -O3 takes
95 secs. Your patch cuts it down to 82 secs.

I tried inlining strncmp with a version from glibc. Without your patch
it takes 88 secs. With your patch, it takes 86 secs (still worse than
your patch alone). A better strncmp version must be used on my system,
I suspect.

--8<--
diff --git a/tree-walk.c b/tree-walk.c
index 322becc..0859b5c 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -457,6 +457,55 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch
 	return retval;
 }
 
+static inline int inline_strncmp(const char *s1, const char *s2, size_t n)
+{
+	unsigned char c1 = '\0';
+	unsigned char c2 = '\0';
+
+	if (n == 0)
+		return 0;
+
+	if (n >= 4) {
+		size_t n4 = n >> 2;
+		do {
+			c1 = (unsigned char) *s1++;
+			c2 = (unsigned char) *s2++;
+			if (c1 == '\0' || c1 != c2)
+				return c1 - c2;
+			c1 = (unsigned char) *s1++;
+			c2 = (unsigned char) *s2++;
+			if (c1 == '\0' || c1 != c2)
+				return c1 - c2;
+			c1 = (unsigned char) *s1++;
+			c2 = (unsigned char) *s2++;
+			if (c1 == '\0' || c1 != c2)
+				return c1 - c2;
+			c1 = (unsigned char) *s1++;
+			c2 = (unsigned char) *s2++;
+			if (c1 == '\0' || c1 != c2)
+				return c1 - c2;
+		} while (--n4 > 0);
+		n &= 3;
+	}
+
+	while (n > 0) {
+		c1 = (unsigned char) *s1++;
+		c2 = (unsigned char) *s2++;
+		if (c1 == '\0' || c1 != c2)
+			return c1 - c2;
+		n--;
+	}
+
+	return c1 - c2;
+}
+
+#if 1
+#ifdef strncmp
+#undef strncmp
+#endif
+#define strncmp inline_strncmp
+#endif
+
 static int match_entry(const struct name_entry *entry, int pathlen,
 		       const char *match, int matchlen,
 		       int *never_interesting)
--8<--
-- 
Duy