TurboPFor: Fastest Integer Compression

======================================

  • TurboPFor: The synonym for “integer compression”
    • ALL functions available for AMD/Intel, 64 bits ARMv8 NEON Linux+MacOS/M1 & Power9 Altivec
    • 100% C (C++ headers), as simple as memcpy. OS:Linux amd64, arm64, Power9, MacOs (Amd/intel + Apple M1),
    • :+1: Java Critical Natives/JNI. Access TurboPFor incl. SIMD/AVX2! from Java as fast as calling from C
    • :sparkles: FULL range 8/16/32/64 bits scalar + 16/32/64 bits SIMD functions
    • No other “Integer Compression” compress/decompress faster
    • :sparkles: Direct Access, integrated (SIMD/AVX2) FOR/delta/Delta of Delta/Zigzag for sorted/unsorted arrays
    • 16 bits + 64 bits SIMD integrated functions
  • For/PFor/PForDelta
    • Novel TurboPFor (PFor/PForDelta) scheme w./ direct access + SIMD/AVX2. +RLE
    • Outstanding compression/speed. More efficient than ANY other fast “integer compression” scheme.
    • Compress 70 times faster and decompress up to 4 times faster than OptPFD
  • Bit Packing
    • Fastest and most efficient “SIMD Bit Packing” 15 Billions integers/sec (60Gb/s!)
    • Scalar “Bit Packing” decoding nearly as fast as SIMD-Packing in realistic (No “pure cache”) scenarios
    • Direct/Random Access : Access any single bit packed entry with zero decompression
  • Variable byte
    • Scalar “Variable Byte” faster and more efficient than ANY other implementation
    • SIMD TurboByte fastest group varint (16+32 bits) incl. integrated delta,zigzag,...
    • TurboByte+TurboPackV novel hybrid scheme combining the fastest SIMD codecs.
  • Simple family
    • Novel “Variable Simple” (incl. RLE) faster and more efficient than simple16, simple-8b
  • Elias fano
    • Fastest “Elias Fano” implementation w/ or w/o SIMD/AVX2
  • Transform
    • Scalar & SIMD Transform: Delta, Zigzag, Zigzag of delta, XOR, Transpose/Shuffle,
    • lossy floating point compression with TurboPFor or TurboTranspose+lz77
  • Floating Point Compression
    • Delta/Zigzag + improved gorilla style + (Differential) Finite Context Method FCM/DFCM floating point compression
    • Using TurboPFor, unsurpassed compression and more than 5 GB/s throughput
    • Point wise relative error bound lossy floating point compression
    • TurboFloat novel efficient floating point compression using TurboPFor
  • Time Series Compression
    • Fastest Gorilla 16/32/64 bits style compression (zigzag of delta + RLE).
    • can compress times series to only 0.01%. Speed > 10 GB/s compression and > 13 GB/s decompress.
  • Inverted Index ...do less, go fast!
    • Direct Access to compressed frequency and position data w/ zero decompression
    • Novel “Intersection w/ skip intervals”, decompress the minimum necessary blocks (~10-15%)!.
    • Novel Implicit skips with zero extra overhead
    • Novel Efficient Bidirectional Inverted Index Architecture (forward/backwards traversal) incl. “integer compression”.
    • more than 2000! queries per second on GOV2 dataset (25 millions documents) on a SINGLE core
    • :sparkles: Revolutionary Parallel Query Processing on Multicores > 7000!!! queries/sec on a simple quad core PC.
      ...forget Map Reduce, Hadoop, multi-node clusters, ...

Promo video

Integer Compression Benchmark (single thread):

- Synthetic data:

  • Generate and test (zipfian) skewed distribution (100.000.000 integers, Block size=128/256)
    Note: Unlike general purpose compression, a small fixed size (ex. 128 integers) is in general used in “integer compression”. Large blocks involved, while processing queries (inverted index, search engines, databases, graphs, in memory computing,...) need to be entirely decoded.

     ./icbench -a1.5 -m0 -M255 -n100M ZIPF
C Sizeratio%Bits/IntegerC MB/sD MB/sName 2019.11
62,939,88615.75.04236910950TurboPFor256
63,392,75915.85.0713597803TurboPFor128
63,392,80115.85.071328924TurboPForDA
65,060,50416.35.20602748FP_SIMDOptPFor
65,359,91616.35.23322436PC_OptPFD
73,477,08818.45.884082484PC_Simple16
73,481,09618.45.886248748FP_SimdFastPFor 64Ki *
76,345,13619.16.1110722878VSimple
91,947,53323.07.3628411737QMX 64k *
93,285,86423.37.46156810232FP_GroupSimple 64Ki *
95,915,09624.07.678483832Simple-8b
99,910,93025.07.991729812408TurboByte+TurboPack
99,910,93025.07.991735712363TurboPackV sse
99,910,93025.07.991169410138TurboPack scalar
99,910,93025.07.9984208876TurboFor
100,332,92925.18.031707711170TurboPack256V avx2
101,015,65025.38.081119110333TurboVByte
102,074,66325.58.1766899524MaskedVByte
102,074,66325.58.1722604208PC_Vbyte
102,083,03625.58.1752004268FP_VByte
112,500,00028.19.00152812140VarintG8IU
125,000,00031.210.001303912366TurboByte
125,000,00031.210.001119711984StreamVbyte 2019
400,000,000100.0032.0089608948Copy
N/AN/AEliasFano

(*) codecs inefficient for small block sizes are tested with 64Ki integers/block.

  • MB/s: 1.000.000 bytes/second. 1000 MB/s = 1 GB/s
  • #BOLD = pareto frontier.
  • FP=FastPFor SC:simdcomp PC:Polycom
  • TurboPForDA,TurboForDA: Direct Access is normally used when accessing few individual values.
  • Eliasfano can be directly used only for increasing sequences
- Data files:

  • gov2.sorted from DocId data set Block size=128/Delta coding

     ./icbench -fS -r gov2.sorted

Speed/Ratio

SizeRatio %Bits/IntegerC Time MB/sD Time MB/sFunction 2019.11
3,321,663,89313.94.4413206088TurboPFor
3,339,730,55714.04.47322144PC.OptPFD
3,350,717,95914.04.4815367128TurboPFor256
3,501,671,31414.64.68562840VSimple
3,768,146,46715.85.0432283652EliasFanoV
3,822,161,88516.05.115722444PC_Simple16
4,411,714,93618.45.90930410444TurboByte+TurboPack
4,521,326,51818.96.058363296Simple-8b
4,649,671,42719.46.2230843848TurboVbyte
4,955,740,04520.76.63706410268TurboPackV
4,955,740,04520.76.6357248020TurboPack
5,205,324,76021.86.9669529488SC_SIMDPack128
5,393,769,50322.57.211446611902TurboPackV256
6,221,886,39026.08.3266686952TurboFor
6,221,886,39026.08.3266442260TurboForDA
6,699,519,00028.08.9618881980FP_Vbyte
6,700,989,56328.08.9627403384MaskedVByte
7,622,896,87831.910.208364792VarintG8IU
8,060,125,03533.711.5084569476Streamvbyte 2019
8,594,342,21635.911.5052286376libfor
23,918,861,764100.032.0058245924Copy

Block size: 64Ki = 256k bytes. Ki=1024 Integers

SizeRatio %Bits/IntegerC Time MB/sD Time MB/sFunction
3,164,940,56213.24.2313446004TurboPFor 64Ki
3,273,213,46413.74.3814967008TurboPFor256 64Ki
3,965,982,95416.65.3015202452lz4+DT 64Ki
4,234,154,42717.75.664365672qmx 64Ki
6,074,995,11725.48.1319762916blosc_lz4 64Ki
8,773,150,64436.711.7425485204blosc_lz 64Ki

“lz4+DT 64Ki” = Delta+Transpose from TurboPFor + lz4
“blosc_lz4” internal lz4 compressor+vectorized shuffle

- Time Series:
FunctionC MB/ssizeratio%D MB/sText
bvzenc321063245,9090.00812823ZigZag
bvzzenc32891456,7130.01013499ZigZag Delta of delta
vsenc3212294140,4000.02412877Variable Simple
p4nzenc256v321932596,0180.1013326TurboPFor256 ZigZag
p4ndenc256v321961596,0180.1013339TurboPFor256 Delta
bitndpack256v3212564909,1890.1613505TurboPackV256 Delta
p4nzenc3218101,159,6330.208502TurboPFor ZigZag
p4nzenc128v3217951,159,6330.2013338TurboPFor ZigZag
bitnzpack256v3296511,254,7570.2213503TurboPackV256 ZigZag
bitnzpack128v32101551,472,8040.2613380TurboPackV ZigZag
vbddenc32619818,057,2963.1310982TurboVByte Delta of delta
memcpy13397577,141,992100.00
- Transpose/Shuffle (no compression)
    ./icbench -eTRANSFORM ZIPF
SizeC Time MB/sD Time MB/sFunction
100,000,00094009132TPbyte 4 TurboPFor Byte Transpose/shuffle AVX2
100,000,00087848860TPbyte 4 TurboPFor Byte Transpose/shuffle SSE
100,000,00076887656Blosc_Shuffle AVX2
100,000,00052047460TPnibble 4 TurboPFor Nibble Transpose/shuffle SSE
100,000,00066206284Blosc shuffle SSE
100,000,00031563372Bitshuffle AVX2
100,000,00021002176Bitshuffle SSE
- (Lossy) Floating point compression:
    ./icapp -Fd file          " 64 bits floating point raw file 
    ./icapp -Ff file          " 32 bits floating point raw file 
    ./icapp -Fcf file         " text file with miltiple entries (ex.  8.657,56.8,4.5 ...)
    ./icapp -Ftf file         " text file (1 entry per line)
    ./icapp -Ftf file -v5     " + display the first entries read
    ./icapp -Ftf file.csv -K3 " but 3th column in a csv file (ex. number,Text,456.5 -> 456.5
    ./icapp -Ftf file -g.001  " lossy compression with allowed pointwise relative error 0.001
- Compressed Inverted Index Intersections with GOV2

GOV2: 426GB, 25 Millions documents, average doc. size=18k.

  • Aol query log: 18.000 queries
    ~1300 queries per second (single core)
    ~5000 queries per second (quad core)
    Ratio = 14.37% Decoded/Total Integers.

  • TREC Million Query Track (1MQT):
    ~1100 queries per second (Single core)
    ~4500 queries per second (Quad core CPU)
    Ratio = 11.59% Decoded/Total Integers.

  • Benchmarking intersections (Single core, AOL query log)
max.docid/qTime sq/sms/q% docid found
1.0007.882283.10.43881
10.00010.541708.50.58584
ALL13.961289.00.776100
q/s: queries/second, ms/q:milliseconds/query
  • Benchmarking Parallel Query Processing (Quad core, AOL query log)
max.docid/qTime sq/sms/q% docids found
1.0002.666772.60.14881
10.0003.395307.50.18884
ALL3.575036.50.199100
Notes:

Compile:

    Download or clone TurboPFor
	git clone git://github.com/powturbo/TurboPFor.git
	cd TurboPFor
	make
    

    To benchmark external libraries + lz77 compression:
	git clone --recursive git://github.com/powturbo/TurboPFor.git
	cd TurboPFor
    make CODEC1=1 CODEC2=1 LZ=1
Windows visual c++
	nmake /f makefile.vs
Windows visual studio c++
    project files under vs/vs2017

Testing:

- Synthetic data (use ZIPF parameter):

  • benchmark groups of “integer compression” functions 

    ./icbench -eBENCH -a1.2 -m0 -M255 -n100M ZIPF
./icbench -eBITPACK/VBYTE -a1.2 -m0 -M255 -n100M ZIPF

Type “icbench -l1” for a list

-zipfian distribution alpha = 1.2 (Ex. -a1.0=uniform -a1.5=skewed distribution)
-number of integers = 100.000.000
-integer range from 0 to 255

  • Unsorted lists: individual function test (ex. Copy TurboPack TurboPFor)

    ./icbench -a1.5 -m0 -M255 -ecopy/turbopack/turbopfor/turbopack256v ZIPF

  • Unsorted lists: Zigzag encoding w/ option -fz or FOR encoding

    ./icbench -fz -eturbovbyte/turbopfor/turbopackv ZIPF
./icbench -eturboforv ZIPF

  • Sorted lists: differential coding w/ option -fs (increasing) or -fS (strictly increasing)

    ./icbench -fs -eturbopack/turbopfor/turbopfor256v ZIPF

  • Generate interactive “file.html” plot for browsing

    ./icbench -p2 -S2 -Q3 file.tbb

  • Unit test: test function from bit size 0 to 32

    ./icbench -m0 -M32 -eturbpfor -fu 
./icbench -m0 -M8 -eturbopack -fs -n1M
- Data files:

  • Raw 32 bits binary data file Test data

    ./icbench file
./icapp file           
./icapp -Fs file         "16 bits raw binary file
./icapp -Fu file         "32 bits raw binary file
./icapp -Fl file         "64 bits raw binary file
./icapp -Ff file         "32 bits raw floating point binary file
./icapp -Fd file         "64 bits raw floating point binary file

  • Text file: 1 entry per line. Test data: ts.txt(sorted) and lat.txt(unsorted))

    ./icbench -eBENCH -fts ts.txt
./icbench -eBENCH -ft  lat.txt

./icapp -Fts data.txt            "text file, one 16 bits integer per line
./icapp -Ftu ts.txt              "text file, one 32 bits integer per line
./icapp -Ftl ts.txt              "text file, one 64 bits integer per line
./icapp -Ftf file                "text file, one 32 bits floating point (ex. 8.32456) per line
./icapp -Ftd file                "text file, one 64 bits floating point (ex. 8.324567789) per line
./icapp -Ftd file -v5            "like prev., display the first 100 values read
./icapp -Ftd file -v5 -g.00001   "like prev., error bound lossy floating point compression
./icapp -Ftt file                "text file, timestamp in seconds iso-8601 -> 32 bits integer (ex. 2018-03-12T04:31:06)
./icapp -FtT file                "text file, timestamp in milliseconds iso-8601 -> 64 bits integer (ex. 2018-03-12T04:31:06.345)
./icapp -Ftl -D2 -H file         "skip 1th line, convert numbers with 2 decimal digits to 64 bits integers (ex. 456.23 -> 45623)
./icapp -Ftl -D2 -H -K3 file.csv  "like prev., use the 3th number in the line (ex. label=3245, text=99 usage=456.23 -> 456.23 )
./icapp -Ftl -D2 -H -K3 -k| file.csv "like prev., use '|' as separator

  • Text file: multiple numbers separated by non-digits (0..9,-,.) characters (ex. 134534,-45678,98788,4345, )

    ./icapp -Fc data.txt         "text file, 32 bits integers (ex. 56789,3245,23,678 ) 
./icapp -Fcd data.txt        "text file, 64 bits floting-point numbers (ex. 34.7689,5.20,45.789 )

  • Multiblocks of 32 bits binary file. (Example gov2 from DocId data set)
    Block format: [n1: #of Ids][Id1] [Id2]...[IdN] [n2: #of Ids][Id1][Id2]...[IdN]...

    ./icbench -fS -r gov2.sorted
- Intersections:

1 - Download Gov2 (or ClueWeb09) + query files (Ex. “1mq.txt”) from DocId data set
8GB RAM required (16GB recommended for benchmarking “clueweb09” files).

2 - Create index file

    ./idxcr gov2.sorted .

create inverted index file “gov2.sorted.i” in the current directory

3 - Test intersections

    ./idxqry gov2.sorted.i 1mq.txt

run queries in file “1mq.txt” over the index of gov2 file

- Parallel Query Processing:

1 - Create partitions

    ./idxseg gov2.sorted . -26m -s8

create 8 (CPU hardware threads) partitions for a total of ~26 millions document ids

2 - Create index file for each partition

  ./idxcr gov2.sorted.s*

create inverted index file for all partitions “gov2.sorted.s00 - gov2.sorted.s07” in the current directory

3 - Intersections:

delete “idxqry.o” file and then type “make para” to compile “idxqry” w. multithreading

  ./idxqry gov2.sorted.s*.i 1mq.txt

run queries in file “1mq.txt” over the index of all gov2 partitions “gov2.sorted.s00.i - gov2.sorted.s07.i”.

Function usage:

See benchmark “icbench” program for “integer compression” usage examples. In general encoding/decoding functions are of the form:

char *endptr = encode( unsigned *in, unsigned n, char *out, [unsigned start], [int b])
endptr : set by encode to the next character in “out” after the encoded buffer
in : input integer array
n : number of elements
out : pointer to output buffer
b : number of bits. Only for bit packing functions
start : previous value. Only for integrated delta encoding functions

char *endptr = decode( char *in, unsigned n, unsigned *out, [unsigned start], [int b])
endptr : set by decode to the next character in “in” after the decoded buffer
in : pointer to input buffer
n : number of elements
out : output integer array
b : number of bits. Only for bit unpacking functions
start : previous value. Only for integrated delta decoding functions

Simple high level functions:

size_t compressed_size = encode( unsigned *in, size_t n, char *out)
compressed_size : number of bytes written into compressed output buffer out

size_t compressed_size = decode( char *in, size_t n, unsigned *out)
compressed_size : number of bytes read from compressed input buffer in

Function syntax:

  • {vb | p4 | bit | vs}[n][d | d1 | f | fm | z ]{enc/dec | pack/unpack}[| 128V | 256V][8 | 16 | 32 | 64]:
    vb: variable byte
    p4: turbopfor
    vs: variable simple
    bit: bit packing
    n : high level array functions for large arrays.

    '' : encoding for unsorted integer lists
    ‘d’ : delta encoding for increasing integer lists (sorted w/ duplicate)
    ‘d1’: delta encoding for strictly increasing integer lists (sorted unique)
    ‘f’ : FOR encoding for sorted integer lists
    ‘z’ : ZigZag encoding for unsorted integer lists

    ‘enc’ or ‘pack’ : encode or bitpack
    ‘dec’ or ‘unpack’: decode or bitunpack
    ‘NN’ : integer size (8/16/32/64)

header files to use with documentation:

c/c++ header fileInteger Compression functionsexamples
vint.hvariable bytevbenc32/vbdec32 vbdenc32/vbddec32 vbzenc32/vbzdec32
vsimple.hvariable simplevsenc64/vsdec64
vp4.hTurboPForp4enc32/p4dec32 p4denc32/p4ddec32 p4zenc32/p4zdec32
bitpack.hBit Packing, For, +Direct Accessbitpack256v32/bitunpack256v32 bitforenc64/bitfordec64
eliasfano.hElias Fanoefanoenc256v32/efanoc256v32

Note: Some low level functions (like p4enc32) are limited to 128/256 (SSE/AVX2) integers per call.

Environment:

OS/Compiler (64 bits):
  • Windows: MinGW-w64 makefile
  • Windows: Visual c++ (>=VS2008) - makefile.vs (for nmake)
  • Windows: Visual Studio project file - vs/vs2017 - Thanks to PavelP
  • Linux amd64: GNU GCC (>=4.6)
  • Linux amd64: Clang (>=3.2)
  • Linux arm64: 64 bits aarch64 ARMv8: gcc (>=6.3)
  • Linux arm64: 64 bits aarch64 ARMv8: clang
  • MaxOS: XCode (>=9)
  • MaxOS: Apple M1 (Clang)
  • PowerPC ppc64le (incl. SIMD): gcc (>=8.0)
Multithreading:
  • All TurboPFor integer compression functions are thread safe

References:

Last update: 13 Nov 2021

APPENDIX: icbench Integer Compression Benchmark

TurboPFor + external libraries
Functions integrated into ‘icbench’ for benchmarking