From: Ingo Molnar <mingo@elte.hu>
Date: Thu, 28 Apr 2011 09:44:59 GMT
Subject: Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons
Message-ID: <20110428094459.GA15952@elte.hu>
In-Reply-To: <BANLkTikWd8=1RbY78tPFMVhuV05eKVzjkg@mail.gmail.com>


* Dmitry Potapov <dpotapov@gmail.com> wrote:

> 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.

> 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