3 ms·

Actually, making the next hash dependent on previous hash through the `seed` doesn't work for benchmarking latency. Several hashes only use the seed at the ver

Actually, making the next hash dependent on previous hash through the `seed` doesn't work for benchmarking latency. 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.

injinj 8y ago
Good point. 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/138543ccc6a23ceb1fcdc05f4628858e 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.
- injinj 8y ago
  The cache line latency is strongly associated with the number of hash call repetitions. At 1, 2, 3, 4 repeats, the latency is not present in the timestamp counter. From 5 -> 9 repeats, the latency builds, adding 2 cycles of latency each repeat step. 9 is the max latency added, for a total of 10 additional cycles. I can make the latency go away with a memory fence added after each repetition, but the total number of cycles added is about 50. 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/138543ccc6a23ceb1fcdc05f4628858e https://gist.github.com/injinj/138543ccc6a23ceb1fcdc05f46288...
- Cyan4973 8y ago
  I'm afraid I don't follow. Is there any code source that could be read ? 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.
  - injinj 8y ago
    This is notable, because this is what rurban/smhasher does in the small key test, which many are using nowadays. 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.

injinj 8y ago

Good point. 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/138543ccc6a23ceb1fcdc05f4628858e 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.

injinj 8y ago
The cache line latency is strongly associated with the number of hash call repetitions. At 1, 2, 3, 4 repeats, the latency is not present in the timestamp counter. From 5 -> 9 repeats, the latency builds, adding 2 cycles of latency each repeat step. 9 is the max latency added, for a total of 10 additional cycles. I can make the latency go away with a memory fence added after each repetition, but the total number of cycles added is about 50. 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/138543ccc6a23ceb1fcdc05f4628858e https://gist.github.com/injinj/138543ccc6a23ceb1fcdc05f46288...
Cyan4973 8y ago
I'm afraid I don't follow. Is there any code source that could be read ? 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.
- injinj 8y ago
  This is notable, because this is what rurban/smhasher does in the small key test, which many are using nowadays. 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.