Page d'accueil>Lié à la programmation>Code source C#
Télécharger

La bibliothèque SIMDComp

Une simple bibliothèque C pour compresser des listes d'entiers à l'aide d'un emballage binaire et d'instructions SIMD. L'hypothèse est soit que vous disposez d'une liste d'entiers de 32 bits dont la plupart sont petits, soit d'une liste d'entiers de 32 bits où les différences entre les entiers successifs sont faibles. Aucun logiciel n'est capable de compresser de manière fiable un tableau de nombres aléatoires de 32 bits.

Cette bibliothèque peut décoder au moins 4 milliards d'entiers compressés par seconde sur la plupart des processeurs de bureau ou d'ordinateur portable. Autrement dit, il peut décompresser les données à une vitesse de 15 Go/s. C'est nettement plus rapide que les codecs génériques comme gzip, LZO, Snappy ou LZ4.

Sur un processeur Skylake Intel, il peut décoder des entiers à une fréquence de 0,3 cycles par entier, ce qui peut facilement se traduire par plus de 8 milliards d'entiers décodés par seconde.

Cette bibliothèque fait partie de la liste Awesome C de ressources C.

Contributeurs : Daniel Lemire, Nathan Kurz, Christoph Rupp, Anatol Belski, Nick White et autres

A quoi ça sert ?

Il s'agit d'une bibliothèque de bas niveau pour une compression rapide d'entiers. De par sa conception, il ne définit pas de format compressé. C'est à l'utilisateur (expert) de créer un format compressé.

Il est utilisé par :

  • mise à l'échelle
  • ÉvénementQL
  • ManticoreRecherche

Exigences

  • Votre processeur doit prendre en charge SSE4.1 (il est pris en charge par la plupart des processeurs Intel et AMD sortis depuis 2008.)
  • Il est possible de construire la partie centrale du code si votre processeur prend en charge SSE2 (Pentium4 ou supérieur)
  • Compilateur compatible C99 (GCC est supposé)
  • Une distribution de type Linux est supposée par le makefile

Pour une version C simple qui n'utilise pas les instructions SIMD, voir https://github.com/lemire/LittleIntPacker

Usage

La compression fonctionne sur des blocs de 128 entiers.

Pour un exemple de travail complet, voir example.c (vous pouvez le construire et l'exécuter avec "make example; ./example").

  1. Listes d'entiers dans un ordre aléatoire. 
 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

Alors que 128 entiers de 32 bits sont lus, seuls des mots de 128 bits sont écrits. Ainsi, le taux de compression est de 32/b.

  1. Listes triées d'entiers.

Nous avons utilisé un codage différentiel : nous stockons la différence entre des entiers successifs. Pour cela, nous avons besoin d’une valeur initiale (appelée 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

Exemple général pour des tableaux de longueur arbitraire : 

 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. Cadre de référence

Nous avons également des fonctions de cadre de référence (FOR) (voir l'en-tête simdfor.h). Ils fonctionnent comme les routines de compression de bits, mais n'utilisent pas de codage différentiel et permettent donc une recherche plus rapide dans certains cas, au détriment de la compression.

Installation

faire faire un test

et si vous osez :

faire installer

Aller

Si vous êtes un utilisateur Go, il existe un dossier "go" dans lequel vous trouverez une démo simple.

Autres bibliothèques

  • Compression rapide d'entiers dans Go : https://github.com/ronanh/intcomp
  • Algorithmes Fast Bitpacking : port Rust de simdcomp https://github.com/quickwit-oss/bitpacking
  • SIMDCompressionAndIntersection : une bibliothèque C++ pour compresser et croiser des listes triées d'entiers à l'aide des instructions SIMD https://github.com/lemire/SIMDCompressionAndIntersection
  • La bibliothèque FastPFOR C++ : Compression rapide d'entiers https://github.com/lemire/FastPFor
  • Codage par dictionnaire haute performance https://github.com/lemire/dictionary
  • LittleIntPacker : bibliothèque C pour compresser et décompresser de courts tableaux d'entiers le plus rapidement possible https://github.com/lemire/LittleIntPacker
  • StreamVByte : compression rapide d'entiers en C à l'aide du codec StreamVByte https://github.com/lemire/streamvbyte
  • MaskedVByte : décodeur rapide pour les entiers compressés en VByte https://github.com/lemire/MaskedVByte
  • CSharpFastPFOR : bibliothèque de compression d'entiers AC# https://github.com/Genbox/CSharpFastPFOR
  • JavaFastPFOR : une bibliothèque de compression d'entiers Java https://github.com/lemire/JavaFastPFOR
  • Encodage : bibliothèques de compression d'entiers pour Go https://github.com/zhenjl/encoding
  • FrameOfReference est une bibliothèque C++ dédiée à la compression frame-of-reference (FOR) : https://github.com/lemire/FrameOfReference
  • libvbyte : une implémentation rapide pour la compression entière varbyte 32 bits/64 bits https://github.com/cruppstahl/libvbyte
  • TurboPFor est une bibliothèque C qui propose de nombreuses optimisations intéressantes. Ça vaut le coup de vérifier ! (Licence GPL) https://github.com/powturbo/TurboPFor
  • Oroch est une bibliothèque C++ qui propose une API utilisable (licence MIT) https://github.com/ademakov/Oroch

Autres langages de programmation

  • Il y a un emballage pour Julia.
  • Il existe un port Rust.

Références

  • Daniel Lemire, Nathan Kurz, Christoph Rupp, Stream VByte : compression d'entiers plus rapide orientée octets, lettres de traitement de l'information, lettres de traitement de l'information 130, février 2018, pages 1-6https://arxiv.org/abs/1709.08990
  • Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, Steven Swanson, Une étude expérimentale de la compression bitmap par rapport à la compression de liste inversée, SIGMOD 2017 http://db.ucsd.edu/wp-content/uploads/2017/03/sidm338-wangA. pdf
  • P. Damme, D. Habich, J. Hildebrandt, W. Lehner, Algorithmes légers de compression de données : une enquête expérimentale (expériences et analyses), EDBT 2017 http://openproceedings.org/2017/conf/edbt/paper-146. pdf
  • P. Damme, D. Habich, J. Hildebrandt, W. Lehner, Aperçus de l'évaluation comparative des algorithmes légers de compression de données, EDBT 2017 http://openproceedings.org/2017/conf/edbt/paper-414.pdf
  • Daniel Lemire, Leonid Boytsov, Nathan Kurz, Compression SIMD et intersection d'entiers triés, Software Practice & Experience 46 (6) 2016. http://arxiv.org/abs/1401.6399
  • Daniel Lemire et Leonid Boytsov, Décoder des milliards d'entiers par seconde grâce à la vectorisation, Software Practice & Experience 45 (1), 2015. http://arxiv.org/abs/1209.2137 http://onlinelibrary.wiley.com/doi/10.1002 /spe.2203/résumé
  • Jeff Plaisance, Nathan Kurz, Daniel Lemire, Vectorized VByte Decoding, Symposium international sur les algorithmes 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, Une approche générale basée sur SIMD pour accélérer les algorithmes de compression, ACM Transactions on Information Systems 33 (3), 2015. http https://arxiv.org/abs/1502.01916
  • TD Wu, Techniques de Bitpacking pour l'indexation des génomes : I. Tables de hachage, Algorithmes pour la biologie moléculaire 11 (5), 2016. http://almob.biomedcentral.com/articles/10.1186/s13015-016-0069-5
Développer
Informations supplémentaires
Applications connexes
Recommandé pour vous
Actualités connexes Tout