Inicio>Relacionado con la programación>código fuente c#
Descargar

La biblioteca SIMDComp

Una biblioteca C sencilla para comprimir listas de números enteros mediante empaquetado binario e instrucciones SIMD. La suposición es que tiene una lista de enteros de 32 bits donde la mayoría de ellos son pequeños, o una lista de enteros de 32 bits donde las diferencias entre enteros sucesivos son pequeñas. Ningún software es capaz de comprimir de manera confiable una matriz de números aleatorios de 32 bits.

Esta biblioteca puede decodificar al menos 4 mil millones de números enteros comprimidos por segundo en la mayoría de los procesadores de computadoras de escritorio o portátiles. Es decir, puede descomprimir datos a una velocidad de 15 GB/s. Esto es significativamente más rápido que los códecs genéricos como gzip, LZO, Snappy o LZ4.

En un procesador Skylake Intel, puede decodificar números enteros a una velocidad de 0,3 ciclos por número entero, lo que puede traducirse fácilmente en más de 8 mil millones de enteros decodificados por segundo.

Esta biblioteca es parte de la lista Awesome C de recursos C.

Colaboradores: Daniel Lemire, Nathan Kurz, Christoph Rupp, Anatol Belski, Nick White y otros

¿Para qué es?

Esta es una biblioteca de bajo nivel para una compresión rápida de enteros. Por diseño no define un formato comprimido. Depende del usuario (sofisticado) crear un formato comprimido.

Es utilizado por:

  • mejoradodb
  • EventQL
  • MantícoraBuscar

Requisitos

  • Su procesador debe ser compatible con SSE4.1 (es compatible con la mayoría de los procesadores Intel y AMD lanzados desde 2008).
  • Es posible construir la parte central del código si su procesador es compatible con SSE2 (Pentium4 o mejor).
  • Compilador compatible con C99 (se supone GCC)
  • El archivo MAKE asume una distribución similar a Linux

Para obtener una versión C simple que no utiliza instrucciones SIMD, consulte https://github.com/lemire/LittleIntPacker

Uso

La compresión funciona sobre bloques de 128 enteros.

Para ver un ejemplo funcional completo, consulte ejemplo.c (puede compilarlo y ejecutarlo con "make example; ./example").

  1. Listas de números enteros en orden aleatorio. 
 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

Mientras que se leen 128 enteros de 32 bits, sólo se escriben b palabras de 128 bits. Por tanto, la relación de compresión es 32/b.

  1. Listas ordenadas de números enteros.

Usamos codificación diferencial: almacenamos la diferencia entre números enteros sucesivos. Para ello, necesitamos un valor inicial (llamado desplazamiento). 

 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

Ejemplo general para matrices de longitud arbitraria: 

 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 ;
}
  1. Marco de referencia

También tenemos funciones de marco de referencia (FOR) (consulte el encabezado simdfor.h). Funcionan como las rutinas de empaquetado de bits, pero no utilizan codificación diferencial, por lo que permiten una búsqueda más rápida en algunos casos, a expensas de la compresión.

Configuración

hacer hacer prueba

y si eres atrevido:

hacer la instalación

Ir

Si es usuario de Go, hay una carpeta "Go" donde encontrará una demostración sencilla.

Otras bibliotecas

  • Compresión rápida de enteros en Go: https://github.com/ronanh/intcomp
  • Algoritmos rápidos de Bitpacking: puerto Rust de simdcomp https://github.com/quickwit-oss/bitpacking
  • SIMDCompressionAndIntersection: una biblioteca de C++ para comprimir e intersectar listas ordenadas de números enteros usando instrucciones SIMD https://github.com/lemire/SIMDCompressionAndIntersection
  • La biblioteca FastPFOR C++: compresión rápida de enteros https://github.com/lemire/FastPFor
  • Codificación de diccionario de alto rendimiento https://github.com/lemire/dictionary
  • LittleIntPacker: biblioteca C para empaquetar y descomprimir matrices cortas de números enteros lo más rápido posible https://github.com/lemire/LittleIntPacker
  • StreamVByte: Compresión rápida de enteros en C usando el códec StreamVByte https://github.com/lemire/streamvbyte
  • MaskedVByte: decodificador rápido para enteros comprimidos con VByte https://github.com/lemire/MaskedVByte
  • CSharpFastPFOR: biblioteca de compresión de enteros AC# https://github.com/Genbox/CSharpFastPFOR
  • JavaFastPFOR: una biblioteca de compresión de enteros de Java https://github.com/lemire/JavaFastPFOR
  • Codificación: Bibliotecas de compresión de enteros para Go https://github.com/zhenjl/encoding
  • FrameOfReference es una biblioteca de C++ dedicada a la compresión de marcos de referencia (FOR): https://github.com/lemire/FrameOfReference
  • libvbyte: una implementación rápida para la compresión de enteros varbyte de 32 bits/64 bits https://github.com/cruppstahl/libvbyte
  • TurboPFor es una biblioteca C que ofrece muchas optimizaciones interesantes. ¡Vale la pena comprobarlo! (Licencia GPL) https://github.com/powturbo/TurboPFor
  • Oroch es una biblioteca C++ que ofrece una API utilizable (licencia MIT) https://github.com/ademakov/Oroch

Otros lenguajes de programación

  • Hay un envoltorio para Julia.
  • Hay un puerto Rust.

Referencias

  • Daniel Lemire, Nathan Kurz, Christoph Rupp, Stream VByte: compresión de enteros orientada a bytes más rápida, Cartas de procesamiento de información, Cartas de procesamiento de información 130, febrero de 2018, páginas 1 a 6 https://arxiv.org/abs/1709.08990
  • Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, Steven Swanson, Un estudio experimental de compresión de mapas de bits frente a compresión de listas invertidas, SIGMOD 2017 http://db.ucsd.edu/wp-content/uploads/2017/03/sidm338-wangA. pdf
  • P. Damme, D. Habich, J. Hildebrandt, W. Lehner, Algoritmos ligeros de compresión de datos: una encuesta experimental (experimentos y análisis), EDBT 2017 http://openproceedings.org/2017/conf/edbt/paper-146. pdf
  • P. Damme, D. Habich, J. Hildebrandt, W. Lehner, Información sobre la evaluación comparativa de algoritmos de compresión de datos ligeros, EDBT 2017 http://openproceedings.org/2017/conf/edbt/paper-414.pdf
  • Daniel Lemire, Leonid Boytsov, Nathan Kurz, Compresión SIMD y la intersección de enteros ordenados, Práctica y experiencia de software 46 (6) 2016. http://arxiv.org/abs/1401.6399
  • Daniel Lemire y Leonid Boytsov, Decodificación de miles de millones de enteros por segundo mediante vectorización, Software Practice & Experience 45 (1), 2015. http://arxiv.org/abs/1209.2137 http://onlinelibrary.wiley.com/doi/10.1002 /spe.2203/abstracto
  • Jeff Plaisance, Nathan Kurz, Daniel Lemire, Decodificación de VByte vectorizada, Simposio 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, Un enfoque general basado en SIMD para acelerar los algoritmos de compresión, Transacciones ACM en sistemas de información 33 (3), 2015. http //arxiv.org/abs/1502.01916
  • TD Wu, Técnicas de empaquetado de bits para indexar genomas: I. Tablas hash, Algoritmos para biología molecular 11 (5), 2016. http://almob.biomedcentral.com/articles/10.1186/s13015-016-0069-5
Expandir
Información adicional
Aplicaciones relacionadas
Recomendado para ti
Información relacionada Todo