Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons

From: Erik Faye-Lund <kusmabite@gmail.com>
Date: Apr 28, 2011, 12:18 UTC
Message-ID: <BANLkTikq=oZ4uk-MN_zOXmdKNq7O3XtJhQ@mail.gmail.com>
In-Reply-To: <20110428101902.GA17257@elte.hu>

2011/4/28 Ingo Molnar <mingo@elte.hu>:

Show 29 quoted lines

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

Show 7 quoted lines

>> 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 :)

Show 8 quoted lines

>> 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 ;)