simdcomp
version 0.1.1
Eine einfache C-Bibliothek zum Komprimieren von Ganzzahllisten mithilfe von Binärpackungs- und SIMD-Anweisungen. Die Annahme ist entweder, dass Sie eine Liste von 32-Bit-Ganzzahlen haben, von denen die meisten klein sind, oder eine Liste von 32-Bit-Ganzzahlen, in denen die Unterschiede zwischen aufeinanderfolgenden Ganzzahlen gering sind. Keine Software ist in der Lage, ein Array von 32-Bit-Zufallszahlen zuverlässig zu komprimieren.
Diese Bibliothek kann auf den meisten Desktop- oder Laptop-Prozessoren mindestens 4 Milliarden komprimierte Ganzzahlen pro Sekunde dekodieren. Das heißt, es kann Daten mit einer Rate von 15 GB/s dekomprimieren. Dies ist deutlich schneller als generische Codecs wie gzip, LZO, Snappy oder LZ4.
Auf einem Skylake-Intel-Prozessor kann er Ganzzahlen mit einer Rate von 0,3 Zyklen pro Ganzzahl dekodieren, was sich problemlos in mehr als 8 dekodierte Milliarden Ganzzahlen pro Sekunde umsetzen lässt.
Diese Bibliothek ist Teil der Awesome C-Liste der C-Ressourcen.
Mitwirkende: Daniel Lemire, Nathan Kurz, Christoph Rupp, Anatol Belski, Nick White und andere
Dies ist eine Low-Level-Bibliothek für die schnelle Ganzzahlkomprimierung. Es definiert konstruktionsbedingt kein komprimiertes Format. Es ist Sache des (erfahrenen) Benutzers, ein komprimiertes Format zu erstellen.
Es wird verwendet von:
Eine einfache C-Version, die keine SIMD-Anweisungen verwendet, finden Sie unter https://github.com/lemire/LittleIntPacker
Die Komprimierung funktioniert über Blöcke mit 128 Ganzzahlen.
Ein vollständiges Arbeitsbeispiel finden Sie unter example.c (Sie können es erstellen und mit „make example; ./example“ ausführen).
const uint32_t b = maxbits ( datain ); // computes bit width
simdpackwithoutmask ( datain , buffer , b ); //compressed to buffer, compressing 128 32-bit integers down to b*32 bytes
simdunpack ( buffer , backbuffer , b ); //uncompressed to backbufferWährend 128 32-Bit-Ganzzahlen gelesen werden, werden nur b 128-Bit-Wörter geschrieben. Somit beträgt das Kompressionsverhältnis 32/b.
Wir haben Differentialkodierung verwendet: Wir speichern die Differenz zwischen aufeinanderfolgenden ganzen Zahlen. Dazu benötigen wir einen Anfangswert (Offset genannt).
uint32_t offset = 0 ;
uint32_t b1 = simdmaxbitsd1 ( offset , datain ); // bit width
simdpackwithoutmaskd1 ( offset , datain , buffer , b1 ); //compressing 128 32-bit integers down to b1*32 bytes
simdunpackd1 ( offset , buffer , backbuffer , b1 ); //uncompressedAllgemeines Beispiel für Arrays beliebiger Länge:
int compress_decompress_demo () {
size_t k , N = 9999 ;
__m128i * endofbuf ;
uint32_t * datain = malloc ( N * sizeof ( uint32_t ));
uint8_t * buffer ;
uint32_t * backbuffer = malloc ( N * sizeof ( uint32_t ));
uint32_t b ;
for ( k = 0 ; k < N ; ++ k ){ /* start with k=0, not k=1! */
datain [ k ] = k ;
}
b = maxbits_length ( datain , N );
buffer = malloc ( simdpack_compressedbytes ( N , b )); // allocate just enough memory
endofbuf = simdpack_length ( datain , N , ( __m128i * ) buffer , b );
/* compressed data is stored between buffer and endofbuf using (endofbuf-buffer)*sizeof(__m128i) bytes */
/* would be safe to do : buffer = realloc(buffer,(endofbuf-(__m128i *)buffer)*sizeof(__m128i)); */
simdunpack_length (( const __m128i * ) buffer , N , backbuffer , b );
for ( k = 0 ; k < N ; ++ k ){
if ( datain [ k ] != backbuffer [ k ]) {
printf ( "bugn" );
return -1 ;
}
}
return 0 ;
}Wir haben auch Frame-of-Reference (FOR)-Funktionen (siehe simdfor.h-Header). Sie funktionieren wie die Bitpacking-Routinen, verwenden jedoch keine Differenzcodierung, sodass sie in einigen Fällen eine schnellere Suche auf Kosten der Komprimierung ermöglichen.
machen, machen, testen
Und wenn Sie sich trauen:
make installieren
Wenn Sie ein Go-Benutzer sind, gibt es einen „Go“-Ordner, in dem Sie eine einfache Demo finden.
