Research
Security News
Malicious npm Packages Inject SSH Backdoors via Typosquatted Libraries
Socket’s threat research team has detected six malicious npm packages typosquatting popular libraries to insert SSH backdoors.
github.com/powturbo/turbopfor-integer-compression
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
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.
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
Test file Timestamps: ts.txt(sorted)
./icapp -Ft ts.txt -I15 -J15
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 |
./icapp -e117,118,119 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 |
./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
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.
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 |
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 |
Download or clone TurboPFor
git clone https://github.com/powturbo/TurboPFor-Integer-Compression.git
cd TurboPFor-Integer-Compression
make
To benchmark TurboPFor + general purpose compression codecs (zstd,lz4, Turbo-Range-Coder, bwt, bitshuffle):
git clone --recursive https://github.com/powturbo/TurboPFor-Integer-Compression.git
cd TurboPFor-Integer-Compression
make ICCODEC=1
To benchmark external libraries:
Download the external libraries from github into the current directory
Activate/deactivate the ext. libs in the makefile
make CODEC1=1 CODEC2=1 ICCODEC=1
nmake /f makefile.vs
project files under vs/vs2022
benchmark groups of "integer compression" functions
./icapp -a1.2 -m0 -M255 -n100M ZIPF
./icapp -a1.2 -m0 -M255 -n100M ZIPF -e20-50
-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
./icapp -a1.5 -m0 -M255 -e1,2,3 ZIPF
Unsorted lists: Zigzag encoding
./icapp -e10,11,12 ZIPF
Sorted lists: differential coding (increasing/strictly increasing)
./icapp -e4,5,6 ZIPF
./icapp -e7,8,9 ZIPF
Transpose/RLE/TurboVByte + General purpose compressor (lz,zstd,turborc,bwt...)
./icapp file -e80-95
./icapp file -e80-95 -Ezstd,15
./icapp file -e80-95 -Eturborc,1
./icapp file -e80-95 -Eturborc,20
2D/3D/4D Transpose + General purpose compressor (lz,zstd,turborc,...)
./icapp file512x128.f32 R512x128 -Ff
./icapp file512x128.f32 -R512x128 -Ff -e100,101,102
./icapp file1024x512x128.f32 -R1024x512x128 -Ff -e100,101,102
Automatic dimension determination from file name ( option -R0 )
./icapp file1024x512x128.f32 -R0 -Ff -e103,104,105
./icapp file1024x512x128.f64 -R0 -Fl -e103,104,105
Lossy floating point compression
./icapp file512x128.f32 -R512x128 -Ff -g.0001
./icapp file.f32 -Ff -g.001
./icapp file.f64 -Fd -g.001
Raw 32 bits binary data file Test data
./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))
./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 )
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
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".
See benchmark "icapp" 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
{vb | p4 | bit | vs | v8 | bic }[n][d | d1 | f | fm | z ]{enc/dec | pack/unpack}[| 128v | 256v][8 | 16 | 32 | 64]:
vb: variable byte
p4: turbopfor
vs: variable simple
v8: TurboByte SIMD + Hybrid TurboByte + TurboPack
bit: bit packing
fp: Floating Point + Turbo Razor: pointwise relative error rounding algorithm
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)
public header file to use with documentation:
include/ic.h
Note: Some low level functions (like p4enc32) are limited to 128/256 (SSE/AVX2) integers per call.
Applications:
Benchmark references:
Integer compression publications:
Last update: 10 JUN 2023
FAQs
Unknown package
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Research
Security News
Socket’s threat research team has detected six malicious npm packages typosquatting popular libraries to insert SSH backdoors.
Security News
MITRE's 2024 CWE Top 25 highlights critical software vulnerabilities like XSS, SQL Injection, and CSRF, reflecting shifts due to a refined ranking methodology.
Security News
In this segment of the Risky Business podcast, Feross Aboukhadijeh and Patrick Gray discuss the challenges of tracking malware discovered in open source softare.