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 majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html