HackerPapers

arXiv:1209.2137cs.IR

Decoding billions of integers per second through vectorization

Daniel Lemire, Leonid Boytsov

Abstract

In many important applications -- such as search engines and relational database systems -- data is 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 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 per integer. 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.

arXiv comments
For software, see https://github.com/lemire/FastPFor, For data, see http://boytsov.info/datasets/clueweb09gap/
Journal reference
Software: Practice & Experience 45 (1), 2015
DOI
doi:10.1002/spe.2203
Subjects
cs.IRInformation Retrieval cs.DBDatabases

On Hacker News

Linked by 7 identifiable commenters in 7 comments across 6 threads, from Sep 2012 to Oct 2025.

Comments linking this paper, per year.

Discussed in comments6 threads

  1. 86 GB/s bitpacking with ARM SIMD (single thread) 1 comment

    • Thank you so much for attempting a reproduction! (I posted this on Reddit and most commenters didn't even click the link) For the baseline you need SIMDe headers: https://github.com/simd-everywhere/simde/tree/master/simde. These alias x86 intrinsics to ARM intrinsics. The…

      ashtonsixView on HNParent context

  2. Sorted Integer Compression 1 comment

    • > For my purpose, I want to get as high a compression rate as possible, and I need to store just the list of integers Then PFor(Delta) is not the best option, that class of algorithms is intentionally a trade-off between compression rate and decoding speed, as it's meant to…

      otView on HNParent context

  3. Stream VByte: breaking new speed records for integer compression 1 comment

    • if you want bit level granularity you can use either SIMD-BP128 or SIMD-FastPFOR from https://arxiv.org/pdf/1209.2137.pdf

      jeffffffView on HNParent context

  4. Multihash – self-describing hashes 1 comment

    • IMHO: Using varint for this is silly, and just wastes decoding time. (Doing because proto/etc did it, when they have wildly different use cases, it a bad idea.) The example they purport to give even proves it: " For example, a 100 TB file in IPFS may have as many as 400 million…

      DannyBeeView on HNParent context

  5. Fast integer compression in Java 1 comment

    • You should probably read the original research paper if you're curious: http://arxiv.org/abs/1209.2137

      gwernView on HNParent context

  6. Fast integer compression: decoding billions of integers per second 2 comments

    • Look for the section that says 'We posted our paper online together with our software.' The word 'paper' is a link to http://arxiv.org/abs/1209.2137 and 'our software' is a link to https://github.com/lemire/FastPFor

      kevingaddView on HNParent context

    • It's buried in the article, but here's the paper: http://arxiv.org/abs/1209.2137 Here's the source: https://github.com/lemire/FastPFor

      cube13View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.