3 ms·

umash (https://github.com/backtrace-labs/umash https://github.com/backtrace-labs/umash) has a similar structure PH block structure (and similar universality gua

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

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