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

Decoding billions of integers per second through vectorization

通过向量化每秒解码数十亿整数
Daniel Lemire, Leonid Boytsov · 2012

SIMD-BP128 等向量化整数压缩方案,解码速度近乎翻倍

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 4 人首次 2012-09-12 · 最近 2025-10-05
4不同的人
4活跃月份
4讨论串
312被引(OpenAlex)

针对搜索引擎和关系数据库中整数数组的压缩与解码开销,提出新的向量化方案 SIMD-BP128,在桌面处理器上几乎是此前最快方案(varint-G8IU 和 PFOR)的两倍快,同时每个整数最多省 2 比特。另一个新方案 SIMD-FastPFOR 压缩率与最先进的 Simple-8b 相差在 10% 以内,解码速度却快两倍。

HN 为什么提它

HN 上的人把它当作有序整数压缩(如 PForDelta、二进制打包)的好综述和速度基线,也用来说明变长字节编码是最慢的做法。

方法难度 4 / 5约 60 分钟经得起时间
读之前最好知道
1整数压缩与倒排索引
2SIMD 指令(SSE)
3位打包(bit packing)与差分编码
4CPU 超标量与流水线

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐ot · 2021-06

“which is indeed a very good survey of this stuff”

称它是这方面很好的综述,讲有序整数压缩
Sorted Integer Compression原评论 ↗
引用kevingadd · 2012-09

“The word 'paper' is a link to Decoding billions of integers per second through vectorization”

贴出论文链接,说明向量化每秒解码数十亿整数
Fast integer compression: decoding billions of integers per second原评论 ↗
引用DannyBee · 2017-02

“variable byte encoding is pretty much the slowest way to do it.”

引它说明 variable byte 编码几乎是最慢的做法
Multihash – self-describing hashes原评论 ↗
引用ashtonsix · 2025-10

“The baseline is based on the previous State-of-The-Art which happens to be x86-based”

指出它是此前最先进的 x86 基线,用作对比
86 GB/s bitpacking with ARM SIMD (single thread)原评论 ↗