Intel and AMD support the Carry-less Multiplication (CLMUL) instruction set in their x64 processors. We use CLMUL to implement an almost universal 64-bit hash family (CLHASH). We compare this new family with what might be the fastest almost universal family on x64 processors (VHASH). We find that CLHASH is at least 60% faster. We also compare CLHASH with a popular hash function designed for speed (Google's CityHash). We find that CLHASH is 40% faster than CityHash on inputs larger than 64 bytes and just as fast otherwise.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
At a glance, this seems like a clear explanation of using standard SIMD instructions to solve the problem, but I think the landscape has changed since this was written such that there are now better approaches.
In 2010, Intel released processors with the a dedicated instruction for "packed carry-less multiplication": https://software.intel.com/en-us/articles/intel-carry-less-m.... Unfortunately, the early implementations (through Sandy Bridge) were slow, and could be beaten by combining other SIMD operations as shown in this paper.
With the Haswell generation released in 2013, though, PCLMULQDQ got much faster. Instead of being able to complete one instruction every 8…
Read the full comment
cycles, it became possible to finish one every 2 cycles (inverse throughput went from 8 to 2). This paper 2015 paper "Faster 64-bit universal hashing using carry-less multiplications" shows the difference this makes: https://arxiv.org/pdf/1503.03465.pdf
If you are looking for an explanation of how the problem could be solved with the basic building blocks of SIMD, the 2013 Plank, Greenan, Miller paper might be a good resource. But if you are hoping to implement high performance solution for modern processors, the 2015 Lemire and Kaser paper is probably a better starting point.
(This is with the caveat that I don't actually understand the theory or terminology of Galois fields, and maybe there is something about applying it to Erasure Coding that makes the faster PCLMULQDQ approach inapplicable.)
Where can I read what they mean by "Strong" hashing for HighwayHash? Also, is there a peer-reviewed paper on SipTreeHash? I am not a cryptographer, so I wouldn't trust my own instincts in terms of evaluating its strength compared to SipHash.
For non-cryptographic applications, CLHASH produces 64 bits of result and is 2.004/2^64 almost delta universal, at a cost of 0.16 cycles per byte on Haswell and 0.10 cycles per byte on Skylake.
https://github.com/lemire/StronglyUniversalStringHashing
http://arxiv.org/abs/1503.03465
The paper (http://arxiv.org/pdf/1503.03465v7.pdf) goes into that section 6.1, which Lemire mentions in a comment on the post--summarizing as best I can:
CLHash, the hash the post is focused on, passes all except the avalanche test for strings <8 bytes, and could be made to pass it by adding a bit-mixing step to the end (that provably doesn't make random collisions more likely, since it's an invertible transform on the hash).
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes.
Jon Kleinberg, Sendhil Mullainathan, Manish Raghavan
Recent discussion in the public sphere about algorithmic classification has involved tension between competing notions of what it means for a probabilistic classification to be fair to different groups.