[LLVMdev] Proposed implementation of N3333 hashing interfaces for LLVM (and possible libc++)

[Tobias Grosser]

On 02/28/2012 12:34 PM, Chandler Carruth wrote:
> Hello folks,
>
> TL;DR: This is my proposed hashing interface based on a proposed
> standard hashing interface. It also is implemented with a much faster
> and higher quality algorithm than the current one. This is an *early
> draft* of the code, looking for initial feedback.
>
>
> There has been recent interest in improving the quality and consistency
> of LLVM's approach to hashing. In particular, getting a single API and a
> high quality implementation in one place that other parts of the
> codebase can use to hash custom data structures. As it happens, Jeffrey
> Yasskin and I have been working on a proposal with similar goals to the
> the C++ standard library[1].

Hi Chandler,

I just skimmed over the proposal and it seems very interesting to me. 
Unfortunately I did not have time to look further into it.

One point that I found surprising is that your hashing is in most cases 
notably faster than the old LLVM hashing, except for key sizes which are 
a modulo of 4. Here the existing hash function is a lot faster than your 
new solution. If keys that are multiple of 4 bytes are common in LLVM, 
it might be worth to check if this change does not cause performance 
regressions.


> old_llvm_performance.txt
>
>
> -------------------------------------------------------------------------------
> --- Testing llvm (LLVM Hashing)
>
> [[[ Speed Tests ]]]
>
> Small key speed test -    4-byte keys -    16.77 cycles/hash      7.39 nanos/hash
> Small key speed test -    8-byte keys -    25.93 cycles/hash     11.43 nanos/hash
> Small key speed test -   12-byte keys -    30.39 cycles/hash     13.39 nanos/hash
> Small key speed test -   16-byte keys -    30.18 cycles/hash     13.30 nanos/hash
> Small key speed test -   20-byte keys -    39.33 cycles/hash     17.34 nanos/hash
> Small key speed test -   24-byte keys -    44.70 cycles/hash     19.70 nanos/hash
> Small key speed test -   28-byte keys -    49.17 cycles/hash     21.68 nanos/hash

> new_llvm_performance.txt
>
>
> -------------------------------------------------------------------------------
> --- Testing std64 (LLVM Standard-baed Hashing)
>
> [[[ Speed Tests ]]]
>
> Small key speed test -    4-byte keys -    40.22 cycles/hash     17.73 nanos/hash
> Small key speed test -    8-byte keys -    40.24 cycles/hash     17.73 nanos/hash
> Small key speed test -   12-byte keys -    44.69 cycles/hash     19.70 nanos/hash
> Small key speed test -   16-byte keys -    44.69 cycles/hash     19.70 nanos/hash
> Small key speed test -   24-byte keys -    50.95 cycles/hash     22.46 nanos/hash
> Small key speed test -   28-byte keys -    50.95 cycles/hash     22.46 nanos/hash

Cheers
Tobi