vnmakarov / mum-hash Goto Github PK

Though, this platforms are going to die, there is still wide adoption of.
So, it should be mention, which performance to expect from Mum, compared for other well performed 32bit hash functions.

https://github.com/vnmakarov/mum-hash/blob/master/mum.h#L312-L320

There is no any guarantee, than _mum_next_factor will return prime number.
Neither it is guaranteed to be odd (but it looks like algorithm doesn't depends on it).
If generator behind rand is a good random generator, then _mem_next_factor even
allowed to return zero.

Hi,

could you please benchmark against BLAKE2b and BLAKE2s if it's not too much hassle?
It tries to be a very fast cryptographically secure hash function. I believe it to be still ballpark 10x slower than MUM but it would be nice to know for sure! Of course it would also make sense to compare it with MUM512. Thanks in advance!

[1] https://blake2.net/

mum-prng passes NIST STS but that's not the state-of-the-art for PRNG testing.

Do you have info on the performance of mum-prng in TestU01 or PractRand? PractRand is probably the more convenient of the two.

linux kernel now use siphash_4u32 in net/ipv4/syncookies.c & net/ipv6/syncookies.c:
( https://github.com/torvalds/linux/tree/master )
static u32 cookie_hash(__be32 saddr, __be32 daddr, __be16 sport, __be16 dport,
u32 count, int c)
{
net_get_random_once(syncookie_secret, sizeof(syncookie_secret));
return siphash_4u32((__force u32)saddr, (__force u32)daddr,
(__force u32)sport << 16 | (__force u32)dport,
count, &syncookie_secret[c]);
}

siphash maybe too heavy or slow to generate tcp syncookie, just a message authentication code can do it, syncookie not need second pre-image resistance or collision resistance, pre-image resistance may be enough, how to prove mum-hash can do it?

This code in the inner loop of the hash assumes _mum_primes has an infinite number of elements and will produce non-deterministic output for any key longer than ((16 + _MUM_UNROLL_FACTOR) * sizeof(uint64_t) + 7)

for (i = 0; i < n; i++)
    result ^= _mum (_mum_le (((uint64_t *) str)[i]), _mum_primes[i]);

Modern Meow Hash (v0.4 and up) is actually faster than Mum on small inputs now in randomized testing. The version checked into this tree is a very old version and not representative of the current speed.

- Casey

I plugged in your v2 code into demerphq/smhasher and, unlike v1, it's failing most of its test suite. Have you tested it with that smhasher fork by any chance? It doesn't make sense to me that this would happen to the extent it is, so it may be something to do with the integration; I'll check that next unless you have an idea of what's going on.

Hello, I'd like to thank you for your hard work - I really like your algorithm.

However, I have a sort of question: I tried mum-hash to calculate shingles which implies a lot of hash calculations for individual words in some arbitrary text. It turns out, that mum-hash performs quite bad in these conditions: it is slower than xxhash64:

mum-hash:

(50000 words of 5 len, 0.02 perm factor): percentage of common shingles: 0.968, generate time: 0.0533 sec
(50000 words of 16 len, 0.02 perm factor): percentage of common shingles: 0.937, generate time: 0.0351 sec

xxhash64:

(50000 words of 5 len, 0.02 perm factor): percentage of common shingles: 0.781, generate time: 0.0330 sec
(50000 words of 16 len, 0.02 perm factor): percentage of common shingles: 0.906, generate time: 0.0361 sec

As you can see, for inputs that are not 'good' for hash the performance is reduced significantly. I think this is worth to mention in the documentation.

When compiling with the -wno-unused-value flag the following warning is produced:

mum.h:118:13: warning: right-hand operand of comma expression has no effect [-Wunused-value]
  118 |   lo = v * p, hi;
      |

Claims to be 5x faster than SipHash, implementations:

• c++ version
• go version

In how to use MUM we can read:

• mum_hash_init, mum_hash_step, and mum_hash_finish for hashing complex data structures
• mum_hash64 for hashing a 64-bit data
• mum_hash for hashing any continuous block of data

The most often scenario I'm woking with is creating hashes for multiple continuous blocks of data.
How should I do that with MUM, it is not obvious from the source.

e.g. how to I get the single hash over the following arrays with the right combinations of mum functions ?

const uint8_t key_1 [1] = { 0 };
const uint8_t key_2 [2] = { 1, 2 };
const uint8_t key_3 [3] = { 1, 2, 3 };