4 ms·

I updated the post to reflect the numbers I get from the native rust implementation's benchmarks (instead of SMHasher's copy of the C code): 66 ns and 5.5 GB/s.

I updated the post to reflect the numbers I get from the native rust implementation's benchmarks (instead of SMHasher's copy of the C code): 66 ns and 5.5 GB/s. However, I don't see any dependency chain between iterations in the short-input benchmarks; the numbers don't necessarily reflect latency as much as throughput when hashing a lot of short inputs independently (a rare situation). Even SMHasher gets that wrong: writing some of the previous iteration's output to the new hashed data, or using it to update the "seed" may not suffice, depending on the algorithm. It's probably safest to derive the address of hashed data from the previous hash value; I think this would look like `slice.split_at(prev_hash & 8).1.split_at(hash_size).0` in Rust, where the input `slice` is padded with 8 extra elements.

oconnor663 6y ago
> I updated the post Thanks for taking the time to do that! > SMHasher's copy of the C code It looks like that copy is old, but still I wouldn't expect it to be ~4x slower. My guess is it's some build configuration issue excluding the AVX-512 code. It's on our todo list to make a reusable CMake build setup for our C implementation, but we haven't gotten to it yet. > the numbers don't necessarily reflect latency as much as throughput That's an interesting point. What's an example of an application that needs to hash a lot of small inputs, with data dependencies between them?
- pkhuong 6y ago
  > That's an interesting point. What's an example of an application that needs to hash a lot of small inputs, with data dependencies between them? For short inputs, we want to estimate the time that elapses from the moment we know what data to hash, to the moment when we know that data's hash value. For example, a realistic application might hash one small input and immediately need the result of the hash to, e.g., determine where to probe in a hash table. When a benchmarking loop does not introduce data dependencies between iterations, it lets hardware superscalar and out-of-order execution overlap the computation for multiple hashes; when we don't need the result of `hash(x)` to start `hash(y)`, the time it takes to compute `hash(x)` and `hash(y)` is often less than twice the time it takes to compute `hash(x)`. For short inputs and simple algorithms, we might actually observe that it takes exactly as many cycles to compute one or two independent hashes (for example, that's what we observe for UMASH on <= 8 bytes). Did we improve the latency of our hash function by computing two values in a loop? By most people's definition of "latency," that's a no. What we did do is improve the throughput, for independent computations. However, the throughput on short inputs is rarely what matters... and, for longer inputs, overlapping the first or last couple iterations is essentially measurement noise. In a pure hashing loop, we don't really have anything to block execution on the output of the hash function. We can come close by making each call to the hash function depend on the previous call's result: this way, the average time it takes to compute one hash in a series of n will roughly match the time it takes to fully compute one hash.

oconnor663 6y ago

> I updated the post Thanks for taking the time to do that! > SMHasher's copy of the C code It looks like that copy is old, but still I wouldn't expect it to be ~4x slower. My guess is it's some build configuration issue excluding the AVX-512 code. It's on our todo list to make a reusable CMake build setup for our C implementation, but we haven't gotten to it yet. > the numbers don't necessarily reflect latency as much as throughput That's an interesting point. What's an example of an application that needs to hash a lot of small inputs, with data dependencies between them?

pkhuong 6y ago
> That's an interesting point. What's an example of an application that needs to hash a lot of small inputs, with data dependencies between them? For short inputs, we want to estimate the time that elapses from the moment we know what data to hash, to the moment when we know that data's hash value. For example, a realistic application might hash one small input and immediately need the result of the hash to, e.g., determine where to probe in a hash table. When a benchmarking loop does not introduce data dependencies between iterations, it lets hardware superscalar and out-of-order execution overlap the computation for multiple hashes; when we don't need the result of `hash(x)` to start `hash(y)`, the time it takes to compute `hash(x)` and `hash(y)` is often less than twice the time it takes to compute `hash(x)`. For short inputs and simple algorithms, we might actually observe that it takes exactly as many cycles to compute one or two independent hashes (for example, that's what we observe for UMASH on <= 8 bytes). Did we improve the latency of our hash function by computing two values in a loop? By most people's definition of "latency," that's a no. What we did do is improve the throughput, for independent computations. However, the throughput on short inputs is rarely what matters... and, for longer inputs, overlapping the first or last couple iterations is essentially measurement noise. In a pure hashing loop, we don't really have anything to block execution on the output of the hash function. We can come close by making each call to the hash function depend on the previous call's result: this way, the average time it takes to compute one hash in a series of n will roughly match the time it takes to fully compute one hash.