simdcomp
version 0.1.1
바이너리 패킹 및 SIMD 명령어를 사용하여 정수 목록을 압축하기 위한 간단한 C 라이브러리입니다. 대부분이 작은 32비트 정수 목록이 있거나 연속된 정수 간의 차이가 작은 32비트 정수 목록이 있다고 가정합니다. 32비트 난수 배열을 안정적으로 압축할 수 있는 소프트웨어는 없습니다.
이 라이브러리는 대부분의 데스크탑 또는 노트북 프로세서에서 초당 최소 40억 개의 압축 정수를 디코딩할 수 있습니다. 즉, 15GB/s의 속도로 데이터의 압축을 풀 수 있습니다. 이는 gzip, LZO, Snappy 또는 LZ4와 같은 일반 코덱보다 훨씬 빠릅니다.
Skylake Intel 프로세서에서는 정수당 0.3사이클의 속도로 정수를 디코딩할 수 있으며, 이는 초당 80억 개가 넘는 디코딩된 정수로 쉽게 변환될 수 있습니다.
이 라이브러리는 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" 폴더가 있습니다.
