HackerPapers

arXiv:1709.08990cs.IR

Stream VByte: Faster Byte-Oriented Integer Compression

Daniel Lemire, Nathan Kurz, Christoph Rupp

Abstract

Arrays of integers are often compressed in search engines. Though there are many ways to compress integers, we are interested in the popular byte-oriented integer compression techniques (e.g., VByte or Google's Varint-GB). They are appealing due to their simplicity and engineering convenience. Amazon's varint-G8IU is one of the fastest byte-oriented compression technique published so far. It makes judicious use of the powerful single-instruction-multiple-data (SIMD) instructions available in commodity processors. To surpass varint-G8IU, we present Stream VByte, a novel byte-oriented compression technique that separates the control stream from the encoded data. Like varint-G8IU, Stream VByte is well suited for SIMD instructions. We show that Stream VByte decoding can be up to twice as fast as varint-G8IU decoding over real data sets. In this sense, Stream VByte establishes new speed records for byte-oriented integer compression, at times exceeding the speed of the memcpy function. On a 3.4GHz Haswell processor, it decodes more than 4 billion differentially-coded integers per second from RAM to L1 cache.

arXiv comments
Journal reference
Information Processing Letters 130, February 2018, Pages 1-6
DOI
doi:10.1016/j.ipl.2017.09.011
Subjects
cs.IRInformation Retrieval cs.DBDatabases

On Hacker News

Linked by 3 identifiable commenters in 3 comments across 2 threads, from May 2024 to Aug 2024.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Another variable-length integer encoding (2021) 1 comment

    • Stream VByte[1,2,3] is not far away from that idea, storing the packed lengths in a separate stream from the data bytes. (There’s also a more conventional interleaved design in varint-G8IU, but Stepanov decided to fuck everyone over and patented that.) [1]…

      mananaysiempreView on HNParent context

  2. vu128: Efficient variable-length integers 2 comments

    • If I’m following, this presents an alternative format and implementation to LEB128 which encodes and decodes substantially faster. Notably, the implementation is quite simple. Cool! And agreed that modern CPUs really suffer from branches. Should I interpret the plot to mean the…

      danking00View on HNParent context

    • Yeah, see Stream VByte [1] for more information. [1] https://arxiv.org/abs/1709.08990

      lifthrasiirView on HNParent context

Submitted to Hacker News

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