Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons
- From
- Ingo Molnar <mingo@elte.hu>
- Date
- Apr 28, 2011, 06:27 UTC
- Message-ID
- <20110428062717.GA952@elte.hu>
- In-Reply-To
- <7voc3r5kzn.fsf@alter.siamese.dyndns.org>
* Junio C Hamano <gitster@pobox.com> wrote:
Show 20 quoted lines
> Ingo Molnar <mingo@elte.hu> 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;
> > + }
> > + }
> > +
> > + 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?Well, i used a very fresh GCC version:
gcc version 4.6.0 20110419 (Red Hat 4.6.0-5) (GCC)
And used a relatively fresh CPU as well. So given how compiler and CPU versions trickle down to users and how long they live there Git will live with this combination for years to come.
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.
Should a compiler ever turn this into suboptimal code again we can revisit the issue once more - it's not like we *can* keep the compiler from messing up the assembly output! :-) ...
Show 7 quoted lines
> > +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.
But is_null_sha1() is not called that often in the tests i've done so we could keep it untouched as well.
Thanks,
Ingo
diff --git a/cache.h b/cache.h index 2674f4c..427ad5a 100644 --- a/cache.h +++ b/cache.h @@ -675,14 +675,32 @@ extern char *sha1_pack_name(const unsigned char *sha1); extern char *sha1_pack_index_name(const unsigned char *sha1); extern const char *find_unique_abbrev(const unsigned char *sha1, int); extern const unsigned char null_sha1[20]; -static inline int is_null_sha1(const unsigned char *sha1) + +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; + } + } + + return 0; } -static inline int hashcmp(const unsigned char *sha1, const unsigned char *sha2) + +static inline int is_null_sha1(const unsigned char *sha1) { - return memcmp(sha1, sha2, 20); + const unsigned int *sha1_32 = (void *)sha1; + + if (sha1_32[0] || sha1_32[1] || sha1_32[2] || sha1_32[3] || sha1_32[4]) + return 0; + + return 1; } + static inline void hashcpy(unsigned char *sha_dst, const unsigned char *sha_src) { memcpy(sha_dst, sha_src, 20);