SMhasher

Alternative timings with a modern AMD Ryzen 3 3200U 3.5GHz laptop:

Hash function MiB/sec cycl./hash cycl./map size Quality problems
donothing32 14837011.36 3.04 - 13 test NOP
donothing64 14852735.41 3.01 - 13 test NOP
donothing128 14818680.06 3.11 - 13 test NOP
NOP_OAAT_read64 55243.46 13.47 - 47 test NOP
BadHash 947.66 58.35 - 47 test FAIL
sumhash 13587.84 23.21 - 363 test FAIL
sumhash32 54652.07 19.31 - 863 UB, test FAIL
multiply_shift 10212.29 20.50 400.39 (2) 345 fails all tests
pair_multiply_shift 7198.28 31.72 416.92 (3) 609 fails all tests

crc32 472.15 107.09 458.47 (4) 422 insecure, 8590x collisions, distrib
md5_32 438.42 500.67 1003.44 (27) 4419
md5_64 438.42 500.67 1003.44 (27) 4419
md5-128 437.75 502.84 1014.29 (34) 4419
sha1_32a 717.81 602.63 1136.55 (15) 5126 Sanity, collisions, 36.6% distrib
sha1-160 718.61 656.78 1172.92 (18) 5126 Comb/Cyclic low3
sha2-224 281.41 724.75 - Cyclic low32
sha2-224_64 281.66 730.82 1260.31 (22) Cyclic low32
sha2-256 280.13 731.39 1227.49 (4)
sha2-256_64 279.46 723.37 1261.39 (33)
sha1ni 1999.23 147.52 637.57 (1) 989 insecure,sanity, Permutation, Zeroes, amd epyc only
sha1ni_32 2019.94 146.68 651.32 (2) 989 insecure,sanity, Permutation, Zeroes, TwoBytes, amd epyc only
sha2ni-256 1910.30 147.89 628.97 (3) 4241 insecure,sanity, Permutation, Zeroes, amd epyc only
sha2ni-256_64 1900.27 153.28 653.32 (4) 4241 insecure,sanity, Permutation, Zeroes, TwoBytes, amd epyc only
blake3_c 1585.56 313.11 817.64 (2) no 32bit portability
rmd128 364.75 559.55 1077.37 (5)
rmd160 233.83 853.42 1357.66 (33)
rmd256 458.90 475.70 979.52 (13)
blake2s-128 409.80 542.11 1011.59 (5)
blake2s-160 407.43 558.79 1025.51 (29)
blake2s-224 407.11 559.17 1033.87 (9)
blake2s-256 406.97 550.43 1026.33 (4)
blake2s-256_64 406.98 551.79 1030.91 (9)
blake2b-160 681.42 667.62 1136.08 (14)
blake2b-224 683.20 666.89 1134.97 (9)
blake2b-256 687.59 650.79 1135.68 (14) Sparse high 32-bit
blake2b-256_64 692.34 649.74 1142.25 (26)
asconhashv12 144.98 885.02 1324.23 (38) 6490
asconhashv12_64 145.12 413.31 870.35 (14) 4341
sha3-256 154.58 2572.11 3105.41 (89) PerlinNoise
sha3-256_64 152.10 2720.95 3045.20 (10) PerlinNoise
hasshe2 3474.57 51.57 490.47 (1) 445 Permutation,TwoBytes,Zeroes,Seed
poly_1_mersenne 1706.60 49.12 456.82 (2) 479 fails most tests
poly_2_mersenne 1654.09 56.01 458.97 (1) 479
poly_3_mersenne 1672.92 63.37 466.00 (1) 479
poly_4_mersenne 1683.02 70.46 474.19 (1) 479
tabulation32 7159.13 29.98 454.42 (1) 848 collisions
tabulation 9961.51 31.60 430.00 (1) 554
crc32_hw 7664.42 33.39 446.57 (1) 653 insecure, 100% bias, collisions, distrib, machine-specific (x86 SSE4.2)
crc32_hw1 9303.14 39.59 451.97 (1) 671 insecure, 100% bias, collisions, distrib, machine-specific (x86 SSE4.2)
crc64_hw 7663.00 32.36 291.96 (1) 652 insecure, 100% bias, collisions, distrib, machine-specific (x64 SSE4.2)
crc32_pclmul 1810479.66 6.01 - 481 insecure, 100% bias, collisions, distrib, machine-specific (x86 PCLMUL)
o1hash 14677437.55 14.26 368.10 (1) 101 insecure, zeros, fails all tests
fibonacci 21517.13 19.66 745.72 (2) 1692 UB, zeros, fails all tests
FNV1a 952.70 58.22 450.91 (3) 204 zeros, fails all tests
FNV1A_Totenschiff 7698.74 21.57 463.21 (1) 270 UB, zeros, fails all tests
FNV1A_Pippip_Yurii 7699.24 22.12 461.30 (1) 147 UB, sanity, fails all tests
FNV1a_YT 17165.60 24.05 445.28 (1) 321 UB, fails all tests
FNV2 7699.02 25.97 327.85 (1) 278 fails all tests
FNV64 952.95 58.03 386.24 (1) 79 fails all tests
k-hash32 2686.33 42.99 504.48 (17) 808 UB, insecure, zeros, fails all tests
k-hash64 2808.54 39.19 434.43 (15) 609 UB, insecure, zeros, fails all tests
fletcher2 19125.61 18.51 719.51 (8) 248 UB, fails all tests
fletcher4 19125.27 18.51 713.87 (1) 371 UB, fails all tests
bernstein 1283.71 45.58 450.95 (1) 41 fails all tests
sdbm 950.73 55.98 446.51 (1) 41 fails all tests
x17 951.15 58.33 452.67 (2) 79 99.98% bias, fails all tests
libiberty 556.16 87.56 273.09 (15) 37 insecure, 100% bias, fails all tests
gcc 619.25 85.10 245.78 (17) 39 insecure, 100% bias, fails all tests
JenkinsOOAT 755.98 87.15 473.89 (3) 153 53.5% bias, fails all tests
JenkinsOOAT_perl 755.50 74.22 463.33 (1) 65 1.5-11.5% bias, 7.2x collisions, LongNeighbors
MicroOAAT 904.82 60.38 454.68 (2) 68 100% bias, distrib
VHASH_32 16599.04 51.55 507.93 (1) 1231 sanity, Seed, MomentChi2
VHASH_64 16615.13 51.57 499.80 (1) 1231 sanity, Seed, Sparse
farsh32 14053.09 74.29 245.33 (3) 944 insecure: AppendedZeroes, collisions+bias, MomentChi2, LongNeighbors
farsh64 7216.29 130.30 302.44 (3) 944 insecure: AppendedZeroes, collisions+bias, MomentChi2, LongNeighbors
farsh128 8143.20 185.68 616.21 (14) ??
farsh236 ??
jodyhash32 2139.68 33.76 534.29 (18) 102 bias, collisions, distr, LongNeighbors
jodyhash64 5638.08 21.85 523.35 (29) 118 bias, collisions, distr, LongNeighbors
lookup3 3064.08 31.84 453.97 (1) 341 UB, 28% bias, collisions, 30% distr
superfast 2956.46 37.53 450.84 (2) 210 UB, 91% bias, 5273.01x collisions, 37% distr, BIC
MurmurOAAT 629.62 81.58 458.49 (3) 47 collisions, 99.998% distr., BIC, LongNeighbors
Crap8 3850.23 29.21 466.24 (3) 342 UB, 2.42% bias, collisions, 2% distrib
Murmur1 2567.1 38.29 459.59 (12) UB, fails all tests, 1 bad seed
Murmur2 3850.07 32.92 449.17 (2) 358 UB, 1.7% bias, 81x coll, 1.7% distrib, BIC
Murmur2A 3850.06 36.71 452.21 (3) 407 UB, 12.7% bias, LongNeighbors
Murmur2B 7697.11 30.54 370.23 (1) 433 UB, 1.8% bias, collisions, 3.4% distrib, BIC
Murmur2C 4789.81 38.75 398.96 (1) 444 UB, 91% bias, collisions, distr, BIC, LongNeighbors
Murmur3A 3764.82 38.64 455.28 (5) 351 UB, Moment Chi2 69
PMurHash32 3782.23 39.05 452.79 (2) 1862 Moment Chi2 69
Murmur3C 6075.28 44.57 468.10 (5) 859 UB, LongNeighbors, DiffDist
PMPML_32 8392.12 36.03 452.05 (2) 1084 Avalanche >512, unseeded: Seed, MomentChi2
PMPML_64 12576.64 39.15 425.25 (4) 1305 unseeded: Seed, MomentChi2
xxHash32 7411.65 39.03 448.37 (1) 738 LongNeighbors, collisions with 4bit diff, MomentChi2 220
metrohash64_1 19594.03 32.12 392.76 (1) 624 UB, LongNeighbors, BIC, MomentChi2
metrohash64_2 19592.68 32.02 395.69 (1) 627 UB, LongNeighbors
metrohash64crc_1 9987.10 35.19 380.91 (3) 632 UB, cyclic collisions 8 byte, BIC, MomentChi2, machine-specific (x64 SSE4.2)
metrohash64crc_2 9992.76 35.23 393.92 (1) 632 UB, cyclic collisions 8 byte, BIC, machine-specific (x64 SSE4.2)
metrohash128_1 20070.86 58.67 468.55 (4) 773 UB, LongNeighbors
metrohash128_2 20071.20 58.67 465.88 (2) 773 UB, LongNeighbors
cmetrohash64_1o 19718.36 31.65 362.88 (1) 3506 LongNeighbors, MomentChi2
cmetrohash64_1 19576.09 32.12 396.59 (1) 652 LongNeighbors, BIC, MomentChi2
cmetrohash64_2 19516.27 31.98 392.18 (4) 655 LongNeighbors
City64noSeed 17835.31 25.51 415.24 (1) 1038 Avalanche, Sparse, TwoBytes, MomentChi2, Seed
City64 17876.12 36.82 456.39 (3) 1120 Sparse, TwoBytes
t1ha1_64le 17176.31 25.19 452.18 (3) 517 Avalanche
t1ha1_64be 14653.85 25.84 458.75 (4) 555 Avalanche
t1ha0_32le 9196.24 39.22 451.00 (1) 509 Sparse, LongNeighbors
t1ha0_32be 8482.65 39.97 455.29 (6) 533 Sparse, LongNeighbors
t1ha2_stream 17418.77 64.63 500.29 (130) 1665 Sparse, Permutation, LongNeighbors
t1ha2_stream128 17412.54 76.63 511.85 (2) 1665 Sparse, Permutation, LongNeighbors
aesnihash 6633.37 44.76 657.74 (49) 1209 fails many tests, machine-specific (x64 AES-NI)
falkhash 63972.28 97.43 540.55 (2) 264 Sparse, LongNeighbors, machine-specific (x64 AES-NI)
MeowHash 33443.50 52.04 496.22 (2) 1764 Sparse, machine-specific (x64 AES-NI)
MeowHash64low 33479.49 52.02 493.90 (4) 1764 Sparse, machine-specific (x64 AES-NI)
MeowHash32low 35248.53 52.30 503.57 (2) 1764 Sparse, machine-specific (x64 AES-NI)
tifuhash_64 195.51 401.07 786.93 (6) 276
beamsplitter 779.07 680.13 1130.13 (14) UB
floppsyhash 190.37 458.85 842.41 (3) 623
chaskey 1432.61 101.09 541.03 (2) 1609 PerlinNoise
SipHash 1167.86 110.10 495.75 (1) 1071
HalfSipHash 1376.89 65.27 479.68 (1) 700 zeroes
GoodOAAT 922.03 68.14 461.18 (1) 237
pearsonbhash64 2951.62 222.03 343.63 (4) 683
pearsonbhash128 2951.62 222.03 343.63 (4) 1134
pearsonbhash256 2951.62 222.03 343.63 (4) 844
prvhash64_64m 3838.73 38.31 471.23 (23) 349
prvhash64_64 3720.87 39.07 479.33 (120) 384
prvhash64_128 3986.91 70.61 605.25 (86) 718
prvhash64s_64 7249.18 240.06 774.15 (19) 2640
prvhash64s_128 7002.12 289.49 - 2799
SipHash13 2261.48 76.97 467.06 (1) 778 0.9% bias
discohash1 4923.07 163.05 - 1294
discohash1-128 4967.81 188.54 701.67 (2) 1294
discohash2 5007.35 164.10 712.79 (10) 1294
discohash2-128 4966.56 188.85 689.98 (1) 1294
discoNONG 4437.01 326.97 840.01 (2) bad seeds
pearsonhash64 2951.62 222.03 343.63 (4) Avalanche, Seed, SSSE3 only. broken MSVC
pearsonhash128 2951.62 222.03 343.63 (4) Avalanche, Seed, SSSE3 only. broken MSVC
pearsonhash256 2951.62 222.03 343.63 (4) Avalanche, Seed, SSSE3 only. broken MSVC
TSip 5371.30 41.88 474.18 (2) 519 !msvc
aesni 32360.68 25.66 629.14 (50) 519 machine-specific (x64 AES-NI)
aesni-low 34262.67 25.92 642.08 (68) 519 machine-specific (x64 AES-NI)
seahash 10048.09 45.22 476.88 (5) 871 PerlinNoise, !msvc
seahash32low 10021.55 45.22 487.35 (1) 871 PerlinNoise, !msvc
clhash 23095.27 52.83 491.27 (4) 1809 PerlinNoise, machine-specific (x64 SSE4.2)
HighwayHash64 10293.59 84.62 530.66 (3) 2546
Murmur3F 9666.27 38.31 436.97 (2) 699 UB
fasthash32 7697.65 31.94 453.42 (2) 566 UB
fasthash64 7698.26 30.37 408.88 (4) 509 UB, Moment Chi2 5159 !
MUM 12228.56 28.52 434.85 (1) 1912 UB, too many bad seeds, machine-specific (32/64 differs)
MUMlow 12100.34 28.36 458.00 (3) 1912 UB, 5 bad seeds
xmsx32 2039.10 46.39 249.30 (7) 192 2 bad seeds
mirhash 8197.76 30.26 402.05 (1) 1112 2^36 bad seeds, UB, LongNeighbors, machine-specific (32/64 differs)
mirhash32low 8229.50 30.25 452.15 (1) 1112 4 bad seeds, UB, Cyclic, LongNeighbors, machine-specific (32/64 differs)
mirhashstrict 4737.68 39.95 430.11 (1) 1112
mirhashstrict32low 4737.63 39.87 456.85 (5) 1112 1 bad seed, MomentChi2 9
mx3 11391.98 38.88 420.45 (1) 734 UB
pengyhash 16544.54 58.81 491.94 (1) 421
City32 6876.89 42.68 473.56 (5) 1319
City64low 17961.33 36.73 481.23 (3) 1120
City128 17422.69 69.62 506.56 (2) 1841
CityCrc128 9915.82 55.41 488.65 (1) 295
FarmHash32 27580.96 37.26 481.39 (2) 11489 machine-specific (x64 SSE4/AVX)
FarmHash64 18098.22 37.42 461.90 (2) 3758
FarmHash128 17481.30 55.16 483.56 (2) 163
farmhash32_c 27566.57 37.21 480.67 (2) 762 machine-specific (x64 SSE4/AVX)
farmhash64_c 18087.55 38.45 455.54 (1) 3688
farmhash128_c 17261.07 54.93 485.75 (2) 1890
metrohash64 19434.43 32.02 392.25 (4) 624 LongNeighbors
metrohash128 19203.11 58.53 467.74 (3) 624 UB
metrohash128crc_1 9990.25 63.30 470.07 (2) 723 UB, machine-specific (x64 SSE4.2)
metrohash128crc_2 9999.69 63.31 470.33 (4) 723 UB, machine-specific (x64 SSE4.2)
xxHash64 15340.14 39.33 409.54 (1) 1999
Spooky32 16521.68 62.11 463.49 (2) 2221 UB
Spooky64 16555.70 61.79 440.94 (4) 2221 UB
Spooky128 16565.11 63.45 441.99 (5) 2221 UB
SpookyV2_32 16816.08 45.12 472.80 (19) 2069
SpookyV2_64 16879.61 45.18 490.62 (35) 2069
SpookyV2_128 16326.13 48.59 486.83 (124) 2069
t1ha2_atonce 17705.49 30.49 448.85 (1) 541
t1ha2_atonce128 17636.67 42.52 476.14 (1) 613 LongNeighbors
t1ha0_aes_noavx 34530.80 29.34 443.11 (7) 925 LongNeighbors, machine-specific (x86 AES-NI)
t1ha0_aes_avx1 34532.21 29.34 438.07 (1) 843 LongNeighbors, machine-specific (x64 AVX)
t1ha0_aes_avx2 69583.42 29.34 440.99 (2) 792 LongNeighbors, machine-specific (x64 AVX2)
ahash64 14705.55 23.34 458.05 (14) 412 rust
xxh3 25867.89 23.60 433.96 (2) 744 Moment Chi2 14974, BIC
xxh3low 25877.21 23.58 467.69 (2) 756 Moment Chi2 1.8e+9 !
xxh128 23950.99 26.60 457.73 (2) 1012 Moment Chi2 14974
xxh128low 23935.79 26.93 459.01 (2) 1012 Moment Chi2 14974, BIC
MeowHash 33443.50 52.04 496.22 (2) 1764 Sparse low32, machine-specific (x64 AES-NI)
MeowHash32low 35248.53 52.30 503.57 (2) 1764 Sparse, machine-specific (x64 AES-NI)
wyhash 27093.03 22.05 428.98 (1) 474
wyhash32 2532.89 37.95 222.17 (4) 426 4 bad and broken seeds, 32-bit
wyhash32low 26979.48 22.32 466.74 (5) 474 5 bad seeds
umash32 19106.63 46.69 473.08 (4) 1530
umash32_hi 28063.01 33.41 474.46 (7) 1530
umash64 19055.83 42.97 560.92 (138) 1530
umash128 11243.58 37.45 469.42 (9) 1530
halftime_hash64 7320.03 91.23 598.61 (22) 1530
halftime_hash128 21097.01 73.68 587.12 (21) 1530
halftime_hash256 21188.10 79.11 579.31 (15) 1530
halftime_hash512 12815.44 92.22 595.51 (25) 1530
nmhash32 15739.53 45.37 468.34 (5) 2445
nmhash32x 15983.31 34.12 456.67 (3) 1494
k-hashv32 11312.23 43.05 519.40 (10) 1280
k-hashv64 11309.15 42.69 515.67 (19) 1279
komihash 12341.32 33.90 249.42 (15) 728
Other timings:

Summary

I added some SSE assisted hashes and fast intel/arm CRC32-C and AES HW variants, but not the fastest crcutil yet. See our crcutil results. See also the old https://code.google.com/p/smhasher/w/list.

So the fastest hash functions on x86_64 without quality problems are:

Hash functions for symbol tables or hash tables typically use 32 bit hashes, for databases, file systems and file checksums typically 64 or 128bit, for crypto now starting with 256 bit.

Typical median key size in perl5 is 20, the most common 4. Similar for all other dynamic languages. See github.com/rurban/perl-hash-stats

When used in a hash table the instruction cache will usually beat the CPU and throughput measured here. In my tests the smallest FNV1A beats the fastest crc32_hw1 with Perl 5 hash tables. Even if those worse hash functions will lead to more collisions, the overall speed advantage and inline-ability beats the slightly worse quality. See e.g. A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing for a concise overview of the best hash table strategies, confirming that the simplest Mult hashing (bernstein, FNV*, x17, sdbm) always beat "better" hash functions (Tabulation, Murmur, Farm, ...) when used in a hash table.

The fast hash functions tested here are recommendable as fast for file digests and maybe bigger databases, but not for 32bit hash tables. The "Quality problems" lead to less uniform distribution, i.e. more collisions and worse performance, but are rarely related to real security attacks, just the 2nd sanity zeroes test against \0 invariance is security relevant.

Columns

MiB/sec: The average of the Bulk key speed test for alignments 0-7 with 262144-byte keys. The higher the better.

cycl./hash: The average of the Small key speed test for 1-31 byte keys. The smaller the better.

cycl./map: The result of the Hashmap test for /usr/dict/words with std::unordered_map get queries, with the standard deviation in brackets. This tests the inlinability of the hash function (see size). The smaller the better.

size: The object size in byte on AMD64. This affects the inlinability in e.g. hash tables. The smaller the better.

Quality problems: See the failures in the linked doc. The less the better.

Other

SECURITY

The hash table attacks described in SipHash against City, Murmur or Perl JenkinsOAAT or at Hash Function Lounge are not included here.

Such an attack avoidance cannot be the problem of the hash function, but only the hash table collision resolution scheme. You can attack every single hash function, even the best and most secure if you detect the seed, e.g. from language (mis-)features, side-channel attacks, collision timings and independly the sort-order, so you need to protect your collision handling scheme from the worst-case O(n), i.e. separate chaining with linked lists. Linked lists chaining allows high load factors, but is very cache-unfriendly. The only recommendable linked list scheme is inlining the key or hash into the array. Nowadays everybody uses fast open addressing, even if the load factor needs to be ~50%, unless you use Cuckoo Hashing.

I.e. the usage of SipHash for their hash table in Python 3.4, ruby, rust, systemd, OpenDNS, Haskell and OpenBSD is pure security theatre. SipHash is not secure enough for security purposes and not fast enough for general usage. Brute-force generation of ~32k collisions need 2-4m for all these hashes. siphash being the slowest needs max 4m, other typically max 2m30s, with <10s for practical 16k collision attacks with all hash functions. Using Murmur is usually slower than a simple Mult, even in the worst case. Provable secure is only uniform hashing, i.e. 2-5 independent Mult or Tabulation, or using a guaranteed logarithmic collision scheme (a tree) or a linear collision scheme, such as Robin Hood or Cockoo hashing with collision counting.

One more note regarding security: Nowadays even SHA1 can be solved in a solver, like Z3 (or faster ones) for practical hash table collision attacks (i.e. 14-20 bits). All hash functions with less than 160 bits tested here cannot be considered "secure" at all.

The '' vulnerability attack with binary keys is tested in the 2nd Sanity Zero test.

CRYPTO

The official NIST hash function testsuite does not do such extensive statistical tests, to search for weak ranges in the bits. Also crypto does not change the initial state, which we do here for our random 32bit seed. Crypto mostly cares about unreversable key -> hash functions without changing the initial fixed state and timings/sidechannel attacks.

The NIST "Cryptographic Algorithm Validation Program" (CAVP) involves the testing of the implementations of FIPS-approved and NIST-recommended cryptographic algorithms. During the NIST SHA-3 competition, the testing methodology was borrowed from the "CAVP", as the KATs and MCTs of the SHA-3 Competition Test Suite were based on the CAVP tests for SHA-2. In addition to this, the “Extremely Long Message Test,” not present in the CAVP for SHA-2, required the submitters to generate the hash value corresponding to a message with a length of 1 GiB. “NIST - Cryptographic Algorithm Validation Program (CAVP),” June 2017. Available: http://csrc.nist.gov/groups/STM/cavp (No testing source code provided, just high-level descriptions)

Two other independent third party testsuites found an extensive number of bugs and weaknesses in the SHA3 candidates. "Finding Bugs in Cryptographic Hash Function Implementations", Nicky Mouha, Mohammad S Raunak, D. Richard Kuhn, and Raghu Kacker, 2017. https://eprint.iacr.org/2017/891.pdf

Maybe independent researchers should come together to do a better public SHA-4 round, based on better and more testing methods, open source code for the tests, and using standard industry practices, such as valgrind, address-sanitizer and ubsan to detect obvious bugs.

PROBLEMS

Typical undefined behaviour (UB) problems: