Sorry for coming late to this thread. I've been very active in recent work on hashing routines inside and outside of Google, so I've a keen interest in this...<div><br></div><div>Some initial clarifications:<br><br>
<div class="gmail_quote">On Tue, Feb 14, 2012 at 2:26 AM, Chris Lattner <span dir="ltr"><<a href="mailto:clattner@apple.com">clattner@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 class="im"><br>
On Feb 13, 2012, at 1:27 AM, Jay Foad wrote:<br>
<br>
> On 13 February 2012 09:22, Jay Foad <<a href="mailto:jay.foad@gmail.com">jay.foad@gmail.com</a>> wrote:<br>
>> Would it be possible to use CityHash instead for strings?<br>
>><br>
>> <a href="http://code.google.com/p/cityhash/" target="_blank">http://code.google.com/p/cityhash/</a><br>
><br>
> Incidentally there was talk of using CityHash for LLVM's StringMap<br>
> last year, but I don't think it ever came to anything:<br>
><br>
> <a href="http://lists.cs.uiuc.edu/pipermail/cfe-dev/2011-April/014656.html" target="_blank">http://lists.cs.uiuc.edu/pipermail/cfe-dev/2011-April/014656.html</a><br>
<br>
</div>At that point, there wasn't a clear win.  CityHash (iirc) is optimized for huge strings, which aren't the usual case in the compiler AFAIK.<br></blockquote><div><br></div><div>This isn't entirely accurate. Let me try to clarify.</div>
<div><br></div><div>For reference, I'm the one that did this. I looked at both DenseMap and StringMap quite closely. I replaced all of the hashing I could to use CityHash. The reason I did this was because collisions in the hash table showed up on the profile in a few test cases with Clang.</div>
<div><br></div><div>However, when measuring it, what I observed was that while the collisions did show up, they were still small enough overall that increasing the complexity of the hash function to achieve fewer collisions was not in fact a good tradeoff. They just didn't happen *that* often.</div>
<div><br></div><div><br></div><div>CityHash has some specializations for larger strings to make it a reasonably good hash function, but for truly huge strings, it still isn't ideal. There are some very interesting CRC instruction based hashing strategies that are much more promising for *huge* datasets. The goal of CityHash is to be an excellent hashing function for *general* usage. That includes small strings, ints, structs, and other common keys.</div>
<div><br></div><div>That said, any really high quality hash function is going to spend more cycles-per-byte on small inputs than an large inputs because it is harder to "mix" smaller inputs sufficiently. This doesn't make CityHash bad for general usage, it's just something to be aware of.</div>
<div><br></div><div>I measured *no* performance degradation from switching to cityhash. These benchmarks as well as others led to libc++ adopting CityHash for its unordered containers. The reason I didn't push forward is that I also measured no performance improvements from it for LLVM and Clang. The reason seemed pretty clear: there aren't enough collisions for a higher quality hashing algorithm to have a high impact. LLVM and Clang's tables are (relatively speaking) very small. Doesn't mean a bad algorithm should be kept around, but it limited the amount of time I wanted to invest.</div>
</div></div>