PaperlayerView exact revision on arXiv

Source-linked AI summary

Decoding billions of integers per second through vectorization

Daniel Lemire, Leonid Boytsov

arXiv:1209.2137v7cs.IRcs.DB

TL;DR

Integer-array encoding and decoding consume substantial CPU time in applications such as search and databases. The paper introduces vectorized binary-packing and patched schemes, including SIMD-BP128 and SIMD-FastPFOR, to improve decoding speed while retaining competitive compression. The schemes are reported as up to twice as fast as prior methods, with SIMD-FastPFOR combining faster decoding with compression close to Simple-8b.

  • Problem

    Integer-array encoding, especially decoding, consumes considerable CPU time, motivating faster compression and decompression methods.

  • Method

    The paper vectorizes binary packing, patched compression, differential decoding, and prefix-sum operations, including a new exception layout for SIMD-FastPFOR.

  • Results

    Up to twice as fast as previously best available schemes, the proposed methods retain competitive compression ratios; SIMD-FastPFOR is at least 30% faster than PFOR with a 10% superior compression ratio.

  • Takeaways & Limitations

    SIMD-BP128 is the fastest scheme, while SIMD-FastPFOR provides better compression than binary packing with fast vectorized decoding.

  • Takeaways & Limitations

    Vectorized bit-packing can worsen compression, and larger SIMD block sizes make binary packing less space-efficient with outlier values.

Abstract

from arXiv · show

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.

1. INTRODUCTION

Integer-array compression matters because memory access limits many workloads, while specialized SIMD schemes target faster decoding and competitive compression. The paper introduces vectorized approaches that improve on prior methods and accelerate differential decoding.

  • Data compression can improve query performance by reducing main-memory bandwidth requirements as memory access increasingly limits workloads.
  • Sorted posting lists and database indexes use small integer differences, which differential coding compresses more efficiently than original values.
  • SIMD-based schemes improve integer-decoding performance by processing multiple values with specialized processor instructions.
  • A factor of two improvement over varint-G8IU was achieved while also improving compression ratio.
  • SIMD-FastPFOR surpasses PFOR decoding speed by at least 30% while offering a 10% superior compression ratio.
  • Vectorized prefix sums can be twice as fast, and without vectorized differential coding the authors could not reach two billion integers per second.

2. RELATED WORK

Earlier integer-compression methods trade compression efficiency, decoding speed, and vectorization support in different ways. The related work spans universal codes, byte-oriented methods, and vectorized block-based decoding.

  • Golomb and Rice coding encode quotients in unary and remainders in binary, but are much slower than Variable Byte.
  • Interpolative coding exploits sorted-array bounds for compact representation, but is slower than Golomb coding.
  • Elias gamma and delta coding represent integers through unary and binary components, but gamma coding becomes inefficient as values grow.
  • Variable Byte is twice as fast as Elias gamma and delta coding, yet gamma coding falls short of the objective of decoding billions of integers per second.
  • k-gamma stores blocks of 2 or 4 integers with a shared bit length to ease vectorization.
  • During k-gamma decompression, groups are decoded with mask-and-shift operations without branching after retrieving their gamma-coded binary length.
  • The reported best k-gamma decoding speed was approximately 550 million integers per second on synthetic data, below the paper’s objective.

2.4. Variable Byte and byte-oriented encodings

Variable Byte stores integers in byte units, while byte-oriented grouped schemes reorganize descriptors to decode several integers simultaneously. Varint-G8IU uses 8-byte groups and SIMD shuffling, improving decoding speed relative to earlier byte-oriented methods while trading some compression.

  • Variable Byte: Variable Byte uses seven data bits per byte and an eighth-bit terminator to encode integers in variable-length byte sequences.During decoding, bytes are read sequentially and a new integer is emitted when the eighth bit is one.
  • Performance and compression: Variable Byte remains reasonably efficient: in the authors’ tests, it encoded data three times faster than most alternatives and matched parsimonious schemes on less-compressible data.The paper also notes that varint-G8IU was probably the fastest prior literature method, subject to cross-platform comparison limits.
  • Grouped byte-oriented encodings: Varint-GB stores one two-bit length descriptor for each of four integers, enabling grouped byte-oriented decoding.For lengths 2, 3, 1, and 4 bytes, the four descriptor fields occupy one byte and the values occupy 10 bytes.
  • Grouped byte-oriented encodings: Varint-G8IU assigns one descriptor bit to each byte in an 8-byte group, which can contain 2–8 integers.A descriptor bit of zero marks the end of an integer, reversing Variable Byte’s terminator convention.
  • SIMD decoding: On recent x86 processors, varint-G8IU uses the SSSE3 pshufb instruction to copy selected source bytes into a target buffer and zero others in parallel.The shuffle mask is derived from the descriptor and specifies the byte locations and zero-filled positions.
  • Performance and compression: Varint-G8IU was reported as up to 20% faster than SIMD-based varint-GB and 2–3 times faster than Variable Byte, with compression trade-offs.The cited comparison reports slightly better compression than SIMD-based varint-GB but up to 10% worse compression than Variable Byte.

2.5. The Simple family

The Simple family emits fixed-width words while processing variable numbers of integers, allowing especially compact representations for highly compressible data. Simple-8b is the competitive 64-bit member, using selectors to greedily choose bit widths and offering efficient decoding.

  • Family design: Simple-family schemes output a fixed number of bits while processing a variable number of integers, unlike Variable Byte’s variable-length output per integer.Their non-byte-oriented layout can represent sequences containing only 0 and 1 at approximately 1 bit per integer.
  • Simple-8b: Simple-8b outputs 64-bit words with a 4-bit selector and 60 data bits, storing each integer in a common bit width within the word.It has two schemes for long zero sequences and fourteen schemes for positive integers.
  • Simple-8b: Selector 2 stores 60 integers using 1 bit each, while selector 3 stores 30 integers using 2 bits each.These modes cover values in {0,1} and [0,3], respectively.
  • Simple-8b: Simple-8b greedily tests selectors from the smallest value and chooses the first mode that fits as many next integers as possible.Larger selector values use larger bit widths and fit fewer integers into the 60 data bits.
  • Comparative scope: Simple-9 and Simple-16 may compress slightly better than Simple-8b but are generally slower, so the experiments omit them.Simple-8b supports integers through [0, 2^60), whereas Simple-9 and Simple-16 are restricted to [0, 2^28).
  • Performance and compression: Simple-8b decodes efficiently with little branching and achieves a better compression ratio than Variable Byte, although it encodes more slowly than Variable Byte.The table caption states that between 1 and 240 integers can be coded with one 64-bit word.

2.6. Binary Packing

Binary packing stores blocks of integers using a shared bit width determined by the block’s value range. The approach can provide competitive compression, with a corresponding information-theoretic lower bound analyzed in the paper.

  • Block representation: Binary packing partitions values into blocks, codes each block’s range, and stores every value relative to that range using a common bit width.For values in [1000, 1127], the example uses 7 bits per integer.
  • Storage cost: Binary packing’s storage cost is determined by the maximum-value bit width b, block length B, and fixed overhead κ.The resulting block cost is bB + κ, with fixed-length blocks such as B = 32 or B = 128.

2.7. Binary Packing with variable-length blocks

Variable-length binary packing adapts block sizes to reduce total storage cost, balancing bit-width savings against per-block overhead. Prior methods use heuristics or dynamic programming to select partitions.

  • Fixed-length packing: Binary-packing storage depends on the maximum bit width, block length, and fixed per-block overhead.For a block of length B and width b, the total cost is bB + κ.
  • Variable-length packing: Variable-length packing permits each block to use a different length, adding overhead because both bit width and block length must be stored.The optimization partitions the array to minimize the sum of block costs.
  • Prior adaptive methods: Dynamic block-length heuristics were reported to provide compression gains of 15–30%.Deveaux et al. used both top-down and bottom-up heuristics.
  • Prior adaptive methods: AFOR-2 tests block lengths 8, 16, and 32, while AFOR-3 adds special processing for successive integers and greedily minimizes storage over local configurations.Their configuration search considers partitions of 32 integers into candidate block arrangements.
  • Prior adaptive methods: VSEncoding uses dynamic programming over block lengths 1–14, 16, and 32 to find a partition that truly minimizes total storage cost.The method operates on the integer logarithm of every array element and is expected to compress better than AFOR-2 and AFOR-3.

2.8. Patched coding

Patched coding reduces the impact of large integers by storing low bits directly and handling exceptions separately. PFOR uses page-level widths, while NewPFD and OptPFD select widths per block and improve compression.

  • PFOR: PFOR stores values below 2^b directly and records larger values as exceptions in a separate location.The input is partitioned into pages, and each page uses a fixed bit width.
  • PFOR: A PFOR page selects one bit width b using a sample of at most 2^16 integers and tests candidate widths for compression.A histogram of integer logarithms can accelerate this selection.
  • NewPFD and OptPFD: NewPFD and OptPFD choose a bit width per block of 128 integers instead of using one width per page.They avoid compulsory exceptions by storing the first b bits of exceptional values and compressing their high bits and locations.
  • Comparison: PFOR and PFOR2008 use one bit width per page and can generate compulsory exceptions, unlike NewPFD and OptPFD.NewPFD and OptPFD store exceptions per block, while PFOR and PFOR2008 use page-level exception handling.
  • NewPFD and OptPFD: NewPFD chooses the smallest b with no more than 10% exceptions, whereas OptPFD chooses the width maximizing compression.Candidate widths are restricted to 0–16, 20, and 32 to accelerate processing.

3. FAST DIFFERENTIAL CODING AND DECODING

Differential coding replaces sorted integers with smaller successive differences, but straightforward differential decoding can dominate runtime. The paper evaluates standard and vectorized differencing approaches.

  • Decoding cost: A straightforward differential decoding implementation can be four times slower than decompressing small integers.The authors note that differencing is often treated as negligible despite this measured cost.
  • Evaluated approaches: The paper evaluates standard differential coding and a vectorized variant that subtracts the element four positions earlier.The vectorized variant leaves the first four elements unmodified.

4. FAST BIT UNPACKING

Bit packing encodes each small integer with a fixed b-bit field, but fields can cross word boundaries. Vectorization replaces scalar unpacking operations with SIMD operations over multiple integers.

  • Bit packing: Bit packing concatenates fixed-width b-bit representations of integers in [0, 2^b) across 32-bit words.Integers using fewer than b bits are padded with zeros.
  • Representations: Eight 4-bit integers fit in one 32-bit word, whereas eight 5-bit integers require two words with 24 unused bits.The seventh 5-bit field crosses the word boundary.
  • Scalar unpacking: The unpack4 8 and unpack5 8 procedures decode tightly packed fields without branching, although unpack5 8 handles a field crossing two words.Most integers are extracted with four simple operations.
  • Vectorization: Vectorized scalar operations let one unpacking call decode m × 8 integers instead of eight, with recent x86 SIMD instructions using m = 4.Shifts, assignments, and bitwise operations act on vector elements simultaneously.
  • SSE2 implementation: The SIMD implementation replaces C operators with SSE2 intrinsics that process four 32-bit integers at once.For example, vectorized shifts and logical operations correspond to the scalar unpacking operations.

5. NOVEL SCHEMES: SIMD-FASTPFOR, FASTPFOR AND SIMPLEPFOR

FastPFOR and SimplePFOR combine block-level bit-width selection with page-level exception storage to improve the speed–compression trade-off. SIMD-FastPFOR further vectorizes packing, accepting modest padding overhead.

  • Design: FastPFOR and SimplePFOR choose a bit width per 128-integer block while storing exceptions per page.This combines the block-level width selection of NewPFD and OptPFD with page-level exception storage similar to PFOR.
  • Bit-width selection: The heuristic selects b by minimizing b × 128 + (14 − b) × c, where c is the number of exceptions at width b.A histogram of integer bit widths supplies c for candidate widths.
  • Exception compression: SimplePFOR compresses all high exception bits once per page with Simple-8b, while FastPFOR packs them in 32 arrays grouped by bit-width difference.The schemes are otherwise identical.
  • Compression example: 92 bits store 16 example integers, or 5.75 bits per integer, when truncated data, exception metadata, and high bits are compressed.This is below the example’s maximal bit width of 6.
  • Performance: FastPFOR and SimplePFOR encode integers about twice as fast as NewPFD in the reported tests.The authors associate this result with compressing exceptions in bulk.
  • SIMD-FastPFOR: SIMD-FastPFOR vectorizes packing of truncated integers and exception high bits, adding about 0.3–0.4 bits per integer of padding overhead.The overhead comes from array and alignment padding.

6. EXPERIMENTS

Experiments show that the vectorized schemes achieve strong decoding speed, with performance and compression varying across methods, array lengths, and data sets.

  • Bit packing and unpacking: ≈6000 mis is achieved when unpacking integers with bit widths of 8 or less, subject to blocks of at least 128 integers.The vectorized version is roughly twice as fast as the scalar version.
  • Bit packing and unpacking: 70% faster unpacking is achieved by the vertical layout than the horizontal layout for bit widths below 8 or above 27.The two layouts have the same speed from 16 to 26 bits; all schemes therefore use the vertical layout.
  • Synthetic data sets: 2500 mis is the decoding speed reached by SIMD-BP128⋆, compared with 220 mis for Variable Byte.Compression efficiency differs relatively little between Variable Byte and FastPFOR, despite the large speed gap.
  • Synthetic data sets: SIMD-FastPFOR is the clear decoding-speed winner among the schemes with the best compression ratios on long arrays.FastPFOR, SimplePFOR, and SIMD-FastPFOR have equally good compression ratios, while SIMD-FastPFOR decodes faster than the first two.
  • Synthetic data sets: SIMD-BP128⋆ is always 400 mis faster during decoding than any other alternative while matching Variable Byte’s compression ratio.It does not always provide the best compression ratio.
  • Synthetic data sets: 2 bits per integer is the maximum reported difference between vectorized and regular differential coding, typically less than that.SIMD-BP128⋆ uses about one extra bit per integer compared with SIMD-BP128.
  • Synthetic data sets: SIMD-BP128 and SIMD-FastPFOR dominate PFOR and PFOR2008 across coding speed, decoding speed, and compression ratio.PFOR and PFOR2008 otherwise have the best decoding speed among the schemes taken from the literature in these tests.

7. DISCUSSION

The discussion finds that vectorized binary packing offers strong speed–compression trade-offs, while SIMD-FastPFOR preserves the benefits of patching. It also identifies block size, prefix-sum processing, architectures, and compressed-domain processing as important boundaries and opportunities.

  • Binary packing: SIMD-BP128 is more than 3 times faster than Simple-8b during decoding, although it compresses less efficiently.BP32 approaches OptPFD's compression with decoding within 10% of PFOR's speed.
  • Vectorized processing: 4000–8500 mis decoding speeds can make delta computation and prefix sums a major bottleneck.Vectorizing these operations may remove the bottleneck, though the authors report poorer compression ratios in their case.
  • Patched schemes: SIMD-FastPFOR is at least 35% better in compression ratio than SIMD-based varint-G8IU while decoding faster.On realistic data, it also beats BP32 on decoding speed and compression ratio.
  • Block size and patching: Larger SIMD blocks improve vector processing prospects but reduce binary-packing space efficiency when outliers occur.BP32 uses 5.5 bits/int versus 6.3 bits/int for SIMD-BP128 on GOV2; patching can address large-block outliers.
  • Future directions: Directly processing compressed data may favor simpler schemes such as SIMD-BP128 over more sophisticated schemes such as SIMD-FastPFOR.The paper focused on decoding speed rather than this compressed-domain workload.
  • Random access: Blocks of 128 integers can reduce random-access granularity, although vectorized intersection processing has reached a factor-of-5 speedup with much larger blocks.Large blocks may force scans beyond the integers needed by a query.

8. CONCLUSION

The paper presents vectorized compression schemes that combine high speed with competitive compression and encoding performance. SIMD-FastPFOR achieves this balance by storing exceptions in a vectorizable form, while future work targets broader architectures and trade-offs.

  • Conclusion: The new schemes are up to twice as fast as the previously best available schemes while retaining competitive compression ratios and encoding speed.The speedup comes from vectorizing almost every step, including differential decoding.
  • Future work: Future work includes evaluating more varied architectures and providing a wider range of speed–compression trade-offs.

A. INFORMATION-THEORETIC BOUND ON BINARY PACKING

This section bounds the storage cost of binary packing for sorted 32-bit integer arrays by relating block bit widths to delta ranges. It concludes that BP32 and SIMD-BP128 are 2-optimal for sufficiently short arrays.

  • Setup: Binary packing is analyzed for deltas computed from arrays of n distinct sorted 32-bit integers.The goal is to show that this approach is reasonably efficient.
  • Storage bound: Each block of B integers incurs an 8-bit bit-width overhead, while its storage depends on the block's bit width and delta range.The bit width is bounded by the logarithm of the difference between the block's largest and smallest elements.
  • Storage bound: The worst-case total storage is obtained when each block difference satisfies ∆i = 2^32B/n.
  • Storage bound: Binary packing is suboptimal by 8/B + 1 + log B bits/int in the worst case.The bound is expressed for blocks of B integers.
  • Optimality: BP32 is 2-optimal for arrays shorter than 2^25 integers, while SIMD-BP128 is 2-optimal for arrays of length 2^23 or less.These guarantees mean storage is no more than twice the information-theoretic limit.
Loading 1209.2137v7…