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:
>
>> 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?
>
> In a followup mail i measured git fsck, which showed a speedup too. (despite
> being mostly dependent on external libraries to do most of the processing)
>
> If you'd like to see other things tested please suggest a testcase that you
> think uses these hashes extensively, i don't really know what the slowest (and
> affected) Git commands are - git gc is the one *i* notice as being pretty slow
> (for good reasons).
>

You only seem to test cases that iterate through the entire repo, and
I suspect that they might not be representative for all affected
use-cases.

So I'd love to see something like just timing of something like "git
diff > /dev/null" (and some other goodies) in a hot-cache repo with
and without your patch. Perhaps even timing of running the test-suite,
as this touches most git-commands...

>> 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.
>
> Even if that were true it can be solved: you'd need to declare the sha1 not as
> a char array but as a u32 * array or so. We do have control over the alignment
> of data structures, obviously.

True, but that's a very intrusive change. And it's not a bug-fix as
you indicated :)

>> 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.
>
> Well, should we ready be ready to throw up our hands as if we didnt have
> control over the alignment of objects and have to accept suboptimal code as a
> result? We do have control over that.

Yes, but it's better to pick low-hanging fruits and see if we can get
99% of the performance increase without having to change all of the
code. See my previous e-mail (Message-ID:
<BANLkTik-uk-mpdHZxcz8Nem=nEzED_tuJg@mail.gmail.com>) for what I
suspect will do the trick without causing problems.

> In any case, i'll retract the null case as it really isnt called that often in
> the tests i've done - updated patch below - it simply falls back on to hashcmp.

Nice, I think this makes sense. I already stole that hunk and
incorporated that in the diff I posted ;)