[PATCH 5/5] tree-walk: match_entry microoptimization

[Dan McGee <dpmcgee@gmail.com>]

Before calling strncmp(), see if we can get away with checking only the
first character of the passed path components instead.

Signed-off-by: Dan McGee <dpmcgee@gmail.com>
---
 tree-walk.c |   26 ++++++++++++++++++--------
 1 files changed, 18 insertions(+), 8 deletions(-)

diff --git a/tree-walk.c b/tree-walk.c
index 41383b0..083b951 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -488,9 +488,10 @@ static int match_entry(const struct name_entry *entry, int pathlen,
 		       const char *match, int matchlen,
 		       int *never_interesting)
 {
-	int m = -1; /* signals that we haven't called strncmp() */
+	int m = -1; /* signals that we haven't compared strings */
 
 	if (*never_interesting) {
+		const int maxlen = (matchlen < pathlen) ? matchlen : pathlen;
 		/*
 		 * We have not seen any match that sorts later
 		 * than the current path.
@@ -500,10 +501,13 @@ 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,
-			    (matchlen < pathlen) ? matchlen : pathlen);
-		if (m < 0)
-			return 0;
+		if (maxlen && match[0] > entry->path[0]) {
+			/* no good for the shortcut here, match must be <= */
+		} else {
+			m = strncmp(match, entry->path, maxlen);
+			if(m < 0)
+				return 0;
+		}
 
 		/*
 		 * If we come here even once, that means there is at
@@ -531,12 +535,17 @@ static int match_entry(const struct name_entry *entry, int pathlen,
 			return 0;
 	}
 
-	if (m == -1)
+	if (m == -1) {
 		/*
-		 * we cheated and did not do strncmp(), so we do
+		 * we cheated and did compare strings, so we do
 		 * that here.
 		 */
-		m = strncmp(match, entry->path, pathlen);
+		if (pathlen && match[0] == entry->path[0])
+			/* invariant: matchlen == pathlen */
+			m = strncmp(match, entry->path, pathlen);
+		else
+			m = 1;
+	}
 
 	/*
 	 * If common part matched earlier then it is a hit,
@@ -552,6 +561,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,
 static int match_dir_prefix(const char *base,
 			    const char *match, int matchlen)
 {
+	/* invariant: baselen >= matchlen */
 	if (strncmp(base, match, matchlen))
 		return 0;
 
-- 
1.7.4.2