TurboPFor-Integer-Compression

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),
  • :new:(2023.04) Rust Bindings. Access TurboPFor incl. SSE/AVX2/Neon! from Rust
  • :+1: Java Critical Natives/JNI. Access TurboPFor incl. SSE/AVX2/Neon! 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
• 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.
• Bit Packing
  • Fastest and most efficient "SIMD Bit Packing" >20 Billions integers/sec (80Gb/s!)
  • Extremely fast scalar "Bit Packing"
  • 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,xor,...
  • :new:(2023.03)TurboBitByte novel hybrid scheme combining the fastest SIMD codecs TurboByte+TurboPack. Compress considerably better and can be 3 times faster than streamvbyte
• 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
• :new:(2023.03)TurboVLC novel variable length encoding for large integers with exponent + variable bit mantissa
• :new:(2023.03)Binary interpolative coding : fastest implementation

• Transform
  • Scalar & SIMD Transform: Delta, Zigzag, Zigzag of delta, XOR,
  • :new:(2023.03) Transpose/Shuffle with integrated Xor and zigzag delta
  • :new:(2023.03) 2D/3D/4D transpose
  • lossy floating point compression with TurboPFor or TurboTranspose+lz77/bwt
• :new:(2023.03)IC Codecs transpose/rle + general purpose compression with lz4,zstd,turborc (range coder),bwt...

• Floating Point Compression
  • Delta/Zigzag + improved gorilla style + (Differential) Finite Context Method FCM/DFCM floating point compression
  • Using TurboPFor, unsurpassed compression and more than 8 GB/s throughput
  • Point wise relative error bound lossy floating point compression
  • TurboFloat novel efficient floating point compression using TurboPFor
  • :new:(2023.03)TurboFloat LzXor novel floating point lempel-ziv compression
  • :new:(2023.06) _Float16 16 bits floating point support
  • :new:(2023.06) float 16/32/64 bits quantization with variable quantization bit size.
• Time Series Compression
  • Fastest Gorilla 16/32/64 bits style compression (zigzag of delta + RLE).
  • can compress timestamps 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, ...

Integer Compression Benchmark (single thread):

• Download IcApp a new benchmark for TurboPFor
  for testing allmost all integer and floating point file types. ( type: icapp ZIPF )
• Benchmark: TurboTranspose+iccodecs vs Quantile Compression
• Benchmark: TurboByte+TurboBitByte vs streamvbtyte
• Benchmark: Time Series - TurboPFor, TurboFloat, TurboFloat LzX, TurboGorilla,...
• Benchmark: Lossy Floating Point Preprocessing Turbo Razor vs Granular bitround vs libroundfast
• Benchmark: Lossless/Lossy Floating Point Compression. TurboPFor vs zfp & blosc
• Benchmark: TurboPFor: IcApp 16 bits Integer Compression
• Benchmark Intel CPU: Skylake i7-6700 3.4GHz gcc 9.2
• Benchmark ARM: ARMv8 A73-ODROID-N2 1.8GHz

- 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.

   ./icapp -a1.5 -m0 -M255 -n100M ZIPF
  

(*) 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

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

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

- Time Series:

• Test file Timestamps: ts.txt(sorted)

    ./icapp -Ft ts.txt -I15 -J15