I became (slightly) interested in integer compression after evaluating Parquet for a use case at work — where the columns would delta-encode nicely — then watching this CMU Database Group YouTube video: Vortex: LLVM for File Formats. In the video, Manning disses Parquet and his chief criticism is that the format is slow to adopt better, faster encodings (citing FastLanes and pcodec).
I’ve never thought about integer compression. I know that timeseries databases do it, I know that columnar file formats support it, but isn’t it solved? It turns out: no. Hardware advances are spurring software advances and vice versa. The predominant hardware change was SIMD (single instruction, multiple data). And the latest reigning software implementation is FastLanes.
This post talks about two of those advances in integer compression — neither of which is in Parquet’s delta encoding.
SIMD Compression and the Intersection of Sorted Integers
In their 2014 paper, Lemire and coauthors improve upon one of Lemire’s earlier papers: Decoding billions of integers per second through vectorization (2012). It’s that earlier paper that Parquet adapts its delta-encoding from. So… yes, Manning might have a point about Parquet being slow to adapt.
In “SIMD Compression and the Intersection of Sorted Integers,” their favorite algorithm has the catchy name “S4-BP128-D4” that comes from:
- S4: four integer SIMD (during binary packing and prefix summing)
- 128: they binary pack 128 integers per group
- D4: delta encoding four integers at a time (more SIMD, worse compression ratio)
Binary Packing
The paper gives an introduction to integer binary packing. The gist is to store numbers using the minimum bits necessary for the largest value in a block (group of 128):
Consider … the integers 1, 3840, 131073, and 2… The largest of them is 131073 and it can be represented using 18 bits in binary format (as 100000000000000001). Thus we could decide to write the four integers using exactly 18 bits per integer.
The numbers above are compressed from 32 bits to 18 bits. Those remaining 14 bits (32-18) are then used for the first 14 bits of the 5th number: the numbers’ bits are packed round-robin across four SIMD lanes (called interleaving) so decompression in a 128-bit register via SIMD decompresses four numbers at once:
This works well, but the author points out it performs poorly if a few outliers blow up the minimum number of bits:
The downside of the S4-BP128 approach is that the largest integers in a block of 128 integers determine the compression ratio of all these integers… We consider a block of 128 integers beginning with 1,2, 1, 134217729, 0. We assume that all values in the block except for 134217729 do not exceed three and, thus, can be encoded using two bits each.
To mitigate that, the authors use “patched coding.” They store large outliers in a separate set of metadata, replacing the outliers (exceptions) with small references. During decompression, those references are replaced with the original, large value. At this point in the paper nothing is new — it’s just background describing where the 2012 paper left things.
Differential Coding/Delta Encoding
Unfortunately for 2012 Lemire — but fortunately for 2014 Lemire publishing another paper — his patched coding doesn’t play well with the next concept: differential coding. This matters because databases and file formats are rarely skipping straight to binary packing. Instead, they take the delta between numbers, then binary encode those (likely smaller) numbers to store the numbers with fewer bits:
Differential coding takes a sorted integer list x1, x2… and replaces it with successive differences (or deltas) δ2, δ3, … = x2 − x1, x3 − x2,… Since the deltas are smaller than the original integers in the list, we get better compression ratios.
Here is an example from Parquet — which, aside: handles negative values by subtracting the min delta and storing in header:
7, 5, 3, 1, 2, 3, 4, 5, the deltas would be -2, -2, -2, 1, 1, 1, 1 The minimum is -2, so the relative deltas are: 0, 0, 0, 3, 3, 3, 3 The encoded data is header: 8 (block size), 1 (miniblock count), 8 (value count), 7 (first value) block: -2 (minimum delta), 2 (bitwidth), 00000011111111b (0,0,0,3,3,3,3 packed on 2 bits)
To get SIMD involved here too, deltas are computed four-by-four, so one SIMD instruction is de-deltafying (my term) four integers in parallel. The deltas wind up four times as large, requiring more bits, so the compression is worse, but decompression is faster:
The fastest is D4 which computes the deltas four-by-four: e.g., (δ5, δ6, δ7, δ8) = (x5, x6, x7, x8) − (x1, x2, x3, x4)… a single 1-cycle-latency SIMD instruction… can correctly calculate the prefix sum of four consecutive integer
This 2014 paper’s advance is showing how it’s possible, in a single pass of the data, to unpack the bits and also prefix sum (reverting the delta encoding). But it hits a snag. S4-FASTPFOR — the variant of the algorithm with patching — requires extra operations for the patching that slow it down relative to the single-pass approach:
S4-FASTPFOR requires three separate operations in sequence: bit unpacking, patching and computing the prefix sum. Patching must happen after bit unpacking, but before the prefix sum. This makes tight integration between patching and the prefix sum difficult: we tried various approaches but they did not result in performance improvement.
So patched coding gets the boot, and Lemire accepts worse compression for higher speed. A win is a win; it’s much faster: “In some cases, the one-pass approach is almost twice as fast as the two-pass approach.”
The rest of the paper re-uses the improvements from the first part to improve the performance of intersecting two sorted lists of numbers. The authors claim this has relevance for patent databases, e.g. those serving lawyers who “prefer to use complex Boolean queries”… but I think it reads like “let’s bolt something on to make the paper more significant.”
The FastLanes Compression Layout: Decoding >100 Billion Integers per Second with Scalar Code
The Vortex file format, which bills itself as offering equal compression ratios to Parquet while delivering “10-20x faster scans,” uses FastLanes. And its benchmarks seem to support its performance: its read and write throughput is far higher. So, how does FastLanes beat S4-BP128-D4? By re-arranging the values and targeting a large, virtual SIMD register.
Portability
One FastLanes advancement is its portability to wider SIMD register widths. While prior algorithms often targeted 128-bit SIMD registers — four 32-bit integers concurrently being binary packed or de-deltafied — CPUs have expanded to 256 and 512-bit widths:
SIMD register widths in x86 CPUs have doubled three times from MMX (64-bits) to SSE1-4 (128-bits 1999), AVX/AVX2 (256-bits, 2008) and AVX512 (512-bits, 2015). A next doubling is not imminent, but we do see GPUs - and Apple CPUs - adopting a 1024-bit cache-line, which facilitates such a move.
The authors of the FastLanes paper argue that simple extensions of prior algorithms — e.g. using 8-way (for 256-bit registers) or 16-way (for 512-bit registers) formats for binary packing — are short-sighted (register widths might reach 1024 bits soon) and expensive — they each have completely different implementations.
So they skip straight to an implementation targeting a virtual 1024-bit SIMD register. Which is wild, since no CPU supports it. But using a wider 1024-bit register, they can split blocks of integers however necessary to support the SIMD width of the CPU FastLanes is actually running on. For example, if the CPU supports AVX512, and they’re decoding 32-bit integers, they’ll split it in half (two 512-bit instructions). If the CPU supports only SSE1-4 (128-bit), it takes eight 128-bit instructions.
And they do all this while writing scalar code and relying on compilers to auto-vectorize into SIMD, rather than relying on intrinsics (which the Lemire code definitely makes use of).
Avoiding D4’s Worse Compression
As noted, Lemire’s 2014 paper delta decodes four numbers in parallel using a D4 approach where each number’s stored delta is relative to an integer four numbers back rather than the one prior. This makes deltas up to four times larger (about 2 extra bits per integer):
In D4, the differences are 4x bigger, which reduces the compression factor… Unfortunately, to support ever wider SIMD registers, ever larger batches are necessary, increasing this overhead.
In the FastLanes model, its SIMD speedup is not from changing deltas to be against four numbers prior. It’s from re-ordering the numbers to be SIMD-friendly from the start:
Figure 4d shows the “transposed” layout, that stores the values out-of-order. The order for the first 16 values here is 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15. Figure 4e show this leads to optimal 128-bits SIMD processing: only 4 additions are needed. We call this re-ordering a transposition because the idea is to cut up the value column in SIMD register-sized chunks and put these chunks vertically under each other
So they’ve side-stepped worse compression by re-arranging the numbers such that they’re decodable, in order, concurrently across all SIMD lanes.
They still require four bases (above: 25, 41, 55, 74), but they bit-pack the bases as deltas and say it only increases the header metadata by S/1024 (where S is the number of virtual lanes given by (1024/T) and T is the width of the numbers being decoded). In their example, this overhead only increases space by 3%. The next figure directly compares the two approaches: 
Making it Universal Across Integer Widths
They want to re-order rows to decode maximally across SIMD lanes. That creates a challenge though: a naive re-ordering of rows would lead to sort orders that vary between integer widths. More 8-bit values will fit in a register than 16, 32, or 64-bit values so each width would wind up with a different sort order (shown below):
The authors address that by inventing a “Unified Transposed Layout” that lets them decode values in the same order, regardless of integer width (e.g., 8-bit vs 64-bit). The blue rectangles below are 8x16 “tiles” with 128 values each. Targeting their massive 1024-bit virtual register, they can decode a row from all 8 tiles in a single register (bottom) in parallel if the tiles are full of tiny 8-bit integers. If the tiles are full of large 64-bit numbers (top right), then a register holds values from just one row of one tile: they work through one tile at a time.
UTL lets them decode rows in a column of integers in an order where the first row of a tile has a base that is the last row in the preceding tile. Note how in the top three examples, tile “1” is always just beneath tile “0.” And in the narrowest (64-bit integers, 16 columns of which completely fill a 1024-bit virtual register) the tiles are nicely ordered 0, 1, 2…
The improvements add up and their UTL easily beats other decoding strategies: 