<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Mar 18, 2015 at 1:48 PM, Benjamin Kramer <span dir="ltr"><<a href="mailto:benny.kra@gmail.com" target="_blank">benny.kra@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 class="HOEnZb adM"><div class="">> FYI we have StringMap which is specialized for strings. Also I'm sort of<br>
> amazed that StringMap is using HashString (bernstein) instead of the fairly<br>
> sophisticated hash functionality we have in ADT/Hashing.h<br>
<br>
</div></div>I tried using the new hashing back when Hashing.h was written. The<br>
result was that there were fewer collisions, but the hash function was<br>
significantly slower. Result was a net regression in runtime.</blockquote></div><br>FWIW, I did a somewhat more deep analysis of this while I was writing the new hashing stuff.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Fundamentally, StringMap is not a generic string map. It is an source code identifier map.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Source code identifiers tend to be *very* short and tend to fit exactly into the non-colliding space of bernstein. As a consequence, the collisions "aren't too bad" and the runtime is actually faster. For longer strings, Hashing.h will be *tremendously* faster than bernstein, but we never use StringMap for that purpose in a critical path.</div><div class="gmail_extra"><br></div><div class="gmail_extra">We should really use a totally different approach for the identifier maps in Clang that is completely tailored to that (weird) use case, and then StringMap could be usefully switched to the more robust hashing.</div></div>