HackerPapers

arXiv:1503.03465cs.DS

Faster 64-bit universal hashing using carry-less multiplications

Daniel Lemire, Owen Kaser

Abstract

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.

arXiv comments
Journal reference
Journal of Cryptographic Engineering, Volume 6, Issue 3, pp 171-185, 2016
DOI
doi:10.1007/s13389-015-0110-5
Subjects
cs.DSData Structures and Algorithms cs.PFPerformance

On Hacker News

Linked by 3 identifiable commenters in 3 comments across 3 threads, from Oct 2015 to Dec 2016. Found in 1 HN submission from Nov 2015 to Nov 2015. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions (2013) 1 comment

    • 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…

      nkurzView on HNParent context

  2. HighwayHash: Strong hashing at 0.3 clock cycles per byte 1 comment

    • 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…

      jbappleView on HNParent context

  3. Crazily fast hashing with carry-less multiplications 1 comment

    • 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…

      twotwotwoView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.