[cfe-dev] RFC: change string hash function in libc++
Craig Silverstein
csilvers at google.com
Fri Dec 2 17:59:37 PST 2011
Here are the updated results, including City64, which is probably a
better candidate here than City128. The data is a little noisy, but
it looks like City64 is faster than Murmur3F starting at
around 8-byte strings.
Answering another question, Austin said all tests were performed on an
x86_64 machine with gcc 4.6.x, with code compiled via gcc -O2.
Results can differ on different platforms/compilers/etc, making the
choice of a 'best' hash function difficult. Overall, I think either
cityhash or murmurhash would be great choices, and better than what
exists in libc++ now. I don't want to get too bogged down in choosing
between them.
craig
-------------------------------------------------------------------------------
--- 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 City64
[[[ Sanity Tests ]]]
Verification value 0x45754A6F : Passed!
Running sanity check 1..........PASS
Running sanity check 2..........PASS
[[[ Speed Tests ]]]
Bulk speed test - 262144-byte keys
Alignment 0 - 3.589 bytes/cycle - 10267.63 MiB/sec @ 3 ghz
Alignment 1 - 3.565 bytes/cycle - 10199.30 MiB/sec @ 3 ghz
Alignment 2 - 3.565 bytes/cycle - 10199.91 MiB/sec @ 3 ghz
Alignment 3 - 3.565 bytes/cycle - 10199.65 MiB/sec @ 3 ghz
Alignment 4 - 3.565 bytes/cycle - 10198.61 MiB/sec @ 3 ghz
Alignment 5 - 3.565 bytes/cycle - 10199.72 MiB/sec @ 3 ghz
Alignment 6 - 3.565 bytes/cycle - 10199.38 MiB/sec @ 3 ghz
Alignment 7 - 3.565 bytes/cycle - 10199.23 MiB/sec @ 3 ghz
Small key speed test - 1-byte keys - 37.70 cycles/hash, 0.03 bytes/cycle
Small key speed test - 2-byte keys - 35.54 cycles/hash, 0.06 bytes/cycle
Small key speed test - 3-byte keys - 29.74 cycles/hash, 0.10 bytes/cycle
Small key speed test - 4-byte keys - 38.31 cycles/hash, 0.10 bytes/cycle
Small key speed test - 5-byte keys - 37.82 cycles/hash, 0.13 bytes/cycle
Small key speed test - 6-byte keys - 40.93 cycles/hash, 0.15 bytes/cycle
Small key speed test - 7-byte keys - 37.94 cycles/hash, 0.18 bytes/cycle
Small key speed test - 8-byte keys - 37.51 cycles/hash, 0.21 bytes/cycle
Small key speed test - 9-byte keys - 37.02 cycles/hash, 0.24 bytes/cycle
Small key speed test - 10-byte keys - 36.52 cycles/hash, 0.27 bytes/cycle
Small key speed test - 11-byte keys - 39.12 cycles/hash, 0.28 bytes/cycle
Small key speed test - 12-byte keys - 37.67 cycles/hash, 0.32 bytes/cycle
Small key speed test - 13-byte keys - 37.46 cycles/hash, 0.35 bytes/cycle
Small key speed test - 14-byte keys - 36.69 cycles/hash, 0.38 bytes/cycle
Small key speed test - 15-byte keys - 36.31 cycles/hash, 0.41 bytes/cycle
Small key speed test - 16-byte keys - 37.74 cycles/hash, 0.42 bytes/cycle
Small key speed test - 16-byte keys - 37.83 cycles/hash, 0.42 bytes/cycle
Small key speed test - 32-byte keys - 30.28 cycles/hash, 1.06 bytes/cycle
Small key speed test - 48-byte keys - 45.70 cycles/hash, 1.05 bytes/cycle
Small key speed test - 64-byte keys - 47.17 cycles/hash, 1.36 bytes/cycle
Small key speed test - 80-byte keys - 73.64 cycles/hash, 1.09 bytes/cycle
Small key speed test - 96-byte keys - 73.44 cycles/hash, 1.31 bytes/cycle
Small key speed test - 112-byte keys - 76.34 cycles/hash, 1.47 bytes/cycle
Small key speed test - 128-byte keys - 75.35 cycles/hash, 1.70 bytes/cycle
Small key speed test - 128-byte keys - 75.50 cycles/hash, 1.70 bytes/cycle
Small key speed test - 256-byte keys - 106.98 cycles/hash, 2.39 bytes/cycle
Small key speed test - 384-byte keys - 147.98 cycles/hash, 2.59 bytes/cycle
Small key speed test - 512-byte keys - 180.29 cycles/hash, 2.84 bytes/cycle
Small key speed test - 640-byte keys - 214.87 cycles/hash, 2.98 bytes/cycle
Small key speed test - 768-byte keys - 249.37 cycles/hash, 3.08 bytes/cycle
Small key speed test - 896-byte keys - 278.00 cycles/hash, 3.22 bytes/cycle
Small key speed test - 1024-byte keys - 314.24 cycles/hash, 3.26 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