Hashing functions and PRNGs based on them
MUM_V1
before compiling mum.h
MUM_V1
is defined, you will get the same hashes as previouslymum_hash_step
) is used for hashing big data structures-O3
was used for all compilationsrand
calls-flto
for benchmarking all hash
functions excluding MUM. This option makes cross-file inliningSpooky | City | xxHash | SipHash24 | Metro | MeowHash | MUM-V1 | MUM-V2 | MUM-V3 | |
---|---|---|---|---|---|---|---|---|---|
5-byte | 6.62s | 8.78s | 6.80s | 10.07s | 5.76s | 11.25s | 6.57s | 5.56s | 4.85s |
8-byte | 6.30s | 8.81s | 6.54s | 12.89s | 4.18s | 11.25s | 4.74s | 3.69s | 2.88s |
16-byte | 12.64s | 8.20s | 8.11s | 16.13s | 5.71s | 9.42s | 5.85s | 4.75s | 3.95s |
32-byte | 13.20s | 9.60s | 11.60s | 22.40s | 11.72s | 9.42s | 6.83s | 5.52s | 4.71s |
64-byte | 19.40s | 10.60s | 12.86s | 36.70s | 12.53s | 9.42s | 9.35s | 8.79s | 6.54s |
128-byte | 32.58s | 14.25s | 15.49s | 63.82s | 14.63s | 10.46s | 13.64s | 13.01s | 11.53s |
Bulk | 9.74s | 9.17s | 9.59s | 48.63s | 8.89s | 4.65s | 10.33s | 10.38s | 7.93s |
Spooky | City64 | xxHash64 | SipHash24 | Metro64 | MUM-V1 | MUM-V2 | MUM-V3 | |
---|---|---|---|---|---|---|---|---|
5 bytes | 10.10s | 12.97s | 10.51s | 22.22s | 9.93s | 11.19s | 9.19s | 7.95s |
8 bytes | 9.10s | 13.32s | 9.64s | 30.95s | 6.33s | 8.43s | 6.43s | 5.23s |
16 bytes | 19.00s | 12.83s | 14.84s | 36.67s | 8.45s | 11.07s | 9.04s | 7.80s |
32 bytes | 19.04s | 14.94s | 17.56s | 49.97s | 29.71s | 12.05s | 10.05s | 8.83s |
64 bytes | 29.23s | 15.58s | 23.22s | 73.63s | 33.45s | 13.65s | 11.87s | 10.49s |
128 bytes | 49.57s | 23.38s | 28.88s | 123.77s | 40.33s | 17.60s | 15.60s | 14.46s |
16MB | 13.58s | 11.36s | 11.90s | 98.20s | 13.83s | 10.85s | 10.89s | 6.52s |
Spooky | City64 | xxHash64 | SipHash24 | Metro64 | MUM-V1 | MUM-V2 | MUM-V3 | |
---|---|---|---|---|---|---|---|---|
5 bytes | 22.14s | 23.87s | 20.54s | 45.06s | 18.01s | 18.44s | 18.29s | 17.29s |
8 bytes | 17.62s | 23.68s | 19.92s | 54.13s | 9.82s | 9.18s | 7.55s | 6.00s |
16 bytes | 34.02s | 18.60s | 23.62s | 61.19s | 15.75s | 17.32s | 17.47s | 16.46s |
32 bytes | 32.16s | 21.66s | 34.73s | 75.72s | 27.82s | 18.72s | 18.87s | 17.93s |
64 bytes | 53.53s | 23.40s | 37.97s | 104.23s | 29.88s | 21.34s | 20.42s | 20.29s |
128 bytes | 87.46s | 33.17s | 44.60s | 193.19s | 38.73s | 32.96s | 30.90s | 27.47s |
16MB | 17.12s | 13.64s | 14.56s | 116.85s | 12.22s | 11.59s | 11.56s | 10.69s |
Spooky | City64 | xxHash64 | SipHash24 | Metro64 | MUM-V1 | MUM-V2 | MUM-V3 | |
---|---|---|---|---|---|---|---|---|
5 bytes | 18.13s | 25.60s | 22.40s | 27.73s | 18.67s | 20.79s | 16.00s | 17.07s |
8 bytes | 17.60s | 25.60s | 21.33s | 35.73s | 13.33s | 14.39s | 11.20s | 9.06s |
16 bytes | 30.93s | 25.07s | 26.13s | 45.33s | 17.07s | 21.33s | 15.99s | 19.73s |
32 bytes | 30.94s | 29.33s | 36.27s | 62.94s | 36.27s | 28.26s | 24.00s | 28.27s |
64 bytes | 44.80s | 30.40s | 40.54s | 101.87s | 38.40s | 41.60s | 37.34s | 41.07s |
128 bytes | 73.07s | 45.34s | 49.07s | 195.75s | 43.74s | 69.34s | 64.54s | 67.74s |
16MB | 40.01s | 45.82s | 53.24s | 188.42s | 53.25s | 48.48s | 48.48s | 33.90s |
_mum_hash_aligned
can be vectorized
using vector multiplication, addition, xor, and shuffle instructions64 x 64-bit -> 128-bit
(pclmulqdq
only 1 64x64->128-bit
multiplication)32 x 32-bit -> 64-bit
MULQ/MULX
insns does64 x 64-bit -> 128-bit
multiplication, potentially it could increase MUM speed up to 2
times (may be less as major memory speed access becomes a major bottleneck of the overall hash speed)lo(x*C) + hi(x*C)
where C is a constant. Brute force
solution of equation f(x) = a
probably requires 2^63
tries.
Another used function equation x ^ y = a
has a 2^64
solutions. It complicates finding the overal solution furthermum_hash_randomize
).
Finding a string with a given hash even if you know a string with such
hash probably will be close to finding two or more solutions of
Diophantine equationsmum.h
into your C/C++ program and use the following functions:
mum_hash_randomize
for choosing multiplication constants randomlymum_hash_init
, mum_hash_step
, and mum_hash_finish
for hashing complex data structuresmum_hash64
for hashing a 64-bit datamum_hash
for hashing any continuous block of datasrc
and run a scriptsh bench
MUM_TARGET_INDEPENDENT_HASH
src
and run a script sh bench-crypto
MUM512 | SHA2 | SHA3 | Blake2B | |
---|---|---|---|---|
10 bytes (20 M texts) | 0.57s | 0.53s | 0.87s | 0.68s |
100 bytes (20 M texts) | 0.77s | 0.51s | 1.68s | 0.68s |
1000 bytes (20 M texts) | 2.75s | 3.79s | 11.58s | 2.85s |
10000 bytes (5 M texts) | 5.60s | 9.21s | 28.37s | 6.23s |
mum-prng.h
and mum512-prng.h
provides pseudo-random
functions based on MUM and MUM512 hash functionssrc
and run a script sh bench-prng
bbs-prng.h
) and PRNGs based on fast cryto-level hash
functions in ChaCha stream cipher (file chacha-prng.h
) and
SipHash24 (file sip24-prng.h
).
MULX
instructionXOSHIRO512**
performance result (it was 1944 M prns/sec). So I fixed it.
It is actually 1044.M prns/sec | |
---|---|
BBS | 0.078 |
ChaCha | 199 |
SipHash24 | 413 |
MUM512 | 83 |
MUM | 1317 |
XOSHIRO128** | 1130 |
XOSHIRO256** | 1337 |
XOSHIRO512** | 1044 |
GLIBC RAND | 193 |
XOROSHIRO128+ | 1342 |
XOSHIRO256+ | 1339 |
XOSHIRO512+ | 1253 |
M prns/sec | |
---|---|
BBS | - |
ChaCha | 191.33 |
Sip24 | 402.48 |
MUM512 | 152.27 |
MUM | 1414.57 |
XOROSHIRO128** | 482.91 |
XOSHIRO256** | 732.24 |
XOSHIRO512** | 689.60 |
RAND | 180.02 |
XOROSHIRO128+ | 621.52 |
XOSHIRO256+ | 954.42 |
XOSHIRO512+ | 890.81 |