按年被提到
20172024 · 2 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:1709.08990 · cs.IR

Stream VByte: Faster Byte-Oriented Integer Compression

Daniel Lemire, Nathan Kurz, Christoph Rupp · 2017
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2024-05-23 · 最近 2024-08-11
2不同的人
2活跃月份
2讨论串
47被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论danking00 · 2024-05

“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 average elapsed wall clock time per integer decoded/encoded? And can I conclu…”

vu128: Efficient variable-length integers原评论 ↗
评论mananaysiempre · 2024-08

“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] https://lemire.me/blog/2017/09/27/stream-vbyte-breaking-new-speed-records-for-integer-compression/ …”

Another variable-length integer encoding (2021)原评论 ↗