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

From: Erik Faye-Lund <kusmabite@gmail.com>
To: Andreas Ericsson <ae@op5.se>
Cc: "Pekka Enberg" <penberg@cs.helsinki.fi>,
	"Ingo Molnar" <mingo@elte.hu>,
	"Junio C Hamano" <gitster@pobox.com>,
	git@vger.kernel.org, "H. Peter Anvin" <hpa@zytor.com>,
	"Thomas Gleixner" <tglx@linutronix.de>,
	"Peter Zijlstra" <a.p.zijlstra@chello.nl>,
	"Arnaldo Carvalho de Melo" <acme@redhat.com>,
	"Frédéric Weisbecker" <fweisbec@gmail.com>
Subject: Re: [PATCH] git gc: Speed it up by 18% via faster hash comparisons
Date: Thu, 28 Apr 2011 14:28:03 +0200	[thread overview]
Message-ID: <BANLkTi=B4nQPC7CrLkpmn4AhwjOAvs82qw@mail.gmail.com> (raw)
In-Reply-To: <4DB95AEF.5060609@op5.se>

On Thu, Apr 28, 2011 at 2:17 PM, Andreas Ericsson <ae@op5.se> wrote:
>>>> Stack allocation alignment is a harder issue but I doubt it's as bad as you
>>>> make it out to be. On x86, for example, stack pointer is almost always 8 or
>>>> 16 byte aligned with compilers whose writers have spent any time reading the
>>>> Intel optimization manuals.
>>>>
>>>> So yes, your statements are absolutely correct but I strongly doubt it
>>>> matters that much in practice unless you're using a really crappy
>>>> compiler...
>>>
>>> I'm sorry, but the the fact of the matter is that we don't write code
>>> for one compiler, we try to please many. Crappy compilers are very
>>> much out there in the wild, and we have to deal with it. So, we can't
>>> depend on char-arrays being aligned to 32-bytes. This code WILL break
>>> on GCC for ARM, so it's not a theoretical issue at all. It will also
>>> most likely break on GCC for x86 when optimizations are disabled.
>>
>> Yes, ARM is a problem and I didn't try to claim otherwise. However, it's not "impossible to fix" as you say with memalign().
>>
>
> #define is_aligned(ptr) (ptr & (sizeof(void *) - 1))
> if (is_aligned(sha1) && is_aligned(sha2))
>        return aligned_and_fast_hashcmp(sha1, sha2);
>
> return memcmp(sha1, sha2, 20);
>
> Problem solved for all architectures. Not as fast as the original
> patch when we're lucky with alignment, but we cater to sucky
> compilers and make the good ones go a lot faster. The really good
> compilers that recognizes "is it aligned?" checks will optimize the
> is_aligned() checks away or at least hint at the branch prediction
> which path it should prefer.

I'd rather go with the do-not-introduce-the-problem-in-the-first-place
approach. As I've pointed out many times already, the vast majority of
the performance increase comes from the early-out in the first
iteration. Why not just special case that ONE check, and do memcmp as
usual for the rest? The first iteration should affect 99.6% of all
mismatches, so it should have nice performance even for the unaligned
case. This gives us both speed and portability.

> Once again; Bear in mind that x86 style architectures with gcc is
> almost certainly the most common combo for git users by a very wide
> margin, so a 25-30% speedup for those users is pretty worthwhile.

Again, I never argued against speed. I argued against going a route
that is tricky to get right. Very reasonable alternatives were posted,
including Ingo's last patch.