HackerPapers

arXiv:1611.07612cs.DS

Faster Population Counts Using AVX2 Instructions

Wojciech Muła, Nathan Kurz, Daniel Lemire

Abstract

Counting the number of ones in a binary stream is a common operation in database, information-retrieval, cryptographic and machine-learning applications. Most processors have dedicated instructions to count the number of ones in a word (e.g., popcnt on x64 processors). Maybe surprisingly, we show that a vectorized approach using SIMD instructions can be twice as fast as using the dedicated instructions on recent Intel processors. The benefits can be even greater for applications such as similarity measures (e.g., the Jaccard index) that require additional Boolean operations. Our approach has been adopted by LLVM: it is used by its popular C compiler (clang).

arXiv comments
Software is at https://github.com/CountOnes/hamming_weight
Journal reference
Computer Journal, Volume 61, Issue 1, 1 January 2018
DOI
doi:10.1093/comjnl/bxx046
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 5 identifiable commenters in 6 comments across 6 threads, from Dec 2016 to Sep 2022. Found in 2 HN submissions from Nov 2016 to Jul 2021. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments6 threads

  1. Intel Hyperscan is a high-performance multiple regex matching library 1 comment

    • Best throw away all your CPUs then too: https://groups.google.com/g/comp.arch/c/UXEi7G6WHuU/m/Z2z7fC... https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://arxiv.org/abs/1611.07612

      LammyView on HNParent context

  2. The NSA Instruction (2019) 1 comment

    • You can also go faster using SIMD instructions if you need to compute wider population counts (beyond 64 bits): Faster Population Counts Using AVX2 Instructions, Computer Journal, Volume 61, Issue 1, 2018 https://arxiv.org/abs/1611.07612

      dlemireView on HNParent context

  3. Popcount CPU instruction 1 comment

    • Though, interestingly, if AVX2 is available then Lemire's CRoaring package uses a Harley-Seal popcount implementation, at https://github.com/RoaringBitmap/CRoaring/blob/master/includ... , rather than the POPCNT64 instruction. Because it's faster…

      eesmithView on HNParent context

  4. Abusing the CPU's Adder Circuits 1 comment

    • You are obviously already on top of the concept, but in the paper "Faster Population Counts Using AVX2 Instructions" we tried to give a clear explanation (with diagrams) of how it can be faster to roll your own popcnt using Carry-Save-Adders: https://arxiv.org/abs/1611.07612

      nkurzView on HNParent context

  5. Low Level Bit Hacks You Absolutely Must Know 1 comment

    • See also: The Aggregate Magic Algorithms page http://aggregate.org/MAGIC/ For example, Population Count instructions exist. But may actually be microcoded to count one bit per cycle. Vectorizing your tallies can yield log time speedups: Faster Population Counts Using AVX2…

      indescions_2018View on HNParent context

  6. Don’t assume that safety comes for free: a Swift case study 1 comment

    • I work with the author regularly, and am inclined to a more charitable reading. I was serious when I suggested that he'd love to receive your Rust benchmark showing that it has no slowdown, and would happily include a note about them. I'm not sure of the the purpose of the…

      nkurzView on HNParent context

Submitted to Hacker News

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