[cfe-dev] RFC: change string hash function in libc++
David Blaikie
dblaikie at gmail.com
Fri Dec 2 15:58:13 PST 2011
On Fri, Dec 2, 2011 at 3:52 PM, Craig Silverstein <csilvers at google.com> wrote:
> } What are the numbers behind these "performs better"?
>
> Austin Appleby (the murmurhash author) agreed to run some numbers.
> Here's his report. The executive summary is that city is *much*
> faster for strings >512 bytes, and murmur is a bit faster for strings
> <512 bytes.
>
> craig
>
> -- cut here--
>
> SMHasher can generate performance numbers for various hash functions -
> below are numbers for Murmur and City generated on my desktop machine
> (I added the additional block sizes that chandlerc requested and
> tweaked SMHasher's output a bit to make comparison easier).
>
> Generally speaking, City is _much_ faster for large blocks (more loop
> unrolling),
Curious - is it relevant which compiler/optimization levels were used
for this comparison?
> Murmur is faster for small blocks. The crossover point in
> the data below is at 512 bytes.
>
> "Resistance to collisions" is harder to quantify, but any hash
> function that passes all the tests in SMHasher's test suite should be
> virtually indistiguishable from a random oracle in most applications -
> it is quite thorough.
>
> -Austin
>
>
> -------------------------------------------------------------------------------
> --- Testing Murmur3F (MurmurHash3 for x64, 128-bit)
>
> [[[ Sanity Tests ]]]
>
> Verification value 0x6384BA69 : Passed!
> Running sanity check 1..........PASS
> Running sanity check 2..........PASS
>
> [[[ Speed Tests ]]]
>
> Bulk speed test - 262144-byte keys
> Alignment 0 - 2.267 bytes/cycle - 6486.33 MiB/sec @ 3 ghz
> Alignment 1 - 2.254 bytes/cycle - 6449.27 MiB/sec @ 3 ghz
> Alignment 2 - 2.254 bytes/cycle - 6448.78 MiB/sec @ 3 ghz
> Alignment 3 - 2.254 bytes/cycle - 6449.09 MiB/sec @ 3 ghz
> Alignment 4 - 2.254 bytes/cycle - 6449.76 MiB/sec @ 3 ghz
> Alignment 5 - 2.254 bytes/cycle - 6448.82 MiB/sec @ 3 ghz
> Alignment 6 - 2.254 bytes/cycle - 6449.13 MiB/sec @ 3 ghz
> Alignment 7 - 2.254 bytes/cycle - 6449.25 MiB/sec @ 3 ghz
>
> Small key speed test - 1-byte keys - 32.34 cycles/hash, 0.03 bytes/cycle
> Small key speed test - 2-byte keys - 33.51 cycles/hash, 0.06 bytes/cycle
> Small key speed test - 3-byte keys - 37.80 cycles/hash, 0.08 bytes/cycle
> Small key speed test - 4-byte keys - 34.81 cycles/hash, 0.11 bytes/cycle
> Small key speed test - 5-byte keys - 37.85 cycles/hash, 0.13 bytes/cycle
> Small key speed test - 6-byte keys - 41.63 cycles/hash, 0.14 bytes/cycle
> Small key speed test - 7-byte keys - 37.31 cycles/hash, 0.19 bytes/cycle
> Small key speed test - 8-byte keys - 42.23 cycles/hash, 0.19 bytes/cycle
> Small key speed test - 9-byte keys - 43.03 cycles/hash, 0.21 bytes/cycle
> Small key speed test - 10-byte keys - 43.93 cycles/hash, 0.23 bytes/cycle
> Small key speed test - 11-byte keys - 41.56 cycles/hash, 0.26 bytes/cycle
> Small key speed test - 12-byte keys - 47.35 cycles/hash, 0.25 bytes/cycle
> Small key speed test - 13-byte keys - 46.47 cycles/hash, 0.28 bytes/cycle
> Small key speed test - 14-byte keys - 47.23 cycles/hash, 0.30 bytes/cycle
> Small key speed test - 15-byte keys - 47.12 cycles/hash, 0.32 bytes/cycle
> Small key speed test - 16-byte keys - 37.67 cycles/hash, 0.42 bytes/cycle
>
> Small key speed test - 16-byte keys - 37.52 cycles/hash, 0.43 bytes/cycle
> Small key speed test - 32-byte keys - 44.09 cycles/hash, 0.73 bytes/cycle
> Small key speed test - 48-byte keys - 49.50 cycles/hash, 0.97 bytes/cycle
> Small key speed test - 64-byte keys - 55.31 cycles/hash, 1.16 bytes/cycle
> Small key speed test - 80-byte keys - 64.95 cycles/hash, 1.23 bytes/cycle
> Small key speed test - 96-byte keys - 67.22 cycles/hash, 1.43 bytes/cycle
> Small key speed test - 112-byte keys - 78.28 cycles/hash, 1.43 bytes/cycle
> Small key speed test - 128-byte keys - 83.05 cycles/hash, 1.54 bytes/cycle
>
> Small key speed test - 128-byte keys - 83.01 cycles/hash, 1.54 bytes/cycle
> Small key speed test - 256-byte keys - 135.33 cycles/hash, 1.89 bytes/cycle
> Small key speed test - 384-byte keys - 192.02 cycles/hash, 2.00 bytes/cycle
> Small key speed test - 512-byte keys - 248.00 cycles/hash, 2.06 bytes/cycle
> Small key speed test - 640-byte keys - 300.39 cycles/hash, 2.13 bytes/cycle
> Small key speed test - 768-byte keys - 345.25 cycles/hash, 2.22 bytes/cycle
> Small key speed test - 896-byte keys - 405.33 cycles/hash, 2.21 bytes/cycle
> Small key speed test - 1024-byte keys - 455.43 cycles/hash, 2.25 bytes/cycle
>
> -------------------------------------------------------------------------------
> --- Testing City128
>
> [[[ Sanity Tests ]]]
>
> Verification value 0x94B0EF46 : Passed!
> Running sanity check 1..........PASS
> Running sanity check 2..........PASS
>
> [[[ Speed Tests ]]]
>
> Bulk speed test - 262144-byte keys
> Alignment 0 - 3.785 bytes/cycle - 10828.44 MiB/sec @ 3 ghz
> Alignment 1 - 3.761 bytes/cycle - 10761.34 MiB/sec @ 3 ghz
> Alignment 2 - 3.762 bytes/cycle - 10761.92 MiB/sec @ 3 ghz
> Alignment 3 - 3.762 bytes/cycle - 10762.20 MiB/sec @ 3 ghz
> Alignment 4 - 3.762 bytes/cycle - 10763.49 MiB/sec @ 3 ghz
> Alignment 5 - 3.762 bytes/cycle - 10763.35 MiB/sec @ 3 ghz
> Alignment 6 - 3.762 bytes/cycle - 10763.35 MiB/sec @ 3 ghz
> Alignment 7 - 3.762 bytes/cycle - 10763.96 MiB/sec @ 3 ghz
>
> Small key speed test - 1-byte keys - 52.36 cycles/hash, 0.02 bytes/cycle
> Small key speed test - 2-byte keys - 53.84 cycles/hash, 0.04 bytes/cycle
> Small key speed test - 3-byte keys - 54.89 cycles/hash, 0.05 bytes/cycle
> Small key speed test - 4-byte keys - 62.12 cycles/hash, 0.06 bytes/cycle
> Small key speed test - 5-byte keys - 55.49 cycles/hash, 0.09 bytes/cycle
> Small key speed test - 6-byte keys - 53.68 cycles/hash, 0.11 bytes/cycle
> Small key speed test - 7-byte keys - 54.99 cycles/hash, 0.13 bytes/cycle
> Small key speed test - 8-byte keys - 56.67 cycles/hash, 0.14 bytes/cycle
> Small key speed test - 9-byte keys - 58.90 cycles/hash, 0.15 bytes/cycle
> Small key speed test - 10-byte keys - 56.44 cycles/hash, 0.18 bytes/cycle
> Small key speed test - 11-byte keys - 58.28 cycles/hash, 0.19 bytes/cycle
> Small key speed test - 12-byte keys - 58.38 cycles/hash, 0.21 bytes/cycle
> Small key speed test - 13-byte keys - 57.48 cycles/hash, 0.23 bytes/cycle
> Small key speed test - 14-byte keys - 57.18 cycles/hash, 0.24 bytes/cycle
> Small key speed test - 15-byte keys - 56.81 cycles/hash, 0.26 bytes/cycle
> Small key speed test - 16-byte keys - 56.33 cycles/hash, 0.28 bytes/cycle
>
> Small key speed test - 16-byte keys - 56.43 cycles/hash, 0.28 bytes/cycle
> Small key speed test - 32-byte keys - 84.35 cycles/hash, 0.38 bytes/cycle
> Small key speed test - 48-byte keys - 86.97 cycles/hash, 0.55 bytes/cycle
> Small key speed test - 64-byte keys - 93.17 cycles/hash, 0.69 bytes/cycle
> Small key speed test - 80-byte keys - 95.33 cycles/hash, 0.84 bytes/cycle
> Small key speed test - 96-byte keys - 106.40 cycles/hash, 0.90 bytes/cycle
> Small key speed test - 112-byte keys - 118.32 cycles/hash, 0.95 bytes/cycle
> Small key speed test - 128-byte keys - 95.01 cycles/hash, 1.35 bytes/cycle
>
> Small key speed test - 128-byte keys - 95.09 cycles/hash, 1.35 bytes/cycle
> Small key speed test - 256-byte keys - 129.42 cycles/hash, 1.98 bytes/cycle
> Small key speed test - 384-byte keys - 205.25 cycles/hash, 1.87 bytes/cycle
> Small key speed test - 512-byte keys - 249.53 cycles/hash, 2.05 bytes/cycle
> Small key speed test - 640-byte keys - 279.62 cycles/hash, 2.29 bytes/cycle
> Small key speed test - 768-byte keys - 313.20 cycles/hash, 2.45 bytes/cycle
> Small key speed test - 896-byte keys - 349.60 cycles/hash, 2.56 bytes/cycle
> Small key speed test - 1024-byte keys - 376.69 cycles/hash, 2.72 bytes/cycle
>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
More information about the cfe-dev
mailing list