[cfe-dev] RFC: change string hash function in libc++
Craig Silverstein
csilvers at google.com
Fri Dec 2 15:52:34 PST 2011
} 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), 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
More information about the cfe-dev
mailing list