3 ms·

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-

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.

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.