It would be interesting to also have a test where an average size was chosen, but where the actual sizes varied randomly around that average - because that's a common case in real world code, and the results can be very different since branch prediction won't be perfect any more as it is with the fixed size tests.
Also, latency usually means feeding the output of the function back into the input of the next call. Throughput is what you get when you don't do that but you still need to consume the result, so it's not optimized away. You can use something like DoNotOptimize here:
https://github.com/google/benchmark/blob/master/include/benc...
The graphs from the "latency" test are doing this:
for (;;) {
h = hash( val, seed );
seed += h;
}
The original smhasher did this: for (;;) {
hash( val, seed );
}Several hashes only use the seed at the very end of calculation. Among them, CityHash, FarmHash, MeowHash, probably a few more. This makes it possible for them to start calculating next hash before the end of the previous one, so it's no longer "latency" for them, and the test condition becomes uneven.
In reality, in a latency scenario, the hash function is waiting for the input. So it's the input which must depends on previous hash result. This way, all algorithms must wait for previous result, no more dependency on how a specific algorithm handle the seed.
I created a graph with these attributes:
0 total += hash (XXH364) 1 seed += hash (XXH364Seed) 2 seed += hash, val += hash (XXH364SH)
https://gist.github.com/injinj/138543ccc6a23ceb1fcdc05f46288...
There are weird bumps at some key sizes with City and XXH when the key is updated with the previous hash. My guess is there is some underlying cache line latency added when the key is written to.
smhasher should really have a test for good seeding. As I understand it, bad City seeding was the reason people started using SipHash.
Graphs:
1. The original, with repeat at 32
2. The repeats, 1 -> 9
3. The repeats + memory fence, 1 -> 9
https://gist.github.com/injinj/138543ccc6a23ceb1fcdc05f46288...The way to force the hash algorithm to actually wait for input is to use the previous hash to determine the start position of next hash's input. Jumping doesn't have to be large. You can get good results with just a few hundred bytes of variance.
In SpeedTest.cpp, there is a function called timehash():
uint64_t *aligned_result = (uint64_t *) aligned_alloc( 64, 256 / 8 );
uint64_t *aligned_buf = (uint64_t *) aligned_alloc( 64, 256 );
memcpy( aligned_buf, key, len );
begin = rdtsc();
for (int i = 0; i < repeat; i++) {
hash(aligned_buf,len,seed,aligned_result);
seed += aligned_result[0];
aligned_buf[0] += aligned_result[0];
aligned_buf[1] += aligned_result[1];
}
end = rdtsc();
Take away the aligned_buf += aligned_result, and the additional latency goes away.When I get a chance, I'll try your method of randomizing input.
total = 0;
for (;;) {
total += hash( val, seed );
}
Note that the hash value is consumed, but doesn't feed into the next result so multiple hashes can run in parallel. If that wasn't the case, it is lucky the loop wasn't compiled away entirely (probably because the hash functions and the test loop are in different compilation units and LTO is not turned on).
I find it to be the fastest hash in my stable of hashes.
Graphs for 64 / 128:
https://github.com/injinj/smhasher/blob/master/plot64.svg
https://github.com/injinj/smhasher/blob/master/plot128.svg
Latency graphs for 64 / 128
https://github.com/injinj/smhasher/blob/master/plot64lat.svg
https://github.com/injinj/smhasher/blob/master/plot128lat.sv...
Latency is using the hash result after each function, the original smhasher algo does not use the result.