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

Faster Population Counts Using AVX2 Instructions

用 AVX2 指令加速人口计数
Wojciech Muła, Nathan Kurz, Daniel Lemire · 2016

用 AVX2 向量化实现 popcount,比专用 popcnt 指令快约一倍

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 6 人首次 2016-11-24 · 最近 2021-07-28
6不同的人
7活跃月份
7讨论串
60被引(OpenAlex)

统计二进制流中 1 的个数是数据库、信息检索、密码学和机器学习中的常见操作。论文表明,在近期的 Intel 处理器上,基于 SIMD 的向量化方法可以比专用的 popcnt 指令快约两倍;在需要额外布尔运算的相似度度量(如 Jaccard 指数)中收益更大。该方法已被 LLVM 采用,用于 clang 编译器。

HN 为什么提它

评论者用它说明为何手写 SIMD 的 popcount 能比内建 POPCNT 指令更快,并推荐其中带图解、基于进位保存加法器的解释。

方法难度 3 / 5约 20 分钟经得起时间
读之前最好知道
1SIMD 与 AVX2 指令
2位运算与 popcount
3进位保存加法器(carry-save adder)
4CPU 微架构基础

学习路径

读这篇之前,按顺序读书架上的 3 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

候选只有 Roaring 位图及其依赖的向量化整数压缩工作,这条路径帮你先看 SIMD 在位图和整数压缩中的应用,再读 popcount 的向量化。

  1. 1
    Decoding billions of integers per second through vectorization通过向量化每秒解码数十亿整数 · 2012

    展示用 SIMD 向量化加速整数解码,是同类 SIMD 优化的背景。

    读向量化整数压缩的基本思想。

  2. 2

    Roaring 位图是 popcount 的典型应用场景之一。

    读Roaring 的容器设计,以及基数计算在其中的位置。

  3. 3
    Consistently faster and smaller compressed bitmaps with Roaring更快更小的压缩位图:Roaring · 2016

    Roaring 的后续版本,说明位图运算中计数与向量化的需求。

    读位图容器与运行长度编码的混合设计。

  4. 4
    Faster Population Counts Using AVX2 Instructions用 AVX2 指令加速人口计数 · 2016 · 就是这篇

    用 AVX2 向量化实现 popcount,比专用 popcnt 指令更快。

    读AVX2 查表与位并行计数的算法,以及与 popcnt 的速度对比。

HN 书评

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

“we tried to give a clear explanation (with diagrams) of how it can be faster to roll your own popcnt using Carry-Save-Adders:”

推荐其中用 Carry-Save-Adders 自己实现 popcnt 的图解说明
Abusing the CPU's Adder Circuits原评论 ↗
引用nkurz · 2016-12

“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.”

介绍用 SIMD 数置位比内置 POPCNT 指令更快
Don’t assume that safety comes for free: a Swift case study原评论 ↗
引用indescions_2018 · 2018-05

“Vectorizing your tallies can yield log time speedups:”

引用它说明向量化计数可带来对数级加速
Low Level Bit Hacks You Absolutely Must Know原评论 ↗
引用eesmith · 2019-09

“Because it's faster - Faster Population Counts Using AVX2 Instructions.”

引用它回答为什么 AVX2 实现比原生指令更快
Popcount CPU instruction原评论 ↗
引用dlemire · 2021-06

“You can also go faster using SIMD instructions if you need to compute wider population counts”

指出需要更宽的 population count 时可用 SIMD 指令加速
The NSA Instruction (2019)原评论 ↗
被提交为 story · 2 次