Decoding billions of integers per second through vectorization [r-libre/193]

Lemire, Daniel et Boytsov, Leonid (2015). Decoding billions of integers per second through vectorization. Software: Practice & Experience, 45 (1), 1-29. https://doi.org/10.1002/spe.2203

Fichier(s) associé(s) à ce document :

PDF - 1209.2137v6.pdf
Licence : Creative Commons CC BY.

Télécharger

Catégorie de document :	Articles de revues
Évaluation par un comité de lecture :	Oui
Étape de publication :	Publié
Résumé :	In many important applications—such as search engines and relational database systems—data are stored in the form of arrays of integers. Encoding and, most importantly, decoding of these arrays consumes considerable CPU time. Therefore, substantial effort has been made to reduce costs associated with compression and decompression. In particular, researchers have exploited the superscalar nature of modern processors and single-instruction, multiple-data (SIMD) instructions. Nevertheless, we introduce a novel vectorized scheme called SIMD-BP128⋆ that improves over previously proposed vectorized approaches. It is nearly twice as fast as the previously fastest schemes on desktop processors (varint-G8IU and PFOR). At the same time, SIMD-BP128⋆ saves up to 2 bits/int. For even better compression, we propose another new vectorized scheme (SIMD-FastPFOR) that has a compression ratio within 10% of a state-of-the-art scheme (Simple-8b) while being two times faster during decoding.
Adresse de la version officielle :	http://onlinelibrary.wiley.com/doi/10.1002/spe.220...
Déposant:	Lemire, Daniel
Responsable :	Daniel Lemire
Dépôt :	14 juill. 2014 20:13
Dernière modification :	02 mars 2021 18:58

Actions (connexion requise)

RÉVISER