Re: Make GIT_USE_LOOKUP default?

Jeff King [off-list ref] writes:

On Mon, Mar 18, 2013 at 09:44:20AM -0700, Junio C Hamano wrote:

quoted

FWIW, I am getting something like this on my

$ grep 'model name' /proc/cpuinfo | uniq -c
  4 model name      : Intel(R) Core(TM)2 Quad  CPU   Q9450  @ 2.66GHz

The same "rev-list --objects --all >/dev/null", best of five:

[current master, compiled with -O2]
real    0m39.956s
user    0m39.562s
sys     0m0.396s

[revert 1a812f3 (i.e., go back to memcmp), -O2]
real    0m42.161s
user    0m41.879s
sys     0m0.284s

It could be that the difference may be how well memcmp() is
optimized, no?  My box runs Debian with libc6 2.11.3-4 and gcc
4.4.5.

Yeah, that would make sense. I have libc6 2.13-38 and gcc 4.7.2 (debian
unstable).

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?

[without GIT_USE_LOOKUP]
0inputs+0outputs (0major+182895minor)pagefaults 0swaps
0inputs+0outputs (0major+182920minor)pagefaults 0swaps
0inputs+0outputs (0major+183004minor)pagefaults 0swaps
0inputs+0outputs (0major+183006minor)pagefaults 0swaps
0inputs+0outputs (0major+183036minor)pagefaults 0swaps

[with GIT_USE_LOOKUP]
0inputs+0outputs (0major+182803minor)pagefaults 0swaps
0inputs+0outputs (0major+182886minor)pagefaults 0swaps
0inputs+0outputs (0major+182967minor)pagefaults 0swaps
0inputs+0outputs (0major+182997minor)pagefaults 0swaps
0inputs+0outputs (0major+182998minor)pagefaults 0swaps

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) {