Wojciech Muła, Nathan Kurz, Daniel Lemire
2016 · arXiv
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).
Metadata: arXiv. Abstracts retain their original authors’ rights.
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
5 selected excerpts · 5 total mentions
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
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 - https://arxiv.org/abs/1611.07612 .
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
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 Instructions https://arxiv.org/pdf/1611.07612.pdf
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 "obfuscation" comments. I'd guess that they were intended as jokes, but missed the target. Rather than mocking the use of reduce, I think his goal was probably to defend the utility of the humble for loop. On a larger level, both he and I have a concern that people often assume "a sufficiently clever compiler" without checking to see that they actually have one. Here's the sort of thing I've been…
working on him with: https://arxiv.org/abs/1611.07612. It's shows how to count number of set bits with SIMD in a way that is faster than the using the builtin POPCNT instruction. This is a different level of optimization than concerns most programmers, but if you are trying to get that last 50% of maximum performance out of an implementation, it's likely that (at this point) Swift shouldn't be your top choice.
More from the same topics.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
Luca Beurer-Kellner, Beat Buesser, Ana-Maria Creţu +11
As AI agents powered by Large Language Models (LLMs) become increasingly versatile and capable of addressing a broad spectrum of tasks, ensuring their security has become a critical challenge.
Ross Mcilroy, Jaroslav Sevcik, Tobias Tebbi +2
The recent discovery of the Spectre and Meltdown attacks represents a watershed moment not just for the field of Computer Security, but also of Programming Languages.
Daniel Ingalls
This paper presents a personal view of the evolution of six generations of Smalltalk in which the author played a part, starting with Smalltalk-72 and progressing through Smalltalk-80 to Squeak and Etoys.