[LLVMdev] We need better hashing

[Bryce Cogswell]

On Feb 15, 2012, at 2:05 AM, Jeffrey Yasskin wrote:
> On Tue, Feb 14, 2012 at 2:44 AM, Chris Lattner <clattner at apple.com> wrote:
>> 
>> I'm contradicting my stance above about not caring about the implementation
>> :), but is MurmurHash a good hash for string data?  The Bernstein hash
>> function works really well and is much cheaper to compute than Murmur.
> 
> Have you seen benchmarks saying that, or are you just guessing from
> the length of the code? The benchmarks I've seen say the opposite:
> http://code.google.com/p/smhasher/wiki/MurmurHash3#Bulk_speed_test,_hashing_an_8-byte-aligned_256k_block
> and http://code.google.com/p/cityhash/source/browse/trunk/README.
> 

These are the numbers I come up with, graphing time (ns) vs. string length (chars), using the current Xcode compiler, 64-bit, -O3. 
Bernstein is inlined while Murmor and CityHash are not:


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120215/2317e316/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PastedGraphic-5.tiff
Type: image/tiff
Size: 42934 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120215/2317e316/attachment.tiff>