FastPFOR: SIMD integer compression for arrays of mostly small values

The narrow problem the library actually solves

The scope statement is precise, and it matters for evaluating the project. It is a research library with integer compression schemes, broadly applicable to the compression of arrays of 32-bit integers where most integers are small, and it seeks to exploit SIMD instructions whenever possible.

That last clause, where most integers are small, is the assumption everything else follows from. Integer compression is only worth doing when the values are skewed, and a scheme that packs a small number of bits per value is only useful if the values fit in those bits. The codecs in this library are the ones that exploit that skew.

The performance claim is stated as a headline. The library can decode at least four billion compressed integers per second on most x64 desktop or laptop processors, which works out to a decompressing data rate of 15 GB per second, and the readme says this is significantly faster than generic codecs such as gzip, LZO, Snappy or LZ4.

That comparison is a little unfair by construction, and a careful reader will notice. Those generic codecs are byte oriented and work on arbitrary data, so they cannot compete with a codec that knows every value in the array fits in a handful of bits. The right comparison is against other integer codecs, which is what the sibling library list at the end of the readme is for.

The project is also honest about what it is. It calls itself a research library, which means the API is designed to make the codecs accessible and comparable rather than to make them easy to use correctly, and the readme points you at a single example file in the root as the simple example.

Two myths the readme dispels

The readme has a section of myths, and both of them are things people assume about SIMD compression and get wrong.

The first myth is that SIMD compression requires very large blocks of integers, of 1024 or more. The stated fact is that this is not true, because the fastest scheme in the library, SIMDBinaryPacking, works over blocks of 128 integers. The readme also points at another very fast scheme, Stream VByte, which works over blocks of four integers.

That is a genuinely useful correction, because the block size determines the latency of a decode and the memory you have to buffer. A codec that needs a kilobyte of lookahead before it can emit anything is a poor fit for a streaming scenario, while a codec that works over four integers can produce output almost immediately. The reason the myth persists is that some codecs really do need large blocks, and the number 1024 has become associated with the technique rather than with the specific schemes that require it.

The second myth is that SIMD compression means high speed but less compression. The readme says this is wrong, and the reasoning is that some schemes cannot easily be accelerated with SIMD instructions, but many that do compress very well. The misconception comes from treating SIMD as a single category, when in practice it is a property of a specific loop shape. A scheme that packs a fixed number of bits per value vectorises cleanly, and a scheme with a data dependent bit width does not.

The paper references at the end of the readme are where the details live, including the general SIMD-based approach to accelerating compression algorithms, and the earlier work on decoding billions of integers per second through vectorisation.

The security note is the most important paragraph

There is a security section, and it is unusually blunt for a compression library.

It is a low-level library. The inputs are not validated prior to decoding. It is assumed that the provided buffers were generated by the corresponding encoding functions. It is your responsibility to ensure the validity of your data. In production systems, the use of a strong hashing function to check for data integrity is recommended, and the library does not provide this functionality.

Every sentence there is a design decision stated plainly. A codec that decodes a bit-packed stream has to trust the stream, because there is no framing, no length check and no type tag. If the buffer has been tampered with, the decoder will happily produce garbage, and in a search index that garbage can be a wrong answer rather than a crash, which is the harder failure to detect.

The recommendation to add a strong hash is the practical mitigation, and the admission that the library does not implement it is a reminder that the integrity check belongs in the layer above, where you know whether the data came from a trusted store.

This is a design that makes sense for a library whose stated audience is people writing storage engines and search indexes, where the data is produced by the same system that reads it. It is a poor fit for a library sitting on the edge of a network, and it is worth reading the paragraph before you decide where the codec goes.

Sorted lists belong to a different library

The readme addresses a common case and points you elsewhere, which is the kind of honesty that saves a lot of wasted effort.

If you are working primarily with sorted lists of integers, you might want to use differential coding, meaning you compress the deltas instead of the integers themselves. The stated position is that the current library is generic and was not optimized for that purpose, and it points at a separate library designed to compress sorted integer lists, which also comes with new SIMD-based intersection algorithms.

That is a significant recommendation, because sorted integer lists are where inverted indexes live, and the intersection operation is the hot path of a search engine. The companion library also points at a C library for differential coding for the fast computation of deltas and the recovery from them.

So the picture is a family rather than a single project. FastPFOR is the general purpose integer compression library, the sorted list library adds the differential coding and the intersections, and the differential coding C library covers the delta arithmetic on its own.

The readme also lists a wider set of recommended libraries, including a Go integer compression library, a high performance dictionary coding library, LittleIntPacker for packing short arrays quickly, the SIMDComp library, the StreamVByte and MaskedVByte codecs, a C sharp port and a Java port of this library, a Go encoding library, a frame-of-reference library, libvbyte for varbyte 32 and 64 bit compression, TurboPFor with a note that it is well worth checking and is GPL licensed, and Oroch under an MIT licence. The licences are noted individually, which is a courtesy worth copying.

Where this format ended up

The readme lists the users of the library, and this is the most persuasive evidence of its quality, more than any benchmark.

It is used by the zsearch engine and in GMAP and GSNAP, the gene mapping tools. DuckDB derived some of their code from this library. It has been ported to Java, to C sharp and to Go, and the Java port is used by ClueWeb Tools.

The most consequential line is the oldest. Apache Lucene version 4.6.x uses a compression format derived from the FastPFOR scheme, in the form of the PForDelta doc id set.

The Python bindings are a separate project, PyFastPFor, which matters because it is the route by which the schemes can be tried from a notebook before you commit to C++.

There is also a research trail. The readme lists the papers that used the library, including an experimental study of bitmap compression against inverted list compression at SIGMOD in 2017, a survey of lightweight data compression algorithms at EDBT, and work on partitioned Elias-Fano indexes at SIGIR in 2014. The Elias-Fano connection is the interesting one, because that is the structure that made very large sorted integer sets practical in the first place.

The bibliography of the underlying techniques is included too, with the Stream VByte paper, the vectorised decoding paper, the SIMD compression and intersection of sorted integers paper, the vectorised VByte decoding paper and the general SIMD-based approach to accelerating compression algorithms.

A deliberately old compiler baseline

The software requirements section is short and the reason given is the interesting part. The code requires a compiler supporting C++11, and the readme says this was a design decision.

That is a strange thing to say unless you know the history, and the reason is portability. A research library that people want to try, benchmark and compare in their own trees benefits from a low compiler floor, and C++11 is the floor that lets it build in the oldest environments people still care about, which in practice means the compilers shipped with long-term-support distributions and the older toolchains that research environments tend to have.

The build system reflects a library that has been around a while and had to keep working. There is a CMakeLists.txt and a CMakeLists.txt.in, a FastPFORConfig.cmake configuration template, a pkg-config template, a modules directory, a scripts directory, a data directory, a tools directory, a unit test directory, an MSVC directory for the Visual Studio build, and a Travis configuration and an AppVeyor configuration for continuous integration on the two platforms that were common when that was set up.

The headers and source are separated into their own directories, which is what lets the library be consumed as a header plus compiled component, and the example file in the root is a single file rather than a directory of examples, which again says something about the intended use:

example.cpp

The library is header heavy in the sense that the codecs are templates over the integer type, so the bulk of the code is instantiated in your translation unit rather than called into a shared library.

Editorial conclusion

FastPFOR suits a team that stores large integer columns, whether in a search index, a column store or an inverted index, and that is willing to treat the codec as a low-level primitive rather than a library with a friendly API. It is a poor fit if you need input validation, since the library assumes trusted buffers, and a poor fit if your data is sorted and you want the intersection algorithms, because that work belongs to a different library. Before you adopt it, read the security section and put your own integrity check on the path, check that your compiler still supports the C++11 baseline the project chose deliberately, and benchmark the specific codec against your own value distribution rather than trusting a headline number.

Frequently asked questions

Official sources

1. fast-pack/FastPFOR on GitHub
2. License: Apache-2.0
3. Project website
4. README
5. Releases