C++ C Other
Permalink
Failed to load latest commit information.
ext IcBench: External libs Feb 22, 2017
java TurboPFor: Java Critical Natives Jan 29, 2017
.gitattributes . Feb 4, 2017
.gitmodules . Jan 8, 2017
.travis.yml . Jan 8, 2017
README.md Readme Feb 26, 2017
bitpack.c TurboPFor: Bit Packing Feb 26, 2017
bitpack.h TurboPFor: Bit Pack/UnPack c/c++ header Jan 29, 2017
bitpack_.h TurboPFor: Bit Pack include Jan 29, 2017
bitunpack.c TurboPFor: Bit Unpacking Feb 26, 2017
bitunpack_.h TurboPFor: Bit UnPack include Feb 26, 2017
bitutil.c BitUtil: Delta, ZigZag, NumBits, Floating Point,... Feb 26, 2017
bitutil.h BitUtil: c/c++ header Feb 26, 2017
conf.h TurboPFor: Config/Platform Jan 15, 2017
eliasfano.c TurboPFor: Elias fano encode/decode Jan 29, 2017
eliasfano.h TurboPFor: Elias fano c/c++ header Jan 21, 2017
fp.c TurboPFor: Floating Point encode/decode Feb 26, 2017
fp.h TurboPFor: Floating Point c/c++ header Feb 26, 2017
icbench.c IcBench: Benchmark App Feb 26, 2017
idx.h Inverted index: header for idxcr/idxqry Jan 4, 2017
idxcr.c Inverted Index: Indexing Jan 29, 2017
idxqry.c Inverted Index: Query Processing Jan 8, 2017
idxseg.c Inverted Index: Partioning/Sharding App Jan 4, 2017
jic.c TurboPFor: Java Critical Natives Interface Jan 29, 2017
makefile IcBench: Makefile Feb 26, 2017
plugins.cc IcBench: Integer Compression codecs Feb 26, 2017
plugins.h IcBench: Integer Compression codecs include Feb 4, 2017
transpose.c Transform: Byte+Nibble Transpose/Shuffle Feb 26, 2017
transpose.h Transform: Byte+Nibble Transpose/Shuffle header Feb 26, 2017
vint.c TurboPFor: Variable byte encode/decode Feb 26, 2017
vint.h TurboPFor: Variable byte c/c++ header Feb 26, 2017
vp4.h TurboPFor: TurboPFor encode/decode c/c++ header Feb 26, 2017
vp4c.c TurboPFor: TurboPFor encode Feb 26, 2017
vp4d.c TurboPFor: TurboPFor decode Feb 26, 2017
vsimple.c TurboPFor: Variable simple encode/decode Jan 5, 2017
vsimple.h TurboPFor: Variable simple header Jan 4, 2017

README.md

TurboPFor: Fastest Integer Compression Build Status

  • TurboPFor: The new synonym for "integer compression"
    • 100% C (C++ headers), as simple as memcpy
    • πŸ‘ Java Critical Natives/JNI. Access TurboPFor incl. SIMD/AVX2! from Java as fast as calling from C
    • ✨ FULL range 8/16/32/64 bits lists
    • No other "Integer Compression" compress/decompress faster
    • ✨ Direct Access, integrated (SIMD/AVX2) FOR/delta/Zigzag for sorted/unsorted arrays

  • For/PFor/PForDelta
    • Novel "TurboPFor" (PFor/PForDelta) scheme w./ direct access.
    • 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
    • πŸ†• TurboPFor AVX2, now 50%! more faster!!!!
    • πŸ†• TurboPFor Hybrid, better compression and more faster

  • Bit Packing
    • ✨ Fastest and most efficient "SIMD Bit Packing"
    • πŸ†• TurboPack AVX2 more faster. Decoding 10 Billions intergers/seconds (40Gb/s)
    • πŸ†• more faster. Scalar "Bit Packing" decoding 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 than ANY other (incl. SIMD) implementation
    • πŸ†• new scheme : better compression and 30% faster

  • 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, Transpose/Shuffle

  • Floating Point Compression
    • πŸ†• (Differential) Finite Context Method FCM/DFCM floating point compression
    • Using TurboPFor, more than 2 GB/s throughput

  • 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
    • ✨ Revolutionary Parallel Query Processing on Multicores w/ more than 7000!!! queries/sec on a simple quad core PC.
      ...forget Map Reduce, Hadoop, multi-node clusters, ...

Integer Compression Benchmark:

  • Practical (No PURE cache) "integer compression" benchmark w/ large arrays.
  • CPU: Skylake i7-6700 3.4GHz gcc 6.2 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 Size ratio% Bits/Integer C MI/s D MI/s Name
62939886 15.7 5.04 397 2311 TurboPFor256
63392759 15.8 5.07 330 1608 TurboPFor
63392801 15.8 5.07 332 231 TurboPForDA
65060504 16.3 5.20 15 687 FP.SIMDOptPFor
65359916 16.3 5.23 8 609 PC.OptPFD
73477088 18.4 5.88 102 621 PC.Simple16
73481096 18.4 5.88 156 2187 FP.SimdFastPFor 64k *
76345136 19.1 6.11 245 653 VSimple
91956582 25.5 8.15 65 2141 QMX 64k *
95915096 24.0 7.67 212 958 Simple-8b
99910930 25.0 7.99 3290 2968 TurboPackV
99910930 25.0 7.99 2367 2351 TurboPack
99910930 25.0 7.99 2105 2219 TurboFor
100332929 25.1 8.03 3580 2998 TurboPack256V
101015650 25.3 8.08 2380 2371 TurboVByte
102074663 25.5 8.17 1428 1979 MaskedVByte
102074663 25.5 8.17 565 1052 PC.Vbyte
102083036 25.5 8.17 1300 1067 FP.VByte
112500000 28.1 9.00 382 3035 VarintG8IU
125000000 31.2 10.00 1111 2948 StreamVbyte
400000000 100.00 32.00 2240 2237 Copy
N/A N/A EliasFano

(*) codec efficient only for large block size

MI/s: 1.000.000 integers/second. 1000 MI/s = 4 GB/s
#BOLD = pareto frontier.
FP=FastPFor SC:simdcomp PC:Polycom
TurboPForDA,TurboForDA: Direct Access is normally used when accessing few individual values.


- Data files:
  • gov2.sorted from DocId data set Block size=128/Delta coding

    ./icbench -fS -r gov2.sorted
    

Speed/Ratio

Size Ratio % Bits/Integer C Time MI/s D Time MI/s Function
3.321.663.893 13.9 4.44 330 1522 TurboPFor
3.339.730.557 14.0 4.47 8 536 PC.OptPFD
3.350.717.959 14.0 4.48 365 1752 TurboPFor256
3.501.671.314 14.6 4.68 314 710 VSimple
3.768.146.467 15.8 5.04 807 913 EliasFanoV
3.822.161.885 16.0 5.11 143 611 PC.Simple16
4.521.326.518 18.9 6.05 209 824 Simple-8b
4.649.671.427 19.4 6.22 771 962 TurboVbyte
4.955.740.045 20.7 6.63 1766 2567 TurboPackV
4.955.740.045 20.7 6.63 1431 2005 TurboPack
5.205.324.760 21.8 6.96 1738 2372 SC.SIMDPack128
5.393.769.503 22.5 7.21 2261 2715 TurboPackV256
6.221.886.390 26.0 8.32 1667 1738 TurboFor
6.221.886.390 26.0 8.32 1661 565 TurboForDA
6.699.519.000 28.0 8.96 472 495 FP.Vbyte
6.700.989.563 28.0 8.96 685 846 MaskedVByte
7.622.896.878 31.9 10.20 209 1198 VarintG8IU
8.594.342.216 35.9 11.50 1307 1594 libfor
23.918.861.764 100.0 32.00 1456 1481 Copy

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

Size Ratio % Bits/Integer C Time MI/s D Time MI/s Function
3.164.940.562 13.2 4.23 336 1501 TurboPFor 64Ki
3.273.213.464 13.7 4.38 374 1752 TurboPFor256 64Ki
3.965.982.954 16.6 5.30 380 613 lz4+DT 64Ki
6.074.995.117 25.4 8.13 494 729 blosc_lz4 64Ki
8.773.150.644 36.7 11.74 637 1301 blosc_lz 64Ki

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

- Transpose/Shuffle (no compression)
    ./icbench -eTRANSFORM ZIPF
Size C Time MI/s D Time MI/s Function
100000000 2350 2283 TPbyte 4 TurboPFor Byte Transpose/shuffle AVX2
100000000 2196 2215 TPbyte 4 TurboPFor Byte Transpose/shuffle SSE
100000000 1922 1914 Blosc_Shuffle AVX2
100000000 1301 1865 TPnibble 4 TurboPFor Nibble Transpose/shuffle SSE
100000000 1655 1571 Blosc shuffle SSE
100000000 789 843 Bitshuffle AVX2
100000000 525 544 Bitshuffle SSE
- 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/q Time s q/s ms/q % docid found
1.000 7.88 2283.1 0.438 81
10.000 10.54 1708.5 0.585 84
ALL 13.96 1289.0 0.776 100

q/s: queries/second, ms/q:milliseconds/query

  • Benchmarking Parallel Query Processing (Quad core, AOL query log)
max.docid/q Time s q/s ms/q % docids found
1.000 2.66 6772.6 0.148 81
10.000 3.39 5307.5 0.188 84
ALL 3.57 5036.5 0.199 100
Notes:

Compile:

    git clone --recursive git://github.com/powturbo/TurboPFor.git
    cd TurboPFor
    make

    or

    make AVX2=1

    Minimum build w/ TurboPFor scalar functions
    make NSIMD=1

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 
    ./icbench -m0 -M8 -eturbopack -fs -n1M 
    
- Data files:
  • Raw 32 bits binary data file Test data

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

    ./icbench -eBENCH -fts ts.txt
    ./icbench -eBENCH -ft  lat.txt
    
  • 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}[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

    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
    fm: FOR encoding for unsorted integer lists
    z: ZigZag encoding for unsorted integer lists

    enc/pack: encode
    dec/unpack:decode
    XX : integer size (8/16/32/64)

header files to use with documentation:

c/c++ header file Integer Compression functions examples
vint.h variable byte vbenc32/vbdec32 vbdenc32/vbddec32 vbzenc32/vbzdec32
vsimple.h variable simple vsenc64/vsdec64
vp4.h TurboPFor p4enc32/p4dec32 p4denc32/p4ddec32 p4zenc32/p4zdec32
bitpack.h Bit Packing, For, +Direct Access bitpack256v32/bitunpack256v32 bitforenc64/bitfordec64
eliasfano.h Elias Fano efanoenc256v32/efanoc256v32

Environment:

OS/Compiler (64 bits):
  • Linux: GNU GCC (>=4.6)
  • clang (>=3.2)
  • Windows: MinGW-w64 (no parallel query processing)
Multithreading:
  • All TurboPFor integer compression functions are thread safe

References:

Last update: 26 FEB 2017