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

From: Jonathan Nieder <jrnieder@gmail.com>
Date: Apr 28, 2011, 09:31 UTC
Message-ID: <20110428093120.GA377@elie>
In-Reply-To: <20110428063625.GB952@elte.hu>

Ingo Molnar wrote:

> * Jonathan Nieder <jrnieder@gmail.com> wrote:

Show 16 quoted lines

>> E.g., how would something like
>>
>> 	const unsigned int *start1 = (const unsigned int *) sha1;
>> 	const unsigned int *start2 = (const unsigned int *) sha2;
>>
>> 	if (likely(*start1 != *start2)) {
>> 		if (*start1 < *start2)
>> 			return -1;
>> 		return +1;
>> 	}
>> 	return memcmp(sha1 + 4, sha2 + 4, 16);
>>
>> perform?
>
> Note that this function wont work on like 99% of the systems out there due to 
> endianness assumptions in Git.

Yes, I was greedy and broke the semantics, and my suggestion was nonsensical for other reasons (e.g., alignment), too. I should have written something like:

	if (likely(*sha1 != *sha2)) {
		if (*sha1 < *sha2)
			return -1;
		return +1;
	}
	return memcmp(sha1, sha2, 20);

since speeding it up 255/256 times seems good enough already.

> Also, your hypothetical smart compiler would recognize the above as equivalent 
> to memcmp(sha1, sha2, 20) and could rewrite it again - so we'd be back to 
> square 1.

True. The real point is a "likely" to explain to human readers what is happening.

Show 13 quoted lines

> Having said that, it would be nice if someone could test these two patches on a 
> modern AMD box, using the perf stat from here:
>
>   http://people.redhat.com/mingo/tip.git/README
>
>   cd tools/perf/
>   make -j install
>
> and do something like this to test git gc's performance:
>
>   $ perf stat --sync --repeat 10 ./git gc
>
> ... to see whether these speedups are generic, or somehow Intel CPU specific.

Sounds like fun. Will try to find time to play around with this in the next few days.

> Well i messed up endianness in an early version of this patch and 'git gc' was
> eminently unhappy about it! I have not figured out which part of Git relies on
> the comparison result though - most places seem to use the result as a boolean.

I think hashcmp is used to run binary searches within a packfile index. Thanks for explaining.

Regards, Jonathan