Re: Make GIT_USE_LOOKUP default?

On Mon, Mar 18, 2013 at 10:08:11AM -0700, Junio C Hamano wrote:

Just for fun, here is a totally unrelated comparison, both with
current master, compiled with -O2 and running on the same box.

[without GIT_USE_LOOKUP]
real    0m39.906s
real    0m40.020s
real    0m40.022s
real    0m40.027s
real    0m40.146s

[with GIT_USE_LOOKUP]
real    0m40.336s
real    0m40.376s
real    0m40.452s
real    0m40.503s
real    0m40.572s

Maybe the Newton-Raphson is right as a concept (it does seem to
result in fewer minor-faults) but the current code is implemented
poorly and has a huge room for improvement?

I do not see anything obviously wrong in it, though I did not walk
through all of the ofs calculation to look for any clever speedups.
However, I think it is clear from the other timings and Ingo's thread
that glibc 2.11's memcmp does not perform very well on many short reads.
And sha1_entry_pos will do memcmps even smaller than 20 bytes.

What happens if you do this?

diff --git a/sha1-lookup.c b/sha1-lookup.c
index c4dc55d..4ea03bd 100644
--- a/sha1-lookup.c
+++ b/sha1-lookup.c

@@ -102,6 +102,17 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,
 	return -lo-1;
 }
 
+static int short_memcmp(const unsigned char *a,
+			const unsigned char *b,
+			int len)
+{
+	int i;
+	for (i = 0; i < len; i++, a++, b++)
+		if (*a != *b)
+			return *a - *b;
+	return 0;
+}
+
 /*
  * Conventional binary search loop looks like this:
  *

@@ -257,7 +268,7 @@ int sha1_entry_pos(const void *table,
 			    lo, mi, hi, sha1_to_hex(key));
 
 		mi_key = base + elem_size * mi + key_offset;
-		cmp = memcmp(mi_key + ofs_0, key + ofs_0, 20 - ofs_0);
+		cmp = short_memcmp(mi_key + ofs_0, key + ofs_0, 20 - ofs_0);
 		if (!cmp)
 			return mi;
 		if (cmp > 0) {