Awesome

<a id="top"></a>

Better Faster Stronger Mixer

• Mixing Speed
• Mixing Quality
• Results
• Mixers: FNV1A_Pippip, aes2, aes3, crc_mul, ettinger_mixer1, ettinger_mixer2, fnv1a_64, lemire_stronglyuniversal, mum3_mixer, mumxmumxx1, mumxmumxx2, mumxmumxx3, murmurhash3_fmix64, robin_hood_hash_int, rrmxmx, rrxmrrxmsx_0, staffort_mix13, twang_mix64, wyhash3_mix, xxh3_mixer

Testing framework for the quest to find a fast & strong mixer, e. g. for hashtables. Many modern hashtables like robin_hood::unordered_map or Abseil's hash tables require high quality hashing for their tables to work efficiently.

Mixing Speed

Generated with nanobench, g++ 9.2, -O3 -march=native, on an Intel i7-8700 CPU locked to 3.20GHz

Mixing Quality

The testing protocol is taken from by Pelle Evensen's blog post Better, stronger mixer and a test procedure:

Successive increasing numbers, which are rotated right, then optionally bitorder is reversed, are fed into a mixer. The mixer's output is fed into PractRand, which analyzes the quality of the generated number. So basically, the algorithm is this:

// e.g. for rotation 37, and enabled bitreverse:
int rotation = 37;
uint64_t ctr = 0;
while (true) {
    feedPractRand(mixer(bitreverse64(rotr(ctr, rotation))));
    ++ctr;
}

In my tests, I run PractRand 0.95 with the arguments RNG_test stdin64 -tf 2 -tlmin 10 -tlmax 40. The test aborts when it detects a failure in the quality of the mixer results.

Ideally, a mixer doesn't fail the practrand test and is as fast as possible. In the following plot I show the results of the mixers that I have already evaluated. Pareto optimums are green (I consider 2^10 still a failure).

Results

An ideal mixer should be in the upper right corner. The pareto front is colored green (except anything that already fails on tlmax=10. I consider these mixers as too bad for practical use).

FNV1A_Pippip

identity, rotation 0 - 63

min: 2^10, max: 2^10, mean: 2^10.0

identity, rotation 0 - 63

aes2

identity, rotation 0 - 63

min: 2^13, max: 2^16, mean: 2^14.7

identity, rotation 0 - 63

min: 2^13, max: 2^16, mean: 2^14.7

aes3

TODO only tested up to -tlmax 20

identity, rotation 0 - 63

min: 2^19, max: 2^20, mean: 2^20.0

identity, rotation 0 - 63

min: 2^19, max: 2^20, mean: 2^20.0

crc_mul

identity, rotation 0 - 63

min: 2^13, max: 2^14, mean: 2^13.1

identity, rotation 0 - 63

min: 2^13, max: 2^14, mean: 2^13.1

ettinger_mixer1

TODO

ettinger_mixer2

TODO

fnv1a_64

identity, rotation 0 - 63

min: 2^10, max: 2^13, mean: 2^11.6

identity, rotation 0 - 63

min: 2^10, max: 2^14, mean: 2^11.5

lemire_stronglyuniversal

identity, rotation 0 - 63

min: 2^10, max: 2^13, mean: 2^12.2

identity, rotation 0 - 63

min: 2^10, max: 2^14, mean: 2^12.8

mum3_mixer

identity, rotation 0 - 63

min: 2^16, max: 2^17, mean: 2^16.7

identity, rotation 0 - 63

min: 2^16, max: 2^17, mean: 2^16.6

mumxmumxx1

identity, rotation 0 - 63

min: 2^30, max: 2^40, mean: 2^37.2

identity, rotation 0 - 63

min: 2^28, max: 2^40, mean: 2^37.3

mumxmumxx2

identity, rotation 0 - 63

min: 2^40, max: 2^40, mean: 2^40.0

identity, rotation 0 - 63

min: 2^40, max: 2^40, mean: 2^40.0

mumxmumxx3

TODO

murmurhash3_fmix64

identity, rotation 0 - 63

min: 2^14, max: 2^18, mean: 2^15.4

identity, rotation 0 - 63

min: 2^14, max: 2^19, mean: 2^16.5

robin_hood_hash_int

identity, rotation 0 - 63

min: 2^10, max: 2^13, mean: 2^12.1

identity, rotation 0 - 63

min: 2^12, max: 2^15, mean: 2^13.0

rrmxmx

TODO

rrxmrrxmsx_0

TODO

staffort_mix13

identity, rotation 0 - 63

min: 2^16, max: 2^20, mean: 2^17.8

identity, rotation 0 - 63

min: 2^16, max: 2^22, mean: 2^19.4

twang_mix64

identity, rotation 0 - 63

min: 2^13, max: 2^21, mean: 2^16.6

identity, rotation 0 - 63

min: 2^13, max: 2^22, mean: 2^16.8

wyhash3_mix

identity, rotation 0 - 63

min: 2^40, max: 2^40, mean: 2^40.0

identity, rotation 0 - 63

min: 2^40, max: 2^40, mean: 2^40.0

xxh3_mixer

identity, rotation 0 - 63

min: 2^15, max: 2^29, mean: 2^21.6

identity, rotation 0 - 63

min: 2^15, max: 2^27, mean: 2^20.4