Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons
- From
- Ingo Molnar <mingo@elte.hu>
- Date
- Apr 28, 2011, 09:44 UTC
- Message-ID
- <20110428094459.GA15952@elte.hu>
- In-Reply-To
- <BANLkTikWd8=1RbY78tPFMVhuV05eKVzjkg@mail.gmail.com>
* Dmitry Potapov <dpotapov@gmail.com> wrote:
Show 26 quoted lines
> 2011/4/28 Ingo Molnar <mingo@elte.hu>:
> >
> > * Dmitry Potapov <dpotapov@gmail.com> wrote:
> >
> >> 2011/4/28 Ingo Molnar <mingo@elte.hu>:
> >> > +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) {
> >>
> >> At the very least, you may want to put 'likely' in this 'if'
> >> condition, otherwise the compiler may optimize this loop in
> >> the same way as with memcmp. So, it may work well now, but
> >> it may not work much slower with future versions or different
> >> level of optimization. (AFAIK, -O3 is far more aggressive in
> >> optimizing of loops).
> >
> > the main difference is between the string assembly instructions and the loop.
> > Modern CPUs will hardly notice this loop being emitted with slight variations
> > by the compiler. So i do not share this concern.
>
> Here you make an assumption what kind of optimization the compiler
> can do. [...]I make no assumption there because rule #1 is that the compiler can pretty well do what it wants and we have little control over that.
> [...] As Jonathan noticed above, theoretically a smart compiler can turn this > loop into memcmp (or code very similar to memcmp).
Yes, and in practice it does not, and in practice we can speed up git gc measurably.
Show 11 quoted lines
> The reason why memcmp does not work well is that it is optimized > for the worst case scenario (where beginning of two strings is > the same), while _we_ know that with a hash it very unlikely, > and we want to conduct this knowledge to the compiler in some > way. Just re-writing memcmp as explicit loop does not conduct > this knowledge. > > Therefore, I believe it makes sense to add 'likely'. I have not > tested this code, but in the past, I had a very similar code > which was compiled with -O3, and just putting likely turned out > to 40% speed-up for that comparison function.
You guys can certainly add the 'likely()' if you want to (it likely wont hurt) - but note that the compiler can *still* turn it into a memcpy() - see rule #1 above.
Note that Git does not have a likely() facility at the moment and __builtin_expect() is a GNU extension. Should be a separate patch.
Thanks,
Ingo