27 ms·

I have measured (on a Skylake core) the hash from Daniel Lemire, Owen Kaser, "Faster 64-bit universal hashing using carry-less multiplications, Journal of Crypt

by cb321 5y ago

I have measured (on a Skylake core) the hash from Daniel Lemire, Owen Kaser, "Faster 64-bit universal hashing using carry-less multiplications, Journal of Cryptographic Engineering (to appear)" at t_cycles = (0.00741 +- 0.00098 cycles/byte) * bytes + (37.43 +- 0.48) which is roughly 135 B/cycle (675 GB/s at 5 GHz) or over 2x faster than the claim here. Admittedly, that 37 cycle fixed cost is probably quite a bit higher, and I don't know how well the bit mixing compares. Parenthetically, a time equation (like t_cycles = coef * bytes + fixedCost) is a more convenient way to summarize performance of this kind of thing than the constant short string/long string mumble-mumble. Yes, loop unrolling/etc. can create step-ish functions and a linear regression is pretty approximate (but my stderrs are pretty small above), but even so..much less tripping over words.

pkhuong 5y ago
umash (https://github.com/backtrace-labs/umash https://github.com/backtrace-labs/umash) has a similar structure PH block structure (and similar universality guarantees), but was designed for decent bit mixing (enough to satisfy smhasher, unlike CLHASH, which needs an additional finalizer) with a lower fixed time cost: 22 cycles for a one-byte hash on a 2.5 GHz Xeon 8175M. I'm not sure how one would use that linear regression. What kind of hardware offers 675 GB/s of memory bandwidth? 140 bytes/cycle is easily more than twice the L2 read bandwidth offered by any COTS chip I'm aware of. There are also warm up effects past the fixed cost of setup and finalizers that slow down hashing for short input. For what range of input sizes (and hot/cold cache state) would you say the regression is a useful model?
- cb321 5y ago
  I was only doing short < 1024 byte strings in L1 (like URI lengths-ish). I'm well aware no memory system on typical HW can deliver that (EDIT: "at large space scale"). The article itself mentions a similar calculation (but at their slower scale) which is why I included it. And yes, warm up absolutely matters. My numbers are for the best case path which is among the only easy things to even define, IMO. Worst and average are sooooo much harder/assumption-riddled. Then you argue a lot about said assumptions. I do the minimum times of many runs in an inner loop and the regression on those min-time results. So, the min-loops will warm up everything like branch predictors, etc. I'd suspect the regression model would hold up to usable L1 cache (e.g. 30 KiB or so). Beyond that, it's mostly just measuring the memory system not the hash function..and I'm not sure what the point of that is. Separation of concerns would suggest L1 perf is most relevant to the "hash calculation part". (IMO, many benchmarks confuse this.) And, yeah..modern memory systems suck. Simple back of the envelope would suggest some DIMM-oriented workload would be waiting on the DIMMs like 95% of the time, usually much higher on Xeons with their low single core BW (maybe 98%!). The Meow article sort of alludes to that as well with less detail. Single core Xeon BW is always a huge disappointment. Forces you to go (very) parallel just to saturate DIMMs (EDIT: which in turn cannot saturate even a single L1!). BTW, it sounds like you know all of this (and maybe more) and I don't mean to suggest otherwise, but I thought some numbers/details might assist other passersby. { EDIT: Also, the stderr on that slope is ~13%. So, it's possible 135 is really 128 (1.05x lower), the 2 cache line/cycle load limit or something like that. This doesn't mean the 640 GB/s rate number is wrong - it just underscores how mismatched memory systems are at their various scales. } { EDIT: and yes, 128/16 = 8x faster than meow, not 2x. Oops. }
pbsd 5y ago
1/135 cycles per byte on Skylake is just plain impossible, even if the hash consisted of simply one xor per 32 bytes of input. The lower bound for CLHASH would be the cost of one carryless multiplication per 16 bytes of input, or in other words 1/16 ~ 0.0625 cycles per byte, since you can only issue one such multiplication per cycle.
- cb321 5y ago
  Feel free to measure it yourself instead of just speculating. (And as mentioned elsewhere, it is probably 1/128.) { EDIT: and I never measured meow - it could be faster than 1/16 cycle/byte but poorly assessed; just be sure to use a min loop and small data. }
  - brandmeyer 5y ago
    Microbenchmark measurements that are faster than the memory system are frequently a symptom that the compiler optimized most or all of the unit under test into a no-op.
    - cb321 5y ago
      It isn't faster than the L1 memory system which is the most relevant thing to measure to compare hash algos, as already explained.
    - cb321 5y ago
      It isn't faster than the L1 memory system which is the most relevant thing to measure to compare hash algos, as already explained. (duplicated here for clarity/flow) Also, I perhaps could more fully motivate my time equation parenthetical. With such an equation in hand, one can easily compare hash functions with differing trade offs, such as Wang Yi's hash and Farm Hash: mem-wy : tCC = (0.1573 +- 0.0039)*bytes + (7.10 +- 0.13) mem-farm: tCC = (0.3017 +- 0.0014)*bytes + (2.347 +- 0.044) t1 = t2 => m1*n + b1 = m2*n + b2 => n = (b1-b2)/(m2-m1) n = (7.1 - 2.347) / (.3017 - .1573) = (4.753 +- .137) / (0.1444 +- 0.0041) = 32.9 +- 1.3 bytes where this final number is how long strings need to be before Wang Yi's is faster than Farm. So, it is a nicely convenient summary. (And this is true even without my fancy statistical error estimates...) Of course full charts/graphs/yadda-yadda can be even better, but just two summary numbers can also be nice.

by cb321 5y ago

pkhuong 5y ago

umash (https://github.com/backtrace-labs/umash https://github.com/backtrace-labs/umash) has a similar structure PH block structure (and similar universality guarantees), but was designed for decent bit mixing (enough to satisfy smhasher, unlike CLHASH, which needs an additional finalizer) with a lower fixed time cost: 22 cycles for a one-byte hash on a 2.5 GHz Xeon 8175M. I'm not sure how one would use that linear regression. What kind of hardware offers 675 GB/s of memory bandwidth? 140 bytes/cycle is easily more than twice the L2 read bandwidth offered by any COTS chip I'm aware of. There are also warm up effects past the fixed cost of setup and finalizers that slow down hashing for short input. For what range of input sizes (and hot/cold cache state) would you say the regression is a useful model?

cb321 5y ago
I was only doing short < 1024 byte strings in L1 (like URI lengths-ish). I'm well aware no memory system on typical HW can deliver that (EDIT: "at large space scale"). The article itself mentions a similar calculation (but at their slower scale) which is why I included it. And yes, warm up absolutely matters. My numbers are for the best case path which is among the only easy things to even define, IMO. Worst and average are sooooo much harder/assumption-riddled. Then you argue a lot about said assumptions. I do the minimum times of many runs in an inner loop and the regression on those min-time results. So, the min-loops will warm up everything like branch predictors, etc. I'd suspect the regression model would hold up to usable L1 cache (e.g. 30 KiB or so). Beyond that, it's mostly just measuring the memory system not the hash function..and I'm not sure what the point of that is. Separation of concerns would suggest L1 perf is most relevant to the "hash calculation part". (IMO, many benchmarks confuse this.) And, yeah..modern memory systems suck. Simple back of the envelope would suggest some DIMM-oriented workload would be waiting on the DIMMs like 95% of the time, usually much higher on Xeons with their low single core BW (maybe 98%!). The Meow article sort of alludes to that as well with less detail. Single core Xeon BW is always a huge disappointment. Forces you to go (very) parallel just to saturate DIMMs (EDIT: which in turn cannot saturate even a single L1!). BTW, it sounds like you know all of this (and maybe more) and I don't mean to suggest otherwise, but I thought some numbers/details might assist other passersby. { EDIT: Also, the stderr on that slope is ~13%. So, it's possible 135 is really 128 (1.05x lower), the 2 cache line/cycle load limit or something like that. This doesn't mean the 640 GB/s rate number is wrong - it just underscores how mismatched memory systems are at their various scales. } { EDIT: and yes, 128/16 = 8x faster than meow, not 2x. Oops. }

pbsd 5y ago

1/135 cycles per byte on Skylake is just plain impossible, even if the hash consisted of simply one xor per 32 bytes of input. The lower bound for CLHASH would be the cost of one carryless multiplication per 16 bytes of input, or in other words 1/16 ~ 0.0625 cycles per byte, since you can only issue one such multiplication per cycle.

cb321 5y ago
Feel free to measure it yourself instead of just speculating. (And as mentioned elsewhere, it is probably 1/128.) { EDIT: and I never measured meow - it could be faster than 1/16 cycle/byte but poorly assessed; just be sure to use a min loop and small data. }
- brandmeyer 5y ago
  Microbenchmark measurements that are faster than the memory system are frequently a symptom that the compiler optimized most or all of the unit under test into a no-op.
  - cb321 5y ago
    It isn't faster than the L1 memory system which is the most relevant thing to measure to compare hash algos, as already explained.
  - cb321 5y ago
    It isn't faster than the L1 memory system which is the most relevant thing to measure to compare hash algos, as already explained. (duplicated here for clarity/flow) Also, I perhaps could more fully motivate my time equation parenthetical. With such an equation in hand, one can easily compare hash functions with differing trade offs, such as Wang Yi's hash and Farm Hash: mem-wy : tCC = (0.1573 +- 0.0039)*bytes + (7.10 +- 0.13) mem-farm: tCC = (0.3017 +- 0.0014)*bytes + (2.347 +- 0.044) t1 = t2 => m1*n + b1 = m2*n + b2 => n = (b1-b2)/(m2-m1) n = (7.1 - 2.347) / (.3017 - .1573) = (4.753 +- .137) / (0.1444 +- 0.0041) = 32.9 +- 1.3 bytes where this final number is how long strings need to be before Wang Yi's is faster than Farm. So, it is a nicely convenient summary. (And this is true even without my fancy statistical error estimates...) Of course full charts/graphs/yadda-yadda can be even better, but just two summary numbers can also be nice.