“we tried to give a clear explanation (with diagrams) of how it can be faster to roll your own popcnt using Carry-Save-Adders:”
Faster Population Counts Using AVX2 Instructions
用 AVX2 向量化实现 popcount,比专用 popcnt 指令快约一倍
统计二进制流中 1 的个数是数据库、信息检索、密码学和机器学习中的常见操作。论文表明,在近期的 Intel 处理器上,基于 SIMD 的向量化方法可以比专用的 popcnt 指令快约两倍;在需要额外布尔运算的相似度度量(如 Jaccard 指数)中收益更大。该方法已被 LLVM 采用,用于 clang 编译器。
评论者用它说明为何手写 SIMD 的 popcount 能比内建 POPCNT 指令更快,并推荐其中带图解、基于进位保存加法器的解释。
学习路径
读这篇之前,按顺序读书架上的 3 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出候选只有 Roaring 位图及其依赖的向量化整数压缩工作,这条路径帮你先看 SIMD 在位图和整数压缩中的应用,再读 popcount 的向量化。
- 1
展示用 SIMD 向量化加速整数解码,是同类 SIMD 优化的背景。
读向量化整数压缩的基本思想。
- 2
Roaring 位图是 popcount 的典型应用场景之一。
读Roaring 的容器设计,以及基数计算在其中的位置。
- 3
Roaring 的后续版本,说明位图运算中计数与向量化的需求。
读位图容器与运行长度编码的混合设计。
- 4Faster Population Counts Using AVX2 Instructions
用 AVX2 向量化实现 popcount,比专用 popcnt 指令更快。
读AVX2 查表与位并行计数的算法,以及与 popcnt 的速度对比。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“It's shows how to count number of set bits with SIMD in a way that is faster than the using the builtin POPCNT instruction.”
“Vectorizing your tallies can yield log time speedups:”
“Because it's faster - Faster Population Counts Using AVX2 Instructions.”
“You can also go faster using SIMD instructions if you need to compute wider population counts”
- Faster Population Counts Using AVX2 Instructions ↗ingve · 2016-11-24 · 15 分
- Faster Population Counts Using AVX2 Instructions [pdf] ↗flipchart · 2021-07-28 · 3 分