simdcomp

A simple C library for compressing lists of integers

Requirements

• Your processor should support SSE2 (Pentium4 or better)
• C99 compliant compiler (GCC is assumed)
• A Linux-like distribution is assumed by the makefile

Usage

Compression works over blocks of 128 integers.

1. Lists of integers in random order.

    const uint32_t b = maxbits(datain);// computes bit width
    simdpackwithoutmask(datain, buffer, b);//compressed to buffer
    simdunpack(buffer, backbuffer, b);//uncompressed to backbuffer
   

While 128 32-bit integers are read, only b 128-bit words are written. Thus, the compression ratio is 32/b.

2. Sorted lists of integers.

We used differential coding: we store the difference between successive integers. For this purpose, we need an initial value (called offset).

    uint32_t offset = 0; 
    uint32_t b1 = simdmaxbitsd1(offset,datain); // bit width
    simdpackwithoutmaskd1(offset, datain, buffer, b1);//compressed
    simdunpackd1(offset, buffer, backbuffer, b1);//uncompressed

Setup

make make test

and if you are daring:

make install

Go

If you are a go user, there is a "go" folder where you will find a simple demo.

Other libraries

FastPFOR is a C++ research library well suited to compress unsorted arrays: https://github.com/lemire/FastPFor

SIMDCompressionAndIntersection is a C++ research library well suited for sorted arrays (differential coding) and computing intersections: https://github.com/lemire/SIMDCompressionAndIntersection

References

Daniel Lemire and Leonid Boytsov, Decoding billions of integers per second through vectorization, Software: Practice & Experience, 2013. http://dx.doi.org/10.1002/spe.2203

Daniel Lemire, Leonid Boytsov, Nathan Kurz, SIMD Compression and the Intersection of Sorted Integers http://arxiv.org/abs/1401.6399