simdcomp packs 128 integers at a time and leaves the file format to you

The assumption the whole library rests on

simdcomp is a simple C library for compressing lists of integers using binary packing and SIMD instructions, and it states its assumption up front.

The assumption is either that you have a list of 32-bit integers where most of them are small, or a list of 32-bit integers where differences between successive integers are small. The README is blunt about the limit: no software is able to reliably compress an array of 32-bit random numbers.

That is the entire scope of the library, and being explicit about it is a sign of a well understood problem. Bit packing stores each value in the minimum number of bits its magnitude requires, so a run of small values in 32-bit slots collapses dramatically, and a sorted run collapses even further once the differences are small.

The performance claim is stated as a decode rate. The library can decode at least 4 billions of compressed integers per second on most desktop or laptop processors, which is a rate of 15 GB/s, and it says this is significantly faster than generic codecs like gzip, LZO, Snappy or LZ4.

The comparison with those codecs is the point. Snappy and LZ4 are byte-level codecs that find repeated sequences, and they are excellent at that. They are not the right tool for an array of small integers that has no repeated byte patterns, because the redundancy is in the unused high bits of each word rather than in repeated substrings.

On a Skylake Intel processor the README reports 0.3 cycles per integer to decode, which it says can easily translate into more than 8 decoded billions integers per second.

Two backends, one API, selected at compile time

The library runs on both x86 and x64 using SSE, with optional AVX2 and AVX-512 code paths, and on 64-bit ARM with NEON, such as Apple Silicon. The public API is identical on both and is selected automatically at compile time, so the same source, including the __m128i-based entry points, builds on either architecture.

The ARM support is implemented by the project itself. The SSE intrinsics used by the 128-bit kernels are mapped onto ARM NEON by a small, self-contained shim that ships with the library in include/neon128.h. It is described as their own code written directly against arm_neon.h, with no third-party translation layer such as sse2neon pulled in. The wider AVX2 and AVX-512 paths are x86-only and simply inactive on ARM.

The requirements are specific. On x86 and x64 the processor should support SSE4.1, supported by most Intel and AMD processors released since 2008, although the core bit-packing functions only require SSE2, Pentium 4 or better. On ARM it needs an AArch64 processor with NEON. The build needs a C99 or better compiler, a C++17 compiler if you build the benchmarks, and CMake 3.14 or better.

The AVX2 and AVX-512 paths are enabled automatically when you build with -march=native on a capable host, and the CMake option -DSIMDCOMP_NATIVE=OFF turns that off. That flag is the one to know about if you are cross-compiling or building a portable binary, since -march=native produces a binary tied to the build machine.

Packing a block of 128 integers

Compression works over blocks of 128 integers, and the core call takes the bit width and writes b 128-bit words for 128 32-bit inputs.

const uint32_t b = maxbits(datain);// computes bit width
simdpackwithoutmask(datain, buffer, b);//compressed to buffer, compressing 128 32-bit integers down to b*32 bytes
simdunpack(buffer, backbuffer, b);//uncompressed to backbuffer

While 128 32-bit integers are read, only b 128-bit words are written, so the compression ratio is 32/b. That single line is the clearest statement of what the library does: a value that fits in 8 bits is stored in 8 bits, and 128 of them occupy the space of 32 32-bit words.

The variant used is called withoutmask because it does not reserve a bit per value to hold a length prefix. That matters for the difference between the block-oriented and length-oriented APIs, and it is why the general-purpose entry point is the one below.

For arrays of arbitrary length there is a separate set of functions, and the example is worth reading because it shows the allocation pattern.

int compress_decompress_demo() {
  size_t k, N = 9999;
  __m128i * endofbuf;
  uint32_t * datain = malloc(N * sizeof(uint32_t));
  uint8_t * buffer;
  uint32_t * backbuffer = malloc(N * sizeof(uint32_t));
  uint32_t b;

  for (k = 0; k < N; ++k){        /* start with k=0, not k=1! */
    datain[k] = k;
  }

  b = maxbits_length(datain, N);
  buffer = malloc(simdpack_compressedbytes(N,b)); // allocate just enough memory
  endofbuf = simdpack_length(datain, N, (__m128i *)buffer, b);
  /* compressed data is stored between buffer and endofbuf using (endofbuf-buffer)*sizeof(__m128i) bytes */
  /* would be safe to do : buffer = realloc(buffer,(endofbuf-(__m128i *)buffer)*sizeof(__m128i)); */
  simdunpack_length((const __m128i *)buffer, N, backbuffer, b);

  for (k = 0; k < N; ++k){
    if(datain[k] != backbuffer[k]) {
      printf("bug\n");
      return -1;
    }
  }
  return 0;
}

Two details in there are easy to get wrong. The length functions return an end pointer rather than a length, so the compressed size is computed from the pointer difference, and the buffer is allocated with simdpack_compressedbytes to hold the worst case. The comment about reallocating is a suggestion for tightening the allocation once the real size is known.

Differential coding for sorted data, and frame of reference

The second mode handles sorted lists, and the mechanism is differential coding: storing the difference between successive integers. For this an initial value is needed, called the offset.

uint32_t offset = 0;
uint32_t b1 = simdmaxbitsd1(offset,datain); // bit width
simdpackwithoutmaskd1(offset, datain, buffer, b1);//compressing 128 32-bit integers down to b1*32 bytes
simdunpackd1(offset, buffer, backbuffer, b1);//uncompressed

The gain is obvious once you see it. A sorted list of timestamps or identifiers has small differences, so the values that need storing are the differences rather than the values, and the differences need far fewer bits. The offset carries the absolute position, so you can recover the original values exactly rather than only their relative positions.

The third mode is frame-of-reference, in the simdfor.h header. The README says these functions work like the bit packing routines but do not use differential coding, which allows faster search in some cases at the expense of compression.

That trade is the interesting one for database use. If you need to find the position of a value in a sorted block quickly, frame-of-reference keeps the values close to their true magnitudes so a comparison narrows the range faster, whereas differential coding would require reconstructing the differences to compare them.

So the library offers three encoding strategies and the choice depends on whether you are optimising for size, for search speed, or for raw throughput on unsorted data.

Building it and consuming it from CMake

The library builds with CMake, and the three commands cover build, test and install.

cmake -B build
cmake --build build
ctest --test-dir build        # run the unit tests

Installing the library, headers and a CMake package configuration is one more command.

cmake --install build --prefix /your/install/prefix

Once installed, another CMake project consumes it with find_package and the namespaced target.

find_package(simdcomp REQUIRED)
target_link_libraries(myapp PRIVATE simdcomp::simdcomp)

Or you can vendor it with FetchContent, with no install needed.

include(FetchContent)
FetchContent_Declare(simdcomp
  GIT_REPOSITORY https://github.com/lemire/simdcomp.git
  GIT_TAG master)
FetchContent_MakeAvailable(simdcomp)
target_link_libraries(myapp PRIVATE simdcomp::simdcomp)

The useful CMake options are named in the README. SIMDCOMP_BUILD_BENCHMARKS=OFF turns off the benchmarks, which pull in lemire/counters for cycle-accurate timing and require C++17. SIMDCOMP_BUILD_TESTS=OFF skips the tests, and SIMDCOMP_NATIVE=OFF disables -march=native.

The benchmark reports CPU cycles per integer using hardware performance counters when they are available, and otherwise falls back to wall-clock time and throughput.

./build/bitpackingbenchmark        # on Apple Silicon/Linux, run with sudo for cycle counts

Running with sudo is what makes the hardware counters available on Linux, which is a detail that explains why a benchmark reporting cycles per integer would otherwise show much coarser numbers.

There is a complete working example in example/example.c, run after building as ./build/example, and a go/ folder with a simple demo for Go users.

Where simdcomp is the wrong choice

Four cases argue against it.

The first is data that does not fit the assumption. The README states it directly: no software is able to reliably compress an array of 32-bit random numbers. If your integers are full-range and unsorted, this library will produce output the same size as the input and cost you a lot of CPU doing it.

The second is if you want a compression format rather than a primitive. By design the library does not define a compressed format, and the README says it is up to the sophisticated user to create one. That means you have to specify the bit width, the block boundaries, the offset and any header yourself, and design a format that survives a change of those choices.

The third is portability to a platform without SIMD. There is no scalar fallback for the SIMD kernels, and the requirement is SSE4.1 on x86 or NEON on AArch64. For a library intended to be portable, the plain C version mentioned in the README, LittleIntPacker by the same author, is the alternative.

The alternative in the same direction is a general-purpose integer codec such as varint encoding for the storage path, or Gorilla or a similar scheme in a columnar format. The difference in approach is that simdcomp is a set of hand-written SIMD kernels for a specific shape of data, and it will beat a general codec by a wide margin on its target workload, while a general codec works on anything and needs no format design. For a database column where the values are dense small integers, simdcomp is the right tool. For a mixed workload with occasional compression, a general scheme is.

Editorial conclusion

simdcomp fits a systems programmer writing a storage engine or a database column codec who needs to compress integer arrays at memory speed and is prepared to define the container format themselves. It does not fit anyone wanting a drop-in compression codec, because the README states that by design the library does not define a compressed format. Build it with CMake, require SSE4.1 on x86 or NEON on AArch64, and keep in mind that the claimed decode rates of 4 billion integers per second or 15 GB/s apply to data whose values or differences are small, not to random 32-bit data.

Frequently asked questions

Official sources

1. fast-pack/simdcomp on GitHub
2. License: BSD-3-Clause
3. Project website
4. README
5. Releases