Fastest Integer Compression

Overview

TurboPFor: Fastest Integer Compression Build Status

  • TurboPFor: The new synonym for "integer compression"
    • 🆕 (2019.11) ALL functions now available for 64 bits ARMv8 NEON & Power9 Altivec
    • 100% C (C++ headers), as simple as memcpy. OS:Linux amd64, arm64, Power9, MacOs
    • 👍 Java Critical Natives/JNI. Access TurboPFor incl. SIMD/AVX2! from Java as fast as calling from C
    • FULL range 8/16/32/64 bits scalar + 16/32/64 bits SIMD functions
    • No other "Integer Compression" compress/decompress faster
    • 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" 10 Billions integers/sec (40Gb/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
    • 🆕 (2019.11) SIMD TurboByte fastest group varint (16+32 bits) incl. integrated delta,zigzag,...
    • 🆕 (2019.11) 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
    • 🆕 (2019.11) 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
    • 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 Size ratio% Bits/Integer C MB/s D MB/s Name 2019.11
62,939,886 15.7 5.04 2369 10950 TurboPFor256
63,392,759 15.8 5.07 1359 7803 TurboPFor128
63,392,801 15.8 5.07 1328 924 TurboPForDA
65,060,504 16.3 5.20 60 2748 FP_SIMDOptPFor
65,359,916 16.3 5.23 32 2436 PC_OptPFD
73,477,088 18.4 5.88 408 2484 PC_Simple16
73,481,096 18.4 5.88 624 8748 FP_SimdFastPFor 64Ki *
76,345,136 19.1 6.11 1072 2878 VSimple
91,947,533 23.0 7.36 284 11737 QMX 64k *
93,285,864 23.3 7.46 1568 10232 FP_GroupSimple 64Ki *
95,915,096 24.0 7.67 848 3832 Simple-8b
99,910,930 25.0 7.99 17298 12408 TurboByte+TurboPack
99,910,930 25.0 7.99 17357 12363 TurboPackV sse
99,910,930 25.0 7.99 11694 10138 TurboPack scalar
99,910,930 25.0 7.99 8420 8876 TurboFor
100,332,929 25.1 8.03 17077 11170 TurboPack256V avx2
101,015,650 25.3 8.08 11191 10333 TurboVByte
102,074,663 25.5 8.17 6689 9524 MaskedVByte
102,074,663 25.5 8.17 2260 4208 PC_Vbyte
102,083,036 25.5 8.17 5200 4268 FP_VByte
112,500,000 28.1 9.00 1528 12140 VarintG8IU
125,000,000 31.2 10.00 13039 12366 TurboByte
125,000,000 31.2 10.00 11197 11984 StreamVbyte 2019
400,000,000 100.00 32.00 8960 8948 Copy
N/A N/A EliasFano

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

Size Ratio % Bits/Integer C Time MB/s D Time MB/s Function 2019.11
3,321,663,893 13.9 4.44 1320 6088 TurboPFor
3,339,730,557 14.0 4.47 32 2144 PC.OptPFD
3,350,717,959 14.0 4.48 1536 7128 TurboPFor256
3,501,671,314 14.6 4.68 56 2840 VSimple
3,768,146,467 15.8 5.04 3228 3652 EliasFanoV
3,822,161,885 16.0 5.11 572 2444 PC_Simple16
4,411,714,936 18.4 5.90 9304 10444 TurboByte+TurboPack
4,521,326,518 18.9 6.05 836 3296 Simple-8b
4,649,671,427 19.4 6.22 3084 3848 TurboVbyte
4,955,740,045 20.7 6.63 7064 10268 TurboPackV
4,955,740,045 20.7 6.63 5724 8020 TurboPack
5,205,324,760 21.8 6.96 6952 9488 SC_SIMDPack128
5,393,769,503 22.5 7.21 14466 11902 TurboPackV256
6,221,886,390 26.0 8.32 6668 6952 TurboFor
6,221,886,390 26.0 8.32 6644 2260 TurboForDA
6,699,519,000 28.0 8.96 1888 1980 FP_Vbyte
6,700,989,563 28.0 8.96 2740 3384 MaskedVByte
7,622,896,878 31.9 10.20 836 4792 VarintG8IU
8,060,125,035 33.7 11.50 8456 9476 Streamvbyte 2019
8,594,342,216 35.9 11.50 5228 6376 libfor
23,918,861,764 100.0 32.00 5824 5924 Copy

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

Size Ratio % Bits/Integer C Time MB/s D Time MB/s Function
3,164,940,562 13.2 4.23 1344 6004 TurboPFor 64Ki
3,273,213,464 13.7 4.38 1496 7008 TurboPFor256 64Ki
3,965,982,954 16.6 5.30 1520 2452 lz4+DT 64Ki
4,234,154,427 17.7 5.66 436 5672 qmx 64Ki
6,074,995,117 25.4 8.13 1976 2916 blosc_lz4 64Ki
8,773,150,644 36.7 11.74 2548 5204 blosc_lz 64Ki

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

- Time Series:
Function C MB/s size ratio% D MB/s Text
bvzenc32 10632 45,909 0.008 12823 ZigZag
bvzzenc32 8914 56,713 0.010 13499 ZigZag Delta of delta
vsenc32 12294 140,400 0.024 12877 Variable Simple
p4nzenc256v32 1932 596,018 0.10 13326 TurboPFor256 ZigZag
p4ndenc256v32 1961 596,018 0.10 13339 TurboPFor256 Delta
bitndpack256v32 12564 909,189 0.16 13505 TurboPackV256 Delta
p4nzenc32 1810 1,159,633 0.20 8502 TurboPFor ZigZag
p4nzenc128v32 1795 1,159,633 0.20 13338 TurboPFor ZigZag
bitnzpack256v32 9651 1,254,757 0.22 13503 TurboPackV256 ZigZag
bitnzpack128v32 10155 1,472,804 0.26 13380 TurboPackV ZigZag
vbddenc32 6198 18,057,296 3.13 10982 TurboVByte Delta of delta
memcpy 13397 577,141,992 100.00
- Transpose/Shuffle (no compression)
    ./icbench -eTRANSFORM ZIPF
Size C Time MB/s D Time MB/s Function
100,000,000 9400 9132 TPbyte 4 TurboPFor Byte Transpose/shuffle AVX2
100,000,000 8784 8860 TPbyte 4 TurboPFor Byte Transpose/shuffle SSE
100,000,000 7688 7656 Blosc_Shuffle AVX2
100,000,000 5204 7460 TPnibble 4 TurboPFor Nibble Transpose/shuffle SSE
100,000,000 6620 6284 Blosc shuffle SSE
100,000,000 3156 3372 Bitshuffle AVX2
100,000,000 2100 2176 Bitshuffle 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/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:

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

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)
  • PowerPC ppc64le (incl. SIMD): gcc (>=8.0)
Multithreading:
  • All TurboPFor integer compression functions are thread safe

References:

Last update: 20 Aug 2020

APPENDIX: icbench Integer Compression Benchmark

TurboPFor + external libraries
TurboPFor               	https://github.com/powturbo/TurboPFor
FastPFor (FP)              	https://github.com/lemire/FastPFor
lz4				https://github.com/Cyan4973/lz4
LittleIntPacker (LI)       	https://github.com/lemire/LittleIntPacker
MaskedVbyte             	http://maskedvbyte.org
Polycom (PC)               	https://github.com/encode84/bcm
simdcomp (SC)              	https://github.com/lemire/simdcomp
Simple-8b optimized     	https://github.com/powturbo/TurboPFor
Streamvbyte             	https://github.com/lemire/streamvbyte
VarintG8IU              	https://github.com/lemire/FastPFor
Functions integrated into 'icbench' for benchmarking
Codec group:
TURBOPFOR        TurboPFor library TurboPFor256V/TurboPack256V/TurboPFor256N/TurboPFor/TurboPackV/TurboVByte/TurboPack/TurboForDA/EliasFano/VSimple/TurboPForN/TurboPackN/TurboPForDI
DEFAULT          Default TurboPFor/TurboPackV/TurboVByte/TurboPack/TurboFor/TurboPForN/TurboPackN/TurboPForDI/TurboPFor256V/TurboPack256V/TurboPFor256N
BENCH            Benchmark TurboPFor/TurboPackV/TurboVByte/TurboPack/QMX/FP.SimdFastPfor/FP.SimdOptPFor/MaskedVbyte/StreamVbyte
EFFICIENT        Efficient TurboPFor/vsimple/turbovbyte
TRANSFORM        transpose/shufle,delta,zigzag tpbyte4s/tpbyte,4/tpnibble,4/ZigZag_32/Delta_32/BitShuffle,4
BITPACK          Bit Packing TurboPack256V/TurboPackV/TurboPackH/TurboPack/SC.SimdPack128/SC.SimdPack256
VBYTE            Variable byte TurboVByte/FP.VByte/PC.Vbyte/VarintG8IU/MaskedVbyte/StreamVbyte
SIMPLE           Simple Family simple8b/simple16/vsimple/qmx
LZ4              lz4+bitshufle/transpose 4,8 lz4_bitshufle/lz4_tp4/lz4_tp8
LI               Little Integer LI_Pack/LI_TurboPack/LI_SuperPack/LI_HorPack


Function         Description                                      level

--------         -----------                                      -----
TurboPFor        PFor (SSE2)
TurboPForN       PFor (SSE2) large blocks
TurboPFor256     PFor (AVX2)
TurboPFor256N    PFor (AVX2) large blocks
TurboPForDA      PFor direct access
TurboPForDI      PFord min
TurboPForZZ      PFor zigzag of delta
TurboFor         FOR
TurboForV        FOR (SIMD)
TurboFor256V     FOR (AVX2)
TurboForDA       FOR direct access
TurboPackDA      Bit packing direct access
TurboPack        Bit packing (scalar)
TurboPackN       Bit packing (scalar) large blocks
TurboPackV       Bit packing (SSE2 Vertical)
TurboPackH       Bit packing (SSE2 Horizontal)
TurboPackVN      Bit packing (SSE2 large block)
TurboPack256V    Bit packing (AVX2 Vertical)
TurboPack256N    Bit packing (AVX2 large block)
TurboVByte       Variable byte (scalar)
VSimple          Variable simple (scalar)
EliasFano        Elias fano (scalar)
EliasFanoV       Eliasfano  (SSE2)
EliasFano256V    Elias fano (AVX2)
memcpy           memcpy
copy             Integer copy
tpbyte4s         Byte Transpose (scalar)
tpbyte           Byte transpose (simd)  2,4,8
tpnibble         Nibble transpose (simd)  2,4,8
ZigZag32         ZigZag encoding (sse2)
Delta32          Delta encoding (sse2)
DDelta32         Delta of delta encoding (sse2)
Xor32            Xor encoding (sse2)
FP_PREV64        Floating point PFOR
FP_FCM64         Floating point PFOR (FCM)
FP_DFCM64        Floating point PFOR (DFCM)
TurboPFor64      PFOR 64
TurboPFor64V     PFOR 64
Simple8b         64 bits Simple family (instable)
PC_Simple16      Simple 16. limited to 28 bits
PC_OptPFD        OptPFD. limited to 28 bits
PC_Vbyte         Variable byte
PC_Rice          Rice coding (instable)
VarintG8IU       Variable byte SIMD
MaskedVbyte      Variable byte SIMD
StreamVbyte      Variable byte SIMD
FP_FastPFor      PFor scalar (inefficient for small blocks)
FP_SimdFastPFor  PFor SIMD (inefficient for small blocks)
FP_OptPFor       OptPFor scalar 
FP_SIMDOptPFor   OptPFor SIMD
FP_VByte         Variable byte
FP_Simple8bRLE   Simple-8b + rle
FP_GROUPSIMPLE   Group Simple
SC_SIMDPack128   Bit packing (SSE4.1)
SC_SIMDPack256   Bit packing (SSE4.1)
SC_For           For (SSE4.1)
SC_ForDA         For direct access (SSE4.1)
LibFor_For       For
LibFor_ForDA     For direct access
LI_Pack          Bit packing (scalar)
LI_TurboPack     Bit packing (scalar)
LI_SuperPack     Bit packing (scalar)
LI_HorPack       Bit packing (sse4.1 horizontal) 
LI_BMIPack256    Bit packing (avx2)
lz4              lz4
lz4_bit          Bitshuffle + [delta]+lz4 2,4,8
lz4_nibble       TurboPFor's [delta]+nibble transpose + lz4 2,4,8
lz4_bitxor       Bitshuffle + [xor]+lz4 2,4,8
lz4_nibblexor    TurboPFor's [xor]+nibble transpose + lz4 2,4,8
lz4_byte         TurboPFor's [delta]+byte transpose + lz4 2,4,8
BitShuffle       Bit shuffle (simd) 2,4,8
Issues
  • How ist TurboPFor working?

    How ist TurboPFor working?

    Is TurboPFor a library for int compression? If yes, why does the page look like some compare tool for different libs. Put the docs/hello world right there, not the compare results. It's extremely painful to find anything how to use the lib (I hope it's wasn't assumed that users should read icbench or source of any other tool to decifir how to use the lib).

    I use visual studio, and VS build doesn't work at all. Also, that approach that some files result in multiple different output obj files doesn't help overall: it would be better if the lib had tiny wrappers that included those c-files and set required defines to modify compilation.

    Even after I made it build on VS it absolutely doesn't work and completely fails for me. I'm not even sure what function I need to use to compress. After that huge table of irrelevant info, if anybody ever gets as far as "Function usage" section, you'll see some cryptic explanation that doesn't seem to be current anymore. From that section, it seems that I need p4fmencXXX but that doesn't exist (nothing p4fm exist at all). Why is that there that pack/unpack thing doing, to confuse people? From the docs, it seems like p4packXXX should be a valid function, while it's not.

    After digging, it seem that I should try p4enc32, but so far I get stack corruption, and it doesn't seem like it could ever work at all. It crashes for me in _p4enc32 on line while(i != n) MISS; In my case I call p4enc32 with an array of 2731 uints. That while loop will clearly corrupt stack, because the MISS expands to _in[i] = in[i], that is, it will attempt to assign _in[2730] because that loop will run up to the length of the input n=2731. I don't get it, how come that code could even work, as it writes to stack array of 287 elements?! Also, it seems like there are no checks, I don't see a single assert anywhere to check/show conditions/expectations, while in that function it had to make that check!

    opened by pps83 26
  • p4nzenc256v32 sometimes produces different results

    p4nzenc256v32 sometimes produces different results

    While making some changes in my code, I tried to verify that the resulting binary data (compressed with p4nzenc256v32) is identical. To my surprise, the data had many changes as if something corrupted it. I tried to dump hex of compressed data and it clearly had a few modified bytes here and there. What's even more surprising, when I uncompressed the data using p4nzdec256v32 output from these two different buffers was identical. Any idea why, is that normal? If so, what makes it produce different outputs with identical inputs?

    opened by pps83 22
  • Hello TurboPFor

    Hello TurboPFor

    save the file as ictest.c in the TurboPFor directory and type

    make ictest ./ictest

    output: compress size is 6 uncompress size is 6

    #include <stdio.h>
    #define NTURBOPFOR_DAC
    #include "vp4.h"
    
    #define P4NENC_BOUND(n) ((n+127)/128+(n+32)*sizeof(uint32_t))
    
    int main(int argc, char* argv[]) {
          printf("Hello TurboPFor\n");
          int ar[32] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
          unsigned elnum = 10;
          unsigned char* compress_buf =  malloc(P4NENC_BOUND(elnum));
          int *uncompress_buf =  malloc((elnum+32)*sizeof(ar[0]));
      
          size_t compress_size = p4nenc32((uint32_t*)ar, elnum, compress_buf);
          printf("compress size is %lu\n", compress_size);
      
          size_t uncompress_size = p4ndec32(compress_buf, elnum, (uint32_t*)uncompress_buf);
          printf("uncompress size is %lu\n", uncompress_size);
    }
    
    opened by powturbo 17
  • SIGABRT while using p4enc64.

    SIGABRT while using p4enc64.

    #include "conf.h"
    #include "bitpack.h"
    #include "vint.h"		
    #include "bitutil.h"
    #include "vp4.h"
    
    
    typedef uint64_t LONG;
    
    
    int main(LONG argc, char** argv) {
    	LONG *array = (LONG *)malloc(sizeof(LONG)*5);
    	array[0] = 24520120;
    	array[1] = 29620120;
    	array[2] = 42420120;
    	array[3] = 20124222;
    	array[4] = 4294967295;
    
    	unsigned char* out = (unsigned char *)malloc(5*10*sizeof(unsigned char));
    	unsigned char * op = p4enc64(array, 5, out);
    	printf("%d\n",(int)(op-out) );
    	
    
    	LONG *capacity = (LONG *)malloc(sizeof(LONG)*5);
    	unsigned char * op2 =  p4dec64(out, 5, capacity);
    	printf("%d\n",(int)(op2-out) );
    
    }
    
    
    

    When attempting to use p4enc64 in above code, the following error is raised.

    malloc.c:2372: sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.

    Program received signal SIGABRT, Aborted. 0x00007ffff700dc37 in __GI_raise ([email protected]=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:56 56 ../nptl/sysdeps/unix/sysv/linux/raise.c: No such file or directory.

    No issue occurs with uint32_t and also when malloc is not used.

    Please correct me if there is any issue with the code. I am trying to use TurboPFor in my code for compressing 64-bit unsorted integer arrays. Also I am having trouble with allocating the right buffer size for the compressed array.What is the minimum buffer size I can allocate safely while using p4enc64 for integer array of size n?

    opened by jeetu-raj 9
  • Decoding speed bug introduced

    Decoding speed bug introduced

    Just to make sure it's tracked properly, decoding speed reduced by more than 10% for p4nzdec256v32 (my personal project seems to have best results with this function).

    9dad490 doesn't have the problem, 5dff9d3f has the problem. It's absolutely clearly almost 10% slower for entire test where p4nzdec256v32 connsumes perhaps 25% of the cpu time of the entire test.

    Times of my tests with these TurboPFor versions: 9dad490 - 16.605sec ~MyAlgo profiler data: image

    p4nzdec256v32 roughly takes 3.560sec (21.44% of 16.605sec)

    5dff9d3f - 17.636sec ~MyAlgo profiler data: image

    p4nzdec256v32 roughly takes 4.213sec (23.89% of 17.636sec) These tests are performed with absolutely identical code, simply TurboPFor version changed. Also, the test uses 3 threads (according to the debugger, so, actual performance hit in p4nzdec256v32 seems to be way more than 10%, and might easily be in the range of 20%-30%). Also, times were measured without profiler (just to make it clear, it was fully optimized runs of 64-bit builds of TurboPFor)

    Unfortunately, due to the way TurboPFor is managed, it's in permanently broken state and I wasn't able to bisect to find offending commit: if I try to check out anything in between, it's always broken and doesn't build with all kinds of compilation errors. I'd strongly recommend adjusting your approach: it's not suitable for projects that are worked on and used by more than one person.

    opened by pps83 8
  • Inconsistent definition of ctz64/ctz32/clz64/clz32

    Inconsistent definition of ctz64/ctz32/clz64/clz32

    ctz64 for non-windows builds is:

    for example:

    #define ctz64(x) __builtin_ctzll(x)

    while for windows it's:

    static inline int ctz64(uint64_t x) { unsigned long z; _BitScanForward64(&z, x); return x?z:64; }

    __builtin_ctzll isn't defined for x=0, however, for windows builds it does the check: x?z:64.

    https://github.com/powturbo/TurboPFor/blob/4df4bcea29b670dab3acb985aac83a7562bfa2eb/conf.h#L65

    opened by pps83 8
  • Comparison with Blosc can be improved

    Comparison with Blosc can be improved

    I have just seen your project and I see that you are using Blosc for comparison. For completeness, I would recommend to include other Blosc codecs as they give different results that may be a good fit in different scenarios.

    Below, I have selected several combinations that works well for this problem, and here are my results (Linux, GCC 4.9.2, Xeon E3-1240 v3 @ 3.40GHz):

    $ time LD_LIBRARY_PATH=/home/francesc/c-blosc/build/blosc ./icbench -a1.5 -m0 -M255 -n100m
    zipf alpha=1.50 range[0..255].n=100000000
    
    bits histogram:0:40.20% 1:14.22% 2:12.75% 3:10.28% 4:7.77% 5:5.69% 6:4.09% 7:2.92% 8:2.07%
    62064288    15.52    4.97      27.85          130.24   blosc (zlib, nthreads=1, clevel=3)
    62064288    15.52    4.97      42.85          214.16   blosc (zlib, nthreads=4, clevel=3)
    63392801    15.85    5.07     396.74         1412.46   TurboPFor
    77187330    19.30    6.17      51.44          663.17   blosc (lz4hc, nthreads=1, clevel=3)
    77187330    19.30    6.17      78.52          984.59   blosc (lz4hc, nthreads=4, clevel=3)
    101473443    25.37    8.12     862.60          896.15  blosc (lz4, nthreads=1, clevel=3)
    101473443    25.37    8.12    1193.86         1392.87  blosc (lz4, nthreads=2, clevel=3)
    101473443    25.37    8.12    1608.41         1549.34  blosc (lz4, nthreads=4, clevel=3)
    102491006    25.62    8.20     595.36         1815.32  blosc (blosclz, nthreads=1, clevel=3)
    102491006    25.62    8.20     949.23         2049.91  blosc (blosclz,  nthreads=2, clevel=3)
    102491006    25.62    8.20    1293.24         1873.03  blosc (blosclz,  nthreads=4, clevel=3)
    

    The timings with clang 3.5 are very close to these, so I am not reproducing them.

    By the way, very nice work! I did not realized that compressing integers was that important!

    opened by FrancescAlted 8
  • Remove invalid references to USE_SSE, USE_AVX2

    Remove invalid references to USE_SSE, USE_AVX2

    https://github.com/powturbo/TurboPFor/blob/5dff9d3fc120fafa13cedbc8ea0f249e8291215a/vs/vs2017/TurboPFor.vcxproj#L92

    If you remove USE_SSE & USE_AVX2, why don't you grep entire repo to see if you have left overs here and there?..

    opened by pps83 7
  • Cannot generate header jic.h

    Cannot generate header jic.h

    $ javah -jni jic or $ javah -jni jic.java
    fails - no such file. Could you please add jic.h to the repository ? So far, I've tried to make a shared library without it and succeeded with following make file: differences are added flag - -fPIC and

        #$(CC) $(OBJS) -lm -o -shared libic.so $(LFLAGS)
        $(CC) -shared -Wl,-soname,libic.so -o libic.so.1 -lm $(LFLAGS) $(OBJS)
    
    
    # Linux: "export CC=clang" windows mingw: "set CC=gcc" or uncomment one of following lines
    # CC=clang
    # CC=gcc
    
    MARCH=-march=native
    #MARCH=-msse2
    CFLAGS=-DNDEBUG -fstrict-aliasing -m64 $(MARCH) -Iext -fPIC 
    
    UNAME := $(shell uname)
    ifeq ($(UNAME), Linux)
    LIBTHREAD=-lpthread
    LIBRT=-lrt
    else
    CC=gcc
    endif
    
    BIT=./
    all: icbench idxcr idxqry idxseg libic
    
    bitpack.o: $(BIT)bitpack.c $(BIT)bitpack.h $(BIT)bitpack64_.h
        $(CC) -O2 $(CFLAGS) -c $(BIT)bitpack.c
    
    bitpackv.o: $(BIT)bitpackv.c $(BIT)bitpack.h $(BIT)bitpackv32_.h
        $(CC) -O2 $(CFLAGS) -c $(BIT)bitpackv.c
    
    vp4dc.o: $(BIT)vp4dc.c
        $(CC) -O3 $(CFLAGS) -funroll-loops -c $(BIT)vp4dc.c
    
    vp4dd.o: $(BIT)vp4dd.c
        $(CC) -O3 $(CFLAGS) -funroll-loops -c $(BIT)vp4dd.c
    
    varintg8iu.o: $(BIT)ext/varintg8iu.c $(BIT)ext/varintg8iu.h 
        $(CC) -O2 $(CFLAGS) -c -funroll-loops -std=c99 $(BIT)ext/varintg8iu.c
    
    idxqryp.o: $(BIT)idxqry.c
        $(CC) -O3 $(CFLAGS) -c $(BIT)idxqry.c -o idxqryp.o
    
    SIMDCOMPD=ext/simdcomp/
    SIMDCOMP=$(SIMDCOMPD)bitpacka.o $(SIMDCOMPD)src/simdintegratedbitpacking.o $(SIMDCOMPD)src/simdcomputil.o $(SIMDCOMPD)src/simdbitpacking.o
    
    #LIBFOR=ext/for/for.o
    MVB=ext/MaskedVByte/src/varintencode.o ext/MaskedVByte/src/varintdecode.o
    
    # Lzturbo not included
    #LZT=../lz/lz8c0.o ../lz/lz8d.o ../lz/lzbc0.o ../lz/lzbd.o
    
    # blosc. Set the env. variable "EXT=blosc" to include 
    #EXT=blosc
    ifeq ($(EXT), blosc)
    B=ext/
    CFLAGS+=-DSHUFFLE_SSE2_ENABLED -DHAVE_LZ4 -DHAVE_ZLIB -Iext/
    LFLAGS+=-lpthread 
    BLOSC=$(B)lz4hc.o $(B)c-blosc/blosc/blosc.o $(B)c-blosc/blosc/blosclz.o $(B)c-blosc/blosc/shuffle.o $(B)c-blosc/blosc/shuffle-generic.o $(B)c-blosc/blosc/shuffle-sse2.o
    endif
    
    LZ4=ext/lz4.o 
    
    #ZLIB=-lz
    
    #BSHUFFLE=ext/bitshuffle/src/bitshuffle.o
    
    OBJS=icbench.o bitutil.o vint.o bitpack.o bitunpack.o eliasfano.o vsimple.o vp4dd.o vp4dc.o varintg8iu.o bitpackv.o bitunpackv.o $(TRANSP) ext/simple8b.o transpose.o $(BLOSC) $(SIMDCOMP) $(LIBFOR) $(LZT) $(LZ4) $(MVB) $(ZLIB) $(BSHUFFLE)
    
    icbench: $(OBJS)
        $(CC) $(OBJS) -lm -o icbench $(LFLAGS)
    
    libic: $(OBJS)
        #$(CC) $(OBJS) -lm -o -shared libic.so $(LFLAGS)
        $(CC) -shared -Wl,-soname,libic.so -o libic.so.1 -lm $(LFLAGS) $(OBJS)
    
    idxseg:   idxseg.o
        $(CC) idxseg.o -o idxseg
    
    ifeq ($(UNAME), Linux)
    para: CFLAGS += -DTHREADMAX=32  
    para: idxqry
    endif
    
    idxcr:   idxcr.o bitpack.o vp4dc.o bitutil.o
        $(CC) idxcr.o bitpack.o bitpackv.o vp4dc.o bitutil.o -o idxcr $(LFLAGS)
    
    idxqry:   idxqry.o bitunpack.o vp4dd.o bitunpackv.o bitutil.o
        $(CC) idxqry.o bitunpack.o bitunpackv.o vp4dd.o bitutil.o $(LIBTHREAD) $(LIBRT) -o idxqry $(LFLAGS)
    
    .c.o:
        $(CC) -O3 $(CFLAGS) $< -c -o [email protected]
    
    .cc.o:
        $(CXX) -O3 -DNDEBUG -std=c++11 $< -c -o [email protected]
    
    .cpp.o:
        $(CXX) -O3 -DNDEBUG -std=c++11 $< -c -o [email protected]
    
    clean:
        @find . -type f -name "*\.o" -delete -or -name "*\~" -delete -or -name "core" -delete
    
    cleanw:
        del /S ..\*.o
        del /S ..\*~
    
    opened by kk00ss 7
  • Licence and others

    Licence and others

    Hello,

    First of all, sorry for my english,

    Currently, I am finishing a thesis, and your implementation is cited in the bibliography. For doing this I would like to know some data about your code,

    • What are the differences between your code (the PFOR codec) and other state-of-the-art implementations like D. Lemire et al? http://arxiv.org/pdf/1401.6399v12.pdf
      • Are the optimizations based on the implementation?, or has the algorithm changed?
    • Is this code part of any published work (e.g article, thesis, etc) which can be cited using a reference manager?
    • What is the licence of your code? (in the case it has any)

    Thank-you, Julian

    opened by rom3r4 6
  • float16 lossy compression

    float16 lossy compression

    There are padfloat32() and padfloat64(), but no padfloat16(), is it straightforward to create a float16 version based on the float32 version?

    Also, what if I do the lossy compression for float16 data using icapp -f4 -g.001 float16data?

    opened by yunhua-deng 5
  • How TurboPfor supports RandomAccess and its benchmarking script

    How TurboPfor supports RandomAccess and its benchmarking script

    Hi,

    You have demonstrated in the results that TurboPfor can reach a good compression rate with random accesses. However, I have only observed the enc/dec logic of whole blocks in the high level API in the source code.

    May I ask about what kinds of API supports sequential iteration or random access, and what are some demos using them? Also, I want to ask whether 64 bit integers are supported or not?

    Thanks a lot!

    opened by bluecat1024 0
  • P4 decompression reads out of array boundary

    P4 decompression reads out of array boundary

    We have had some segmentation violations in our software using this library which seem to be caused by the P4 decompression. The decompression algorithm (in particular the function p4nd1dec64) often seems to read outside of the boundaries of the in array that is provided. I have seen occurrences of up to 80 bytes after the in array. Please note that the algorithm never seems to use these values, so the results are valid, independent of what data is to be found after the array.

    I was already aware that the compression and decompression write to the out array in locations outside of the strictly required limits (as discussed in #26), but I wasn't aware that it also reads in out of bounds.

    It would be very helpful if there would be variants of the function that never read outside of the boundaries, even if it costs some performance. Alternatively, it would be very helpful if we at least had documentation that describes how far outside of the boundaries the functions are reading.

    How to reproduce?

    • Build and run this program (linking against the library, obviously):
    #include <cstdint>
    #include <iostream>
    #include <cassert>
    #include "vp4.h"
    
    using namespace std;
    
    int main() {
        // the original, uncompressed set
        const size_t numData = 4;
        const uint64_t data[] = { 5246L, 12601L, 15235L, 18998L };
    
        // the compressed set
        // the data array is created on the heap, so that valgrind can find when reading out of the array bounds
        const size_t compressedSize = 8;
        unsigned char* compressed = new unsigned char[compressedSize] 
            { 0x94, 0x7e, 0x0d, 0xba, 0x3c, 0x49, 0xc9, 0x3a };
    
        // the buffer for decompression (enlarged as temporary memory)
        uint64_t decompressed[numData+32];
        p4nd1dec64(compressed, numData, decompressed);
    
        // verify that the results are correct
        for (int i = 0; i < numData; i++) {
            cout 
                << "data[" << i << "]=" << data[i] 
                << " uncompressed[" << i << "]=" << decompressed[i] 
                << endl;
            assert(data[i] == decompressed[i]);
        }
    
       return 0;
    }
    
    • Run the program using valgrind, which results in the following output (on may machine):
    > valgrind ./testP4Error
    ==15779== Memcheck, a memory error detector
    ==15779== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
    ==15779== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
    ==15779== Command: ./testP4Error
    ==15779== 
    ==15779== Invalid read of size 8
    ==15779==    at 0x48E718: bitd1unpack64_13 (bitunpack_.h:3523)
    ==15779==    by 0x409D9F: p4nd1dec64 (vp4d.c:477)
    ==15779==    by 0x40129C: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779==  Address 0x5a25043 is 3 bytes inside a block of size 8 alloc'd
    ==15779==    at 0x4C2AC38: operator new[](unsigned long) (vg_replace_malloc.c:433)
    ==15779==    by 0x401246: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779== 
    ==15779== Invalid read of size 8
    ==15779==    at 0x48E754: bitd1unpack64_13 (bitunpack_.h:3523)
    ==15779==    by 0x409D9F: p4nd1dec64 (vp4d.c:477)
    ==15779==    by 0x40129C: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779==  Address 0x5a2504b is 3 bytes after a block of size 8 alloc'd
    ==15779==    at 0x4C2AC38: operator new[](unsigned long) (vg_replace_malloc.c:433)
    ==15779==    by 0x401246: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779== 
    ==15779== Invalid read of size 8
    ==15779==    at 0x48E7D7: bitd1unpack64_13 (bitunpack_.h:3523)
    ==15779==    by 0x409D9F: p4nd1dec64 (vp4d.c:477)
    ==15779==    by 0x40129C: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779==  Address 0x5a25053 is 11 bytes after a block of size 8 alloc'd
    ==15779==    at 0x4C2AC38: operator new[](unsigned long) (vg_replace_malloc.c:433)
    ==15779==    by 0x401246: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779== 
    ==15779== Invalid read of size 8
    ==15779==    at 0x48E85B: bitd1unpack64_13 (bitunpack_.h:3523)
    ==15779==    by 0x409D9F: p4nd1dec64 (vp4d.c:477)
    ==15779==    by 0x40129C: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779==  Address 0x5a2505b is 19 bytes after a block of size 8 alloc'd
    ==15779==    at 0x4C2AC38: operator new[](unsigned long) (vg_replace_malloc.c:433)
    ==15779==    by 0x401246: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779== 
    ==15779== Invalid read of size 8
    ==15779==    at 0x48E8E2: bitd1unpack64_13 (bitunpack_.h:3523)
    ==15779==    by 0x409D9F: p4nd1dec64 (vp4d.c:477)
    ==15779==    by 0x40129C: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779==  Address 0x5a25063 is 19 bytes after a block of size 16 in arena "client"
    ==15779== 
    ==15779== Invalid read of size 8
    ==15779==    at 0x48E975: bitd1unpack64_13 (bitunpack_.h:3523)
    ==15779==    by 0x409D9F: p4nd1dec64 (vp4d.c:477)
    ==15779==    by 0x40129C: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779==  Address 0x5a2506b is 27 bytes after a block of size 16 in arena "client"
    ==15779== 
    ==15779== Invalid read of size 4
    ==15779==    at 0x48E9FB: bitd1unpack64_13 (bitunpack_.h:3523)
    ==15779==    by 0x409D9F: p4nd1dec64 (vp4d.c:477)
    ==15779==    by 0x40129C: main (in /data/rpm/v93rnd_libic/src/test/testP4Error)
    ==15779==  Address 0x5a25073 is 29 bytes before an unallocated block of size 4,194,128 in arena "client"
    ==15779== 
    data[0]=5246 uncompressed[0]=5246
    data[1]=12601 uncompressed[1]=12601
    data[2]=15235 uncompressed[2]=15235
    data[3]=18998 uncompressed[3]=18998
    ==15779== 
    ==15779== HEAP SUMMARY:
    ==15779==     in use at exit: 8 bytes in 1 blocks
    ==15779==   total heap usage: 1 allocs, 0 frees, 8 bytes allocated
    ==15779== 
    ==15779== LEAK SUMMARY:
    ==15779==    definitely lost: 8 bytes in 1 blocks
    ==15779==    indirectly lost: 0 bytes in 0 blocks
    ==15779==      possibly lost: 0 bytes in 0 blocks
    ==15779==    still reachable: 0 bytes in 0 blocks
    ==15779==         suppressed: 0 bytes in 0 blocks
    ==15779== Rerun with --leak-check=full to see details of leaked memory
    ==15779== 
    ==15779== For lists of detected and suppressed errors, rerun with: -s
    ==15779== ERROR SUMMARY: 7 errors from 7 contexts (suppressed: 0 from 0)
    
    opened by olenz 1
  • TurboPFor fails to build with latest VS 2022 compiler

    TurboPFor fails to build with latest VS 2022 compiler

    These are the errors:

    1>bitutil.h(193,31): warning C4391: 'uint16_t _mm_cvtsi128_si16(__m128i)': incorrect return type for intrinsic function, expected 'short' (compiling source file ..\..\bitpack.c)
    1>bitutil.h(193,60): error C2169: '_mm_cvtsi128_si16': intrinsic function, cannot be defined (compiling source file ..\..\bitpack.c)
    
    opened by pps83 1
  • a bug in icapp.c:1014

    a bug in icapp.c:1014

    #define MINDELTA(t, in, n, dmin) {
    t *_p = (t *)in, _i;
    for(dmin = (t)-1, _i = 1; _i < n; _i++)
    if(_p[_i] < _p[_i-1]) { dmin = (t)-1; break; }
    else { t _d = _p[_i] - _p[_i-1]; if(_d < dmin) { dmin = _d; /printf("[%u]", dmin);/} }
    } Note that, the type of n is unsigned, while t may be uint8_t. That is to say, 0\leq _i \leq 255, which leads to that the loop will never end. I think the type of _i should be the same as that of n.

    opened by BeeBreeze 0
Owner
powturbo
Turbo Data Compression, InformationRetrieval. InvertedIndex, Integer Compression, InMemoryDB, SIMD, Data Structures, Algorithms, BigData, Databases
powturbo
TurboRLE-Fastest Run Length Encoding

TurboRLE: Turbo Run Length Encoding Efficient and fastest Run Length Encoding library ?? The fastest now up to 50% more faster incl. SSE/AVX2 + improv

powturbo 235 May 17, 2022
Brotli compression format

SECURITY NOTE Please consider updating brotli to version 1.0.9 (latest). Version 1.0.9 contains a fix to "integer overflow" problem. This happens when

Google 11.2k Jun 24, 2022
Superfast compression library

DENSITY Superfast compression library DENSITY is a free C99, open-source, BSD licensed compression library. It is focused on high-speed compression, a

Centaurean 974 Jun 30, 2022
data compression library for embedded/real-time systems

heatshrink A data compression/decompression library for embedded/real-time systems. Key Features: Low memory usage (as low as 50 bytes) It is useful f

Atomic Object 1.1k Jun 30, 2022
Heavily optimized zlib compression algorithm

Optimized version of longest_match for zlib Summary Fast zlib longest_match function. Produces slightly smaller compressed files for significantly fas

Konstantin Nosov 117 May 10, 2022
Small strings compression library

SMAZ - compression for very small strings ----------------------------------------- Smaz is a simple compression library suitable for compressing ver

Salvatore Sanfilippo 984 Jun 20, 2022
Compression abstraction library and utilities

Squash - Compresion Abstraction Library

null 362 Jun 6, 2022
Multi-format archive and compression library

Welcome to libarchive! The libarchive project develops a portable, efficient C library that can read and write streaming archives in a variety of form

null 1.8k Jun 25, 2022
Analysing and implementation of lossless data compression techniques like Huffman encoding and LZW was conducted along with JPEG lossy compression technique based on discrete cosine transform (DCT) for Image compression.

PROJECT FILE COMPRESSION ALGORITHMS - Huffman compression LZW compression DCT Aim of the project - Implement above mentioned compression algorithms an

null 1 Dec 14, 2021
Arbitrary Precision provides C++ long integer types that behave as basic integer types. This library aims to be intuitive and versatile in usage, rather than fast.

Arbitrary Precision (AP) Cross-platform and cross-standard header-only arbitrary precision arithmetic library. Currently it offers integer types that

null 15 May 19, 2022
Przemyslaw Skibinski 549 Jun 22, 2022
MIRACL Cryptographic SDK: Multiprecision Integer and Rational Arithmetic Cryptographic Library is a C software library that is widely regarded by developers as the gold standard open source SDK for elliptic curve cryptography (ECC).

MIRACL What is MIRACL? Multiprecision Integer and Rational Arithmetic Cryptographic Library – the MIRACL Crypto SDK – is a C software library that is

MIRACL 482 Jun 24, 2022
LibTomMath is a free open source portable number theoretic multiple-precision integer library written entirely in C.

libtommath This is the git repository for LibTomMath, a free open source portable number theoretic multiple-precision integer (MPI) library written en

libtom 520 Jun 25, 2022
MIRACL Cryptographic SDK: Multiprecision Integer and Rational Arithmetic Cryptographic Library is a C software library that is widely regarded by developers as the gold standard open source SDK for elliptic curve cryptography (ECC).

MIRACL What is MIRACL? Multiprecision Integer and Rational Arithmetic Cryptographic Library – the MIRACL Crypto SDK – is a C software library that is

MIRACL 483 Jun 27, 2022
A C++11 large integer library with effective high performance, simplistic in nature and also clean in the eyes.

BigIntegerCPP BigIntegerCPP is a C++11 port of large integer library used in CryptoLib4Pascal. It allows mostly parsing of numbers as strings in diffe

Telepati 25 Apr 22, 2022
Faster Non-Integer Sample Rate Conversion

Non-Integer Sample Rate Conversion This repository contains a comparison of sample-rate conversion (SRC) algorithms, with an emphasis on performance f

null 23 Mar 6, 2022
Long integer arithmetic.

LongInt Содержимое репозитория представляет из себя исходный код примитивного консольного калькулятора, который использует реализацию длинных чисел из

null 10 Jun 27, 2022
Simple long integer math library for C++

SLIMCPP Simple long integer math library for C++ SLIMCPP is C++ header-only library that implements long integers that exceed maximum size of native t

null 19 May 19, 2022
IntX is a C++11 port of IntX arbitrary precision Integer library with speed, about O(N * log N) multiplication/division algorithms implementation.

IntX IntX is a C++11 port of IntX arbitrary precision Integer library with speed, about O(N * log N) multiplication/division algorithms implementation

Telepati 9 Mar 9, 2022
C implementation of C++ Utility functions Integer Comparison Macros

C implementation of C++ Utility functions Integer Comparison Macros

Robert C. Seacord 15 May 27, 2022
Muriqui Optimizer - A convex mixed integer nonlinear programming solver

Muriqui Optimizer Muriqui Optimizer is a solver for convex Mixed Integer Nonlinear Programming (MINLP) problems. For more informations and user manual

null 4 Jan 21, 2022
SCIP - Solving Constraint Integer Programs

SCIP: Solving Constraint Integer Programs Welcome to what is currently one of the fastest academically developed solvers for mixed integer programming

scipopt 118 Jun 21, 2022
wideint is a C++ implementation of wide exact-width integer types.

wideint - wide exact-width integer types Copyright (c) 2022 Joergen Ibsen About wideint is a C++ implementation of wide exact-width integer types. #in

Jørgen Ibsen 3 Jan 27, 2022
Arduino library for DHT sensors - integer only

DHTINT Arduino library for DHT sensors - integer only Description This is an experimental integer only library, based upon - https://github.com/RobTil

Rob Tillaart 5 Jun 16, 2022
The fastest feature-rich C++11/14/17/20 single-header testing framework

master branch Windows All dev branch Windows All doctest is a new C++ testing framework but is by far the fastest both in compile times (by orders of

Viktor Kirilov 4k Jun 23, 2022
Jsmn is a world fastest JSON parser/tokenizer. This is the official repo replacing the old one at Bitbucket

JSMN jsmn (pronounced like 'jasmine') is a minimalistic JSON parser in C. It can be easily integrated into resource-limited or embedded projects. You

Serge Zaitsev 3k Jun 28, 2022
TurboRLE-Fastest Run Length Encoding

TurboRLE: Turbo Run Length Encoding Efficient and fastest Run Length Encoding library ?? The fastest now up to 50% more faster incl. SSE/AVX2 + improv

powturbo 235 May 17, 2022
The fastest feature-rich C++11/14/17/20 single-header testing framework

master branch Windows All dev branch Windows All doctest is a new C++ testing framework but is by far the fastest both in compile times (by orders of

Viktor Kirilov 4k Jul 1, 2022
hashcat is the world's fastest and most advanced password recovery utility

hashcat is the world's fastest and most advanced password recovery utility, supporting five unique modes of attack for over 300 highly-optimized hashing algorithms. hashcat currently supports CPUs, GPUs, and other hardware accelerators on Linux, Windows, and macOS, and has facilities to help enable distributed password cracking.

null 14.8k Jun 30, 2022