simdcomp
version 0.1.1
バイナリ パッキングと SIMD 命令を使用して整数のリストを圧縮するためのシンプルな C ライブラリ。前提として、ほとんどの整数が小さい 32 ビット整数のリスト、または連続する整数間の差が小さい 32 ビット整数のリストがあることが前提となります。 32 ビット乱数の配列を確実に圧縮できるソフトウェアはありません。
このライブラリは、ほとんどのデスクトップまたはラップトップ プロセッサで 1 秒あたり少なくとも 40 億の圧縮整数をデコードできます。つまり、15 GB/秒の速度でデータを解凍できます。これは、gzip、LZO、Snappy、LZ4 などの汎用コーデックよりも大幅に高速です。
Skylake Intel プロセッサでは、整数あたり 0.3 サイクルの速度で整数をデコードできます。これは、1 秒あたり 8 億を超える整数のデコードに容易に変換できます。
このライブラリは、C リソースの Awesome C リストの一部です。
寄稿者: Daniel Lemire、Nathan Kurz、Christoph Rupp、Anatol Belski、Nick White など
これは、高速整数圧縮のための低レベルのライブラリです。設計上、圧縮形式は定義されていません。圧縮形式を作成するかどうかは、(洗練された) ユーザーの責任です。
これは次のユーザーによって使用されます。
SIMD 命令を使用しないプレーン C バージョンについては、https://github.com/lemire/LittleIntPacker を参照してください。
圧縮は 128 個の整数のブロックに対して機能します。
完全な動作例については、example.c を参照してください (「make example; ./example」でビルドして実行できます)。
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 backbuffer128 個の 32 ビット整数が読み取られる間、b 個の 128 ビット ワードのみが書き込まれます。したがって、圧縮率は 32/b になります。
私たちは差分コーディングを使用しました。つまり、連続する整数の差を保存します。この目的のために、初期値 (オフセットと呼ばれます) が必要です。
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 ); //uncompressed任意の長さの配列の一般的な例:
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 ;
}参照フレーム (FOR) 関数もあります (simdfor.h ヘッダーを参照)。これらはビット パッキング ルーチンと同様に機能しますが、差分コーディングを使用しないため、場合によっては圧縮を犠牲にして検索を高速化できます。
メイクメイクテスト
そして、もしあなたが大胆なら:
インストールする
go ユーザーの場合は、「go」フォルダーに簡単なデモがあります。
