4 ms·
Great post and he raises a very valid point that most high-performance hash functions are essentially optimized for high-end 64-bit superscalar microarchitectur
by jandrewrogers 10y ago
Great post and he raises a very valid point that most high-performance hash functions are essentially optimized for high-end 64-bit superscalar microarchitectures. As a practical consequence, the only exploitable parallelism in the silicon is the multiple ALUs within a single core and the algorithms are designed to exploit that effectively. However, as noted in the article, this runs directly into the fact that vector pipelines only support a limited subset of the operations supported by the scalar pipelines, and for the purposes of high-performance hash functions these tend to be disjoint.
His prescription of a new high-performance hash function based on mul32/xor/shift is also exactly correct in my opinion. Not only does it allow you to scale the hash function down to limited microarchitectures but it also allows you to scale it up to the largest/fastest vector engines in most cases for extreme throughput on higher end hardware.
Coincidentally, I also started working on a new set of hash functions based on the mul32/xor/shift motifs precisely for the purpose of getting something that could be efficiently vectorized for performance while still able to run on, say, a 32-bit ARM core.
- mycall 10y agoFeature detection should be a goal for the function container, exploiting the resources given a particular environment. If AVX2 exists, use it; if CUDA does, use that; if both, use both. Why limit the implementation?
- jandrewrogers 10y agoTwo reasons. First, functions may need to cross system boundaries while producing identical results. Second, it simplifies the implementation and reduces the potential defect surface in the function design.
- jsnell 10y agoThanks. > Coincidentally, I also started working on a new set of hash functions based on the mul32/xor/shift motifs precisely for the purpose of getting something that could be efficiently vectorized for performance while still able to run on, say, a 32-bit ARM core. That's cool to hear. I'm happy to reimplement hash functions to fit my bizarre needs, but as per the post I really don't want to design them :) What's your view on how switching from rotates to shift-xors affects quality? Is it mostly neutral as long as the constants are chosen correctly, or is there some quality loss?
- jandrewrogers 10y agoThe use of multiplication as an operator introduces a bit value bias that arguably makes replacing shift with rotate less of a problem than it would be for algorithms that use e.g. the add/rot/xor operators, since shift introduces a (non-symmetrical) counter-bias to multiply as it is basically a special case of division. Rotate is nice for bit diffusion but most of the necessary heavy lifting is in the high bits being shifted low. I have no hard evidence but my intuition is that the loss of quality by moving from rotate to shift is below the noise floor of what is required to patch up the bit value bias introduced by multiply.