Home

Awesome

LittleIntPacker

C library to pack and unpack short arrays of integers as fast as possible

Introduction

This is a bit packing library. Bit packing is the process by which you take arrays of (32-bit) integers that fit in [0,2^L) and you write them out using as close to L bits per integer as possible.

Motivation

For long blocks of integers (e.g., 128 integers or more), SIMD bit packing is ideal. See for example https://github.com/lemire/simdcomp where blocks of 128 integers are packed and unpacked very fast.

However, what happens if you have small blocks having variable lengths, and lengths that are typically much smaller than 128 integers?

The work is motivated by the engineering underlying TurboPFor https://github.com/powturbo/TurboPFor That is, we write and load compressed bytes in 64-bit words as opposed to 32-bit words.

Hardware requirements

This software makes little sense if you do not have a 64-bit processor.

Usage

make
./unit

Code usage

//#include "bitpacking.h

// number of bytes required to compress l 32-bit integers using b bits each
uint32_t c = byte_count(l, b);

// packing an array of 32-bit unsigned ints from data to buffer
turbopack32(data, l, b,buffer);
// recovering data
turbounpack32(buffer, l, b,backdata);

Current status

Tested.

References

Other relevant libraries