<html>

  <head>

    <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">

  </head>

  <body bgcolor="#FFFFFF" text="#000000">

    <meta http-equiv="content-type" content="text/html;

      charset=ISO-8859-1">

    <pre style="color: rgb(0, 0, 0); font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); ">

On Fri, Feb 17, 2012 at 3:59 AM, Chandler Carruth <chandlerc at google.com> wrote:

<blockquote type="cite"><pre style="color: rgb(0, 0, 0); font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; background-color: rgb(255, 255, 255);">On Tue, Feb 14, 2012 at 2:44 AM, Chris Lattner <<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">clattner at apple.com</a>> wrote:

><i> I'm contradicting my stance above about not caring about the

</i>><i> implementation :), but is MurmurHash a good hash for string data?

</i>><i>  The Bernstein hash function works really well and is much cheaper to

</i>><i> compute than Murmur.  It is used by HashString (and thus by StringMap).

</i>

If you want a good string hashing function, CityHash is by a fair margin

the best one out there. Look at the comparison done by Craig, Howard, and

several others when discussing what hashing function to use for libc++.

The only downside to CityHash is code size. It is heavily tuned, and that

results in several special case routines to get maximal efficiency and hash

quality for short strings (yep, not just huge ones). That said, the code

size increase was measured carefully for libc++ and it's really quite small.

</pre></blockquote>What about machines that are big endian, 32-bit, or less optimized for unaligned

accesses than x86?  From

<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1"><a href="http://code.google.com/p/cityhash/source/browse/trunk/README">http://code.google.com/p/cityhash/source/browse/trunk/README</a>:

> Functions that don't use the CRC32 instruction should also work, slowly,

> in little-endian 32-bit code.  CityHash should work on big-endian CPUs as well;

I ported CityHash about a year ago to a niche research architecture that is all

three of the above, and found that the byteswapping and unaligned loads

killed performance (the target only supports naturally aligned loads).

It's quite possible that x86 is the only target we care about in terms of

compile time performance, just wanted to see if CityHash had since been generalized

to work well on less general-purpose-focused targets, or if there was

something else I was overlooking when I did my initial experiments.

-Matt 

<blockquote type="cite"><meta http-equiv="content-type" content="text/html; charset=ISO-8859-1"></blockquote>

<blockquote type="cite"><pre style="color: rgb(0, 0, 0); font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); ">

That said, I have no benchmarks showing this matters for our uses of

StringMap. It reduced collisions, it didn't show up as a hot function, but

the collisions and the hashing simply didn't dominate any profiles I looked

at....</pre>

</blockquote></pre>

  </body>

</html>