From: Andreas Ericsson <ae@op5.se>
To: Pekka Enberg <penberg@cs.helsinki.fi>
Cc: kusmabite@gmail.com, "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:17:51 +0200 [thread overview]
Message-ID: <4DB95AEF.5060609@op5.se> (raw)
In-Reply-To: <4DB941CD.2050403@cs.helsinki.fi>
On 04/28/2011 12:30 PM, Pekka Enberg wrote:
> Hi,
>
> On 4/28/11 1:19 PM, Erik Faye-Lund wrote:
>> On Thu, Apr 28, 2011 at 12:10 PM, Pekka Enberg<penberg@cs.helsinki.fi> wrote:
>>> On 4/28/11 12:50 PM, Erik Faye-Lund wrote:
>>>>>
>>>>> Alas, i have not seen these sha1 hash buffers being allocated unaligned
>>>>> (in my
>>>>> very limited testing). In which spots are they allocated unaligned?
>>>>
>>>> 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.
>>>
>>> I'd be very surprised if malloc() did "worst case alignment" - that'd suck
>>> pretty badly from performance point of view.
>>
>> From POSIX (I don't have K&R at hand, but it's also specified there):
>> "The pointer returned if the allocation succeeds shall be suitably
>> aligned so that it may be assigned to a pointer to any type of object
>> and then used to access such an object in the space allocated (until
>> the space is explicitly freed or reallocated)."
>>
>> I put it in quotes because it's not the worst-case alignment you can
>> ever think of, but rather the worst case alignment of your CPUs
>> alignment requirements. This is 4 bytes for most CPUs.
>
> That's just the minimum guarantee! Why do you think modern malloc() implementations don't try *very* hard to provide best possible alignment?
>
>>> 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.
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.
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
Considering the successes of the wars on alcohol, poverty, drugs and
terror, I think we should give some serious thought to declaring war
on peace.
next prev parent reply other threads:[~2011-04-28 12:18 UTC|newest]
Thread overview: 45+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-04-27 22:51 [PATCH] git gc: Speed it up by 18% via faster hash comparisons Ingo Molnar
2011-04-27 23:10 ` Ingo Molnar
2011-04-27 23:18 ` Jonathan Nieder
2011-04-28 6:36 ` Ingo Molnar
2011-04-28 9:31 ` Jonathan Nieder
2011-04-28 10:36 ` Ingo Molnar
2011-04-28 9:32 ` Dmitry Potapov
2011-04-27 23:32 ` Junio C Hamano
2011-04-28 0:35 ` Ralf Baechle
2011-04-28 8:18 ` Bernhard R. Link
2011-04-28 9:42 ` Andreas Ericsson
2011-04-28 9:55 ` Erik Faye-Lund
2011-04-28 20:19 ` H. Peter Anvin
2011-04-28 6:27 ` Ingo Molnar
2011-04-28 9:17 ` Erik Faye-Lund
2011-04-28 9:33 ` Ingo Molnar
2011-04-28 9:37 ` Ingo Molnar
2011-04-28 9:50 ` Erik Faye-Lund
2011-04-28 10:10 ` Pekka Enberg
2011-04-28 10:19 ` Erik Faye-Lund
2011-04-28 10:30 ` Pekka Enberg
2011-04-28 11:59 ` Erik Faye-Lund
2011-04-28 12:12 ` Pekka Enberg
2011-04-28 12:36 ` Jonathan Nieder
2011-04-28 12:40 ` Erik Faye-Lund
2011-04-28 13:37 ` Ingo Molnar
2011-04-28 15:14 ` Ingo Molnar
2011-04-28 16:00 ` Erik Faye-Lund
2011-04-28 20:32 ` Ingo Molnar
2011-04-29 7:05 ` Alex Riesen
2011-04-29 16:24 ` H. Peter Anvin
2011-04-28 12:16 ` Tor Arntsen
2011-04-28 20:23 ` H. Peter Anvin
2011-04-28 12:17 ` Andreas Ericsson [this message]
2011-04-28 12:28 ` Erik Faye-Lund
2011-04-28 10:19 ` Ingo Molnar
2011-04-28 12:02 ` Nguyen Thai Ngoc Duy
2011-04-28 12:18 ` Erik Faye-Lund
2011-04-28 20:20 ` Junio C Hamano
2011-04-28 16:36 ` Dmitry Potapov
2011-04-28 8:52 ` Dmitry Potapov
2011-04-28 9:11 ` Ingo Molnar
2011-04-28 9:31 ` Dmitry Potapov
2011-04-28 9:44 ` Ingo Molnar
2011-04-28 9:38 ` Ingo Molnar
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4DB95AEF.5060609@op5.se \
--to=ae@op5.se \
--cc=a.p.zijlstra@chello.nl \
--cc=acme@redhat.com \
--cc=fweisbec@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=hpa@zytor.com \
--cc=kusmabite@gmail.com \
--cc=mingo@elte.hu \
--cc=penberg@cs.helsinki.fi \
--cc=tglx@linutronix.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).