2011/4/28 Ingo Molnar <mingo@xxxxxxx>:
>
> * Junio C Hamano <gitster@xxxxxxxxx> wrote:
>
>> Ingo Molnar <mingo@xxxxxxx> writes:
>>
>> > +static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2)
>> > {
>> > - return !memcmp(sha1, null_sha1, 20);
>> > + int i;
>> > +
>> > + for (i = 0; i < 20; i++, sha1++, sha2++) {
>> > + if (*sha1 != *sha2) {
>> > + if (*sha1 < *sha2)
>> > + return -1;
>> > + return +1;
>> > + }
Why not just:
if (*sha1 != *sha2)
return *sha2 - *sha1;
memcmp isn't guaranteed to return onlt the values -1, 0, +1, it can
return any value, just as long as it's sign of a non-zero return
express the relationship between the first mis-matching byte.
>> > + }
>> > +
>> > + return 0;
>>
>> This is very unfortunate, as it is so trivially correct and we shouldn't
>> have to do it. If the compiler does not use a good inlined memcmp(), this
>> patch may fly, but I fear it may hurt other compilers, no?
If the common case is that the hashes are random (as the assumption in
this patch is), then this patch should give very close to ideal
performance, no? A good memcmp might be faster when there's a match;
but how often do we really compare SHA-1's that are identical?
I see your worry, but if the assumption is correct, I doubt it'd turn
out to be a real problem. ~99.6% of the time we'd early-out on the
first byte, which is ideal.
If comparing identical SHA-1's are important, perhaps just having a
early-out just on the first byte and then doing memcmp is a good
solution (similar to what Jonathan Nieder proposed, but without
alignment problems)?
> 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?
>> > +static inline int is_null_sha1(const unsigned char *sha1)
>> > {
>> > - return memcmp(sha1, sha2, 20);
>> > + const unsigned long long *sha1_64 = (void *)sha1;
>> > + const unsigned int *sha1_32 = (void *)sha1;
>>
>> Can everybody do unaligned accesses just fine?
>
> 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.
--
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