4 ms·

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

by 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 pbsd 5y ago

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.