Subject: [PATCH] tree_entry_interesting: inline strncmp()

From: Nguyễn Thái Ngọc Duy <[email-masked]>
Date: Mon, 4 Apr 2011 21:46:26 +0700

strncmp() is the function that takes most of the time inside
tree_entry_interesting(). Inline it so we can shave some seconds out
of function call time.

Signed-off-by: Nguyễn Thái Ngọc Duy <[email-masked]>
---
 Turns out simplicity is the best. My straight copy of strncmp from
 glibc performed worse.

 With this I get a slightly better performance than Dan's 3/5:
 81.07-82.27 secs versus 82.02-82.92 (no other patches are applied).
 But I'm happy even if it gives the same or slightly worse
 performance because this applies to more cases than flat top tree
 case.

 Dan, match_dir_prefix() can also use some reordering to avoid
 strncmp(). But I suppose it won't give much gain on packages.git

 tree-walk.c |   28 ++++++++++++++++++++++++----
 1 files changed, 24 insertions(+), 4 deletions(-)

diff --git a/tree-walk.c b/tree-walk.c
index 322becc..80bfc3a 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -457,6 +457,26 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch
 	return retval;
 }
 
+/* Static version of strncmp to reduce function call cost */
+static inline int strncmp_1(const char *s1, const char *s2, size_t n)
+{
+	unsigned char c1 = '\0';
+	unsigned char c2 = '\0';
+
+	if (!n)
+		return 0;
+
+	while (n > 0) {
+		c1 = (unsigned char) *s1++;
+		c2 = (unsigned char) *s2++;
+		if (c1 == '\0' || c1 != c2)
+			return c1 - c2;
+		n--;
+	}
+
+	return c1 - c2;
+}
+
 static int match_entry(const struct name_entry *entry, int pathlen,
 		       const char *match, int matchlen,
 		       int *never_interesting)
@@ -473,7 +493,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,
 		 * Does match sort strictly earlier than path
 		 * with their common parts?
 		 */
-		m = strncmp(match, entry->path,
+		m = strncmp_1(match, entry->path,
 			    (matchlen < pathlen) ? matchlen : pathlen);
 		if (m < 0)
 			return 0;
@@ -509,7 +529,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,
 		 * we cheated and did not do strncmp(), so we do
 		 * that here.
 		 */
-		m = strncmp(match, entry->path, pathlen);
+		m = strncmp_1(match, entry->path, pathlen);
 
 	/*
 	 * If common part matched earlier then it is a hit,
@@ -525,7 +545,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,
 static int match_dir_prefix(const char *base, int baselen,
 			    const char *match, int matchlen)
 {
-	if (strncmp(base, match, matchlen))
+	if (strncmp_1(base, match, matchlen))
 		return 0;
 
 	/*
@@ -592,7 +612,7 @@ int tree_entry_interesting(const struct name_entry *entry,
 		}
 
 		/* Does the base match? */
-		if (!strncmp(base_str, match, baselen)) {
+		if (!strncmp_1(base_str, match, baselen)) {
 			if (match_entry(entry, pathlen,
 					match + baselen, matchlen - baselen,
 					&never_interesting))
-- 
1.7.4.74.g639db