simdcomp

A biblioteca SIMDComp

Uma biblioteca C simples para compactar listas de inteiros usando empacotamento binário e instruções SIMD. A suposição é que você tem uma lista de números inteiros de 32 bits, onde a maioria deles é pequena, ou uma lista de números inteiros de 32 bits, onde as diferenças entre números inteiros sucessivos são pequenas. Nenhum software é capaz de compactar de forma confiável uma matriz de números aleatórios de 32 bits.

Esta biblioteca pode decodificar pelo menos 4 bilhões de números inteiros compactados por segundo na maioria dos processadores de desktops ou laptops. Ou seja, ele pode descompactar dados a uma taxa de 15 GB/s. Isso é significativamente mais rápido que codecs genéricos como gzip, LZO, Snappy ou LZ4.

Em um processador Skylake Intel, ele pode decodificar números inteiros a uma taxa de 0,3 ciclos por número inteiro, o que pode facilmente se traduzir em mais de 8 bilhões de números inteiros decodificados por segundo.

Esta biblioteca faz parte da lista Awesome C de recursos C.

Colaboradores: Daniel Lemire, Nathan Kurz, Christoph Rupp, Anatol Belski, Nick White e outros

Para que serve?

Esta é uma biblioteca de baixo nível para compactação rápida de inteiros. Por design, ele não define um formato compactado. Cabe ao usuário (sofisticado) criar um formato compactado.

É usado por:

• upscaledb
• EventQL
• ManticoreSearch

Requisitos

• Seu processador deve suportar SSE4.1 (é compatível com a maioria dos processadores Intel e AMD lançados desde 2008).
• É possível construir a parte central do código se o seu processador suportar SSE2 (Pentium4 ou melhor)
• Compilador compatível com C99 (supõe-se GCC)
• Uma distribuição semelhante ao Linux é assumida pelo makefile

Para uma versão C simples que não usa instruções SIMD, consulte https://github.com/lemire/LittleIntPacker

Uso

A compactação funciona em blocos de 128 números inteiros.

Para um exemplo funcional completo, consulte example.c (você pode construí-lo e executá-lo com "make example; ./example").

1. Listas de inteiros em ordem aleatória.

 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 backbuffer

Enquanto 128 inteiros de 32 bits são lidos, apenas b palavras de 128 bits são escritas. Assim, a taxa de compressão é 32/b.

2. Listas ordenadas de inteiros.

Usamos codificação diferencial: armazenamos a diferença entre números inteiros sucessivos. Para isso, precisamos de um valor inicial (chamado offset).

 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

Exemplo geral para matrizes de comprimento arbitrário:

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

3. Quadro de referência

Também temos funções de quadro de referência (FOR) (consulte o cabeçalho simdfor.h). Elas funcionam como as rotinas de empacotamento de bits, mas não utilizam codificação diferencial, permitindo uma busca mais rápida em alguns casos, em detrimento da compactação.

Configurar

fazer fazer teste

e se você for ousado:

fazer instalar

Ir

Se você é um usuário go, existe uma pasta “go” onde você encontrará uma demonstração simples.

Outras bibliotecas

• Compressão inteira rápida em Go: https://github.com/ronanh/intcomp
• Algoritmos de Bitpacking rápidos: porta Rust do simdcomp https://github.com/quickwit-oss/bitpacking
• SIMDCompressionAndIntersection: uma biblioteca C++ para compactar e cruzar listas classificadas de inteiros usando instruções SIMD https://github.com/lemire/SIMDCompressionAndIntersection
• A biblioteca FastPFOR C++: compactação rápida de números inteiros https://github.com/lemire/FastPFor
• Codificação de dicionário de alto desempenho https://github.com/lemire/dictionary
• LittleIntPacker: biblioteca C para compactar e descompactar matrizes curtas de números inteiros o mais rápido possível https://github.com/lemire/LittleIntPacker
• StreamVByte: compactação rápida de números inteiros em C usando o codec StreamVByte https://github.com/lemire/streamvbyte
• MaskedVByte: decodificador rápido para números inteiros compactados em VByte https://github.com/lemire/MaskedVByte
• CSharpFastPFOR: biblioteca de compactação de inteiros AC# https://github.com/Genbox/CSharpFastPFOR
• JavaFastPFOR: uma biblioteca de compactação de inteiros java https://github.com/lemire/JavaFastPFOR
• Codificação: bibliotecas de compactação de números inteiros para Go https://github.com/zhenjl/encoding
• FrameOfReference é uma biblioteca C++ dedicada à compactação de quadro de referência (FOR): https://github.com/lemire/FrameOfReference
• libvbyte: uma implementação rápida para compactação inteira varbyte de 32 bits/64 bits https://github.com/cruppstahl/libvbyte
• TurboPFor é uma biblioteca C que oferece muitas otimizações interessantes. Vale a pena conferir! (licença GPL) https://github.com/powturbo/TurboPFor
• Oroch é uma biblioteca C++ que oferece uma API utilizável (licença MIT) https://github.com/ademakov/Oroch

Outras linguagens de programação

• Há um invólucro para Julia.
• Existe uma porta Rust.

Referências

• Daniel Lemire, Nathan Kurz, Christoph Rupp, Stream VByte: Faster Byte-Oriented Integer Compression, Information Processing Letters, Information Processing Letters 130, fevereiro de 2018, páginas 1-6https://arxiv.org/abs/1709.08990
• Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, Steven Swanson, Um Estudo Experimental de Compressão de Bitmap vs. Compressão de Lista Invertida, SIGMOD 2017 http://db.ucsd.edu/wp-content/uploads/2017/03/sidm338-wangA. pdf
• P. Damme, D. Habich, J. Hildebrandt, W. Lehner, Algoritmos leves de compressão de dados: uma pesquisa experimental (experimentos e análises), EDBT 2017 http://openproceedings.org/2017/conf/edbt/paper-146. pdf
• P. Damme, D. Habich, J. Hildebrandt, W. Lehner, Insights sobre a avaliação comparativa de algoritmos leves de compressão de dados, EDBT 2017 http://openproceedings.org/2017/conf/edbt/paper-414.pdf
• Daniel Lemire, Leonid Boytsov, Nathan Kurz, SIMD Compression and the Intersection of Sorted Integers, Software Practice & Experience 46 (6) 2016. http://arxiv.org/abs/1401.6399
• Daniel Lemire e Leonid Boytsov, Decodificando bilhões de inteiros por segundo por meio de vetorização, Software Practice & Experience 45 (1), 2015. http://arxiv.org/abs/1209.2137 http://onlinelibrary.wiley.com/doi/10.1002 /spe.2203/resumo
• Jeff Plaisance, Nathan Kurz, Daniel Lemire, Vectorized VByte Decoding, Simpósio Internacional sobre Algoritmos Web 2015, 2015. http://arxiv.org/abs/1503.07387
• Wayne Xin Zhao, Xudong Zhang, Daniel Lemire, Dongdong Shan, Jian-Yun Nie, Hongfei Yan, Ji-Rong Wen, Uma abordagem geral baseada em SIMD para acelerar algoritmos de compressão, Transações ACM em sistemas de informação 33 (3), 2015. http ://arxiv.org/abs/1502.01916
• TD Wu, Técnicas de Bitpacking para indexação de genomas: I. Tabelas de hash, Algoritmos para Biologia Molecular 11 (5), 2016. http://almob.biomedcentral.com/articles/10.1186/s13015-016-0069-5