4 ms·

> 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

> 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.

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.