<div class="gmail_quote">On Mon, Apr 18, 2011 at 9:44 PM, Douglas Gregor <span dir="ltr"><<a href="mailto:dgregor@apple.com">dgregor@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div bgcolor="#FFFFFF"><div><br>Sent from my iPhone</div><div><div></div><div class="h5"><div><br>On Apr 18, 2011, at 6:34 PM, Chandler Carruth <<a href="mailto:chandlerc@google.com" target="_blank">chandlerc@google.com</a>> wrote:<br>
<br></div><div></div><blockquote type="cite"><div><div class="gmail_quote">On Sat, Apr 16, 2011 at 1:48 PM, Török Edwin <span dir="ltr"><<a href="mailto:edwintorok@gmail.com" target="_blank"></a><a href="mailto:edwintorok@gmail.com" target="_blank">edwintorok@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>On 2011-04-16 23:32, Chandler Carruth wrote:<br>
> On Sat, Apr 16, 2011 at 5:01 AM, Benjamin Kramer<br>
</div><div><div></div><div>> <<a href="mailto:benny.kra@googlemail.com" target="_blank"></a><a href="mailto:benny.kra@googlemail.com" target="_blank">benny.kra@googlemail.com</a> <mailto:<a href="mailto:benny.kra@googlemail.com" target="_blank"></a><a href="mailto:benny.kra@googlemail.com" target="_blank">benny.kra@googlemail.com</a>>> wrote:<br>
><br>
> > 3.65% clang clang [.]<br>
> llvm::StringMapImpl::LookupBucketFor(llvm::StringRef)<br>
><br>
> I'm a bit surprised that StringMap is the most expensive entry here,<br>
> maybe microoptimizing<br>
> the hash function (which is a byte-wise djb hash at the moment) can<br>
> help a bit. If someone is<br>
> really bored it would also be useful to test if other string hash<br>
> functions like murmurhash or google's<br>
> new city hash give better performance.<br>
><br>
><br>
> Interesting. I'm familiar with murmurhash and watched the development of<br>
> city hash and am quite familiar with it. I'll take a look at what it<br>
> would take to use cityhash here. Anything special done to produce these<br>
> numbers? Just a build of the kernel?<br>
><br>
> If you could paste how you collected the perf data that would be useful<br>
> as well... i've not used the 'perf' tool extensively before.<br>
<br>
</div></div>Here is what I used:<br>
$ make allmodconfig<br>
$ perf record make CC=clang -j6<br>
(this creates a file perf.data, let it run for at least 2 or 5 minutes,<br>
then interrupt it, or wait for it to finish)<br>
$ perf report<br>
(ncurses-like interface to browse perf.data)<br></blockquote><div><br></div><div>Cool, thanks!</div><div><br></div><div>I was never able to get the lookup to take as much of my CPU time as you did, but the benchmarks were very noisy. When I used my own stress test benchmarks (massive C++ file and the single-source GCC file) I would see roughly 1.5% of the CPU cycles in this function.</div>
<div><br></div><div>I got CityHash into the codebase and taught StringMap to use it. This saved roughly 50% of the time in the function, taking it under the 1% line. I haven't looked in detail to see what is taking the time now.</div>
<div><br></div><div>On another benchmark where this function was a bit hotter (2.4% roughly, similar numbers to those I got by profiling the kernel build) I saw as much as 1% over-all speed up. Nothing stellar, but not terrible either.</div>
<div><br></div><div>If folks are interested, I'll look at getting City Hash checked in, and investigate using it in a few other places as well where collisions and/or hashing cost us some.</div></div></div></blockquote>
<br></div></div><div>Definitely interested!</div></div></blockquote></div><br><div>So, even using a "torture test" for this part of Clang (-Eonly on gcc.c, a 0.75 MLOC file) I can only make it about 0.5% to 1.5% faster overall. We stop getting collisions, and the CPU time spent in LookupBucketFor drops from 7% to 4%, along with memcmp time drops, but the time just goes elsewhere, at least for the test cases I have and the CPU I'm measuring on.</div>
<div><br></div><div>If anyone has a good test case to reproduce the performance impact and measure significant benefit from this, let me know and I'll send you my patch.</div>