Faster Population Counts Using AVX2 Instructions

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).

Software is at https://github.com/CountOnes/hamming_weight

References in corpus (3)

• Better bitmap performance with Roaring bitmaps
• SIMD Compression and the Intersection of Sorted Integers
• Consistently faster and smaller compressed bitmaps with Roaring

Cited by in corpus (14)

• DFTerNet: Towards 2-bit Dynamic Fusion Networks for Accurate Human Activity Recognition
• Roaring Bitmaps: Implementation of an Optimized Software Library
• TernaryNet: Faster Deep Model Inference without GPUs for Medical 3D Segmentation using Sparse and Binary Convolutions
• Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD
• Causal Set Generator and Action Computer
• Automating Generation of Low Precision Deep Learning Operators
• A SIMD algorithm for the detection of epistatic interactions of any order
• Binarizing MobileNet via Evolution-based Searching
• Phonetic Word Embeddings
• Vectorized Character Counting for Faster Pattern Matching
• Efficient Computation of Positional Population Counts Using SIMD Instructions
• Binary Latent Representations for Efficient Ranking: Empirical Assessment
• Rank/Select Queries over Mutable Bitmaps
• Transcoding Billions of Unicode Characters per Second with SIMD Instructions