4 ms·

It's good to see a focus on small input sizes. Small keys are extremely important for hash functions and are often overlooked. Whenever I've looked at the distr

It's good to see a focus on small input sizes. Small keys are extremely important for hash functions and are often overlooked. Whenever I've looked at the distribution of key sizes in real world Rust code using hash maps it's always turned out to be shockingly small. 8 byte hash inputs are very common in real world code, for instance. Most hash functions and benchmarks are not tuned for small inputs. This is why SipHash is disfavored in Rust these days, because while its performance is excellent on large keys it suffers quite a bit on small ones.

adrianratnapala 8y ago
Yes, although even here, small is not that very small: > The main focus is about short keys of random lengths, with a distribution of length roughly in the 20-30 bytes area, featuring occasional outliers, both tiny and large. I have been playing around trying to write interpreters and compilers for a hobby, and though I haven't taken stats, but I suspect that in source code, identifiers half that length are more than twice as common. It make me wonder if compilers are better of using old-school byte-by-byte hashes rather than new ones optmised for parallelism. (Then again, the hash function probably makes no real difference to speed once in a real-world compiler that does optimisation).
- zokier 8y ago
  > Yes, although even here, small is not that very small: > > The main focus is about short keys of random lengths, with a distribution of length roughly in the 20-30 bytes area, featuring occasional outliers, both tiny and large. Based on the graphs, XXH3 still seems to beat everything at key sizes > 6 (presumably bytes?)
  - deleted 8y ago
    [deleted]
- BeeOnRope 8y ago
  > It make me wonder if compilers are better of using old-school byte-by-byte hashes rather than new ones optmised for parallelism. Probably not. Good hashes optimized for small sizes would probably still use wider loads and operations, perhaps overlapping them: e.g., for a 7 byte hash you might do two 4-byte hashes on the first and second half meaning one byte would get done twice, which isn't a problem. High speed small memory copies follow the same approach. One problem with byte-at-a-time hashes are that byte operations aren't really any faster than wider operations (at least up to 64-bits), so you'll do 7 byte mixing operations in the example above rather than 2. The other problem is that wider chunks tend to "quantize" the number of loops in the algorithm, which is very helpful for branch prediction. A byte-at-a-time hash that uses a loop or some kind of jump into inline code will necessarily mispredict unless the exact length is predictable: but if it varies by even 1 byte, the branching is different. Hashes with larger chunks may take the same path for a range of lengths, so may have fewer mispredictions even if the size varies. For example, a hash that uses two possibly overlapping 4-byte reads may handle sizes from 5-8 (or even 4-8) bytes with the same path, so random variation within that range doesn't cause a mispredict. I think the era of the byte-at-a-time hash is really over, except perhaps if gets some special hardware support.
rtfeldman 8y ago
> SipHash is disfavored in Rust these days I wasn't aware of this! What do people use instead? (I remember reading that part of the motivation for making SipHash the default Hasher was that its randomness guards against hash flooding attacks. Is that something people care about in practice?)
- ComputerGuru 8y ago
  It's a sensitive topic that gets some people really riled up, but essentially it doesn't offer the protection people think it does.
  - deleted 8y ago
    [deleted]
  - deleted 8y ago
    [deleted]
  - wahern 8y ago
    Are you referring to this? http://perl11.org/blog/seed.html http://perl11.org/blog/seed.html That's controversial the way climate change is controversial.
    - eurg 8y ago
      The benefits or the critique? (I could guess, but prefer not to ...)
      - wahern 8y ago
        The critique. There's more rambling by (I think) the same author here: https://github.com/google/highwayhash/issues/28 https://github.com/google/highwayhash/issues/28 His arguments are a little inconsistent and ambiguous, which suggests either a misunderstanding, perhaps a touch of mania, or both. But they're all wrong--whether at face value or when assuming the best possible version--at least regarding the security and the ease of generating collisions. As for the argument that SipHash is too slow, that's a qualitative judgment that many people have made. But they don't usually need to first convince themselves, erroneously, that SipHash is insecure.

adrianratnapala 8y ago

Yes, although even here, small is not that very small: > The main focus is about short keys of random lengths, with a distribution of length roughly in the 20-30 bytes area, featuring occasional outliers, both tiny and large. I have been playing around trying to write interpreters and compilers for a hobby, and though I haven't taken stats, but I suspect that in source code, identifiers half that length are more than twice as common. It make me wonder if compilers are better of using old-school byte-by-byte hashes rather than new ones optmised for parallelism. (Then again, the hash function probably makes no real difference to speed once in a real-world compiler that does optimisation).

zokier 8y ago
> Yes, although even here, small is not that very small: > > The main focus is about short keys of random lengths, with a distribution of length roughly in the 20-30 bytes area, featuring occasional outliers, both tiny and large. Based on the graphs, XXH3 still seems to beat everything at key sizes > 6 (presumably bytes?)
- deleted 8y ago
  [deleted]
BeeOnRope 8y ago
> It make me wonder if compilers are better of using old-school byte-by-byte hashes rather than new ones optmised for parallelism. Probably not. Good hashes optimized for small sizes would probably still use wider loads and operations, perhaps overlapping them: e.g., for a 7 byte hash you might do two 4-byte hashes on the first and second half meaning one byte would get done twice, which isn't a problem. High speed small memory copies follow the same approach. One problem with byte-at-a-time hashes are that byte operations aren't really any faster than wider operations (at least up to 64-bits), so you'll do 7 byte mixing operations in the example above rather than 2. The other problem is that wider chunks tend to "quantize" the number of loops in the algorithm, which is very helpful for branch prediction. A byte-at-a-time hash that uses a loop or some kind of jump into inline code will necessarily mispredict unless the exact length is predictable: but if it varies by even 1 byte, the branching is different. Hashes with larger chunks may take the same path for a range of lengths, so may have fewer mispredictions even if the size varies. For example, a hash that uses two possibly overlapping 4-byte reads may handle sizes from 5-8 (or even 4-8) bytes with the same path, so random variation within that range doesn't cause a mispredict. I think the era of the byte-at-a-time hash is really over, except perhaps if gets some special hardware support.

rtfeldman 8y ago

> SipHash is disfavored in Rust these days I wasn't aware of this! What do people use instead? (I remember reading that part of the motivation for making SipHash the default Hasher was that its randomness guards against hash flooding attacks. Is that something people care about in practice?)

ComputerGuru 8y ago
It's a sensitive topic that gets some people really riled up, but essentially it doesn't offer the protection people think it does.
- deleted 8y ago
  [deleted]
- deleted 8y ago
  [deleted]
- wahern 8y ago
  Are you referring to this? http://perl11.org/blog/seed.html http://perl11.org/blog/seed.html That's controversial the way climate change is controversial.
  - eurg 8y ago
    The benefits or the critique? (I could guess, but prefer not to ...)
    - wahern 8y ago
      The critique. There's more rambling by (I think) the same author here: https://github.com/google/highwayhash/issues/28 https://github.com/google/highwayhash/issues/28 His arguments are a little inconsistent and ambiguous, which suggests either a misunderstanding, perhaps a touch of mania, or both. But they're all wrong--whether at face value or when assuming the best possible version--at least regarding the security and the ease of generating collisions. As for the argument that SipHash is too slow, that's a qualitative judgment that many people have made. But they don't usually need to first convince themselves, erroneously, that SipHash is insecure.