Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons

[Erik Faye-Lund <kusmabite@gmail.com>]

2011/4/28 Ingo Molnar <mingo@elte.hu>:
>
> * Erik Faye-Lund <kusmabite@gmail.com> wrote:
>
>> > Secondly, the combined speedup of the cached case with my two patches
>> > appears to be more than 30% on my testbox so it's a very nifty win from two
>> > relatively simple changes.
>>
>> That speed-up was on ONE test vector, no? There are a lot of other uses of
>> hash-comparisons in Git, did you measure those?
>
> I picked this hash function because it showed up in the profile (see the
> profile i posted). There's one other hash that mattered as well in the profile,
> see the lookup_object() patch i sent yesterday.
>

My point was that the 30% improvement was in "git gc", which is not
the only important use-case. How does this affect other git commands?

My suspicion is that it's generally an improvement, but I don't know
for sure. I think something like this might be an acceptable
trade-off, though:

diff --git a/cache.h b/cache.h
index c730c58..50b6f55 100644
--- a/cache.h
+++ b/cache.h
@@ -687,6 +687,10 @@ static inline int is_null_sha1(const unsigned char *sha1)
 }
 static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)
 {
+	/* early out for fast mis-match */
+	if (*sha1 != *sha2)
+		return *sha2 - *sha1;
+
 	return memcmp(sha1, sha2, 20);
 }
 static inline void hashcpy(unsigned char *sha_dst, const unsigned
char *sha_src)

>> > I have added some quick debug code and none of the sha1 pointers (in my
>> > admittedly very limited) testing showed misaligned pointers on 64-bit
>> > systems.
>> >
>> > On 32-bit systems the pointer might be 32-bit aligned only - the patch
>> > below implements the function 32-bit comparisons.
>>
>> That's simply wrong. Unsigned char arrays can and will be unaligned, and this
>> causes exceptions on most architectures (x86 is pretty much the exception
>> here). While some systems for these architectures support unaligned reads
>> from the exception handler, others doesn't. So this patch is pretty much
>> guaranteed to cause a crash in some setups.
>
> If unsigned char arrays are allocated unaligned then that's another bug i
> suspect that should be fixed.

We can't. The compiler decides the alignment of variables on the
stack. Some compilers / compiler-setting pairs might align
char-arrays, while others might not.

> Unaligned access on x86 is not free either -
> there's cycle penalties.
>
> Alas, i have not seen these sha1 hash buffers being allocated unaligned (in my
> very limited testing). In which spots are they allocated unaligned?

Like I said above, it can happen when allocated on the stack. But it
can also happen in malloc'ed structs, or in global variables. An array
is aligned to the size of it's base member type. But malloc does
worst-case-allignment, because it happens at run-time without
type-information.