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) {
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to