Decoding billions of integers per second through vectorization

Abstract

In many important applications -- such as search engines and relational database systems -- data is stored in the form of arrays of integers. Encoding and, most importantly, decoding of these arrays consumes considerable CPU time. Therefore, substantial effort has been made to reduce costs associated with compression and decompression. In particular, researchers have exploited the superscalar nature of modern processors and SIMD instructions. Nevertheless, we introduce a novel vectorized scheme called SIMD-BP128 that improves over previously proposed vectorized approaches. It is nearly twice as fast as the previously fastest schemes on desktop processors (varint-G8IU and PFOR). At the same time, SIMD-BP128 saves up to 2 bits per integer. For even better compression, we propose another new vectorized scheme (SIMD-FastPFOR) that has a compression ratio within 10% of a state-of-the-art scheme (Simple-8b) while being two times faster during decoding.

For software, see https://github.com/lemire/FastPFor, For data, see http://boytsov.info/datasets/clueweb09gap/

References in corpus (1)

• Reordering Columns for Smaller Indexes

Cited by in corpus (17)

• Better bitmap performance with Roaring bitmaps
• Sprintz: Time Series Compression for the Internet of Things
• Techniques for Inverted Index Compression
• SIMD Compression and the Intersection of Sorted Integers
• Consistently faster and smaller compressed bitmaps with Roaring
• A General SIMD-based Approach to Accelerating Compression Algorithms
• Where Is My Training Bottleneck? Hidden Trade-Offs in Deep Learning Preprocessing Pipelines
• The Potential of Learned Index Structures for Index Compression
• Optimizing Guided Traversal for Fast Learned Sparse Retrieval
• Tuple-oriented Compression for Large-scale Mini-batch Stochastic Gradient Descent
• Revec: Program Rejuvenation through Revectorization
• PPQ-Trajectory: Spatio-temporal Quantization for Querying in Large Trajectory Repositories
• Representation Sparsification with Hybrid Thresholding for Fast SPLADE-based Document Retrieval
• Data Compression in the Petascale Astronomy Era: a GERLUMPH case study
• Upscaledb: Efficient Integer-Key Compression in a Key-Value Store using SIMD Instructions
• Efficient Immediate-Access Dynamic Indexing
• Large-Scale Metric Computation in Online Controlled Experiment Platform