SIMD Prefix Sum: 8.9 GiB/s with ARM NEON
核心发现： Daniel Lemire 展示了如何使用 ARM NEON 指令将前缀和（prefix sum）性能提升到 8.9 GiB/s，比标量方法快 2.3 倍。
什么是前缀和？
前缀和（Prefix Sum / Scan）是一种常见的数组操作：对于每个位置 i，计算从开始到 i 的所有元素之和。
// 标量实现
for (size_t i = 1; i < length; i++) {
data[i] += data[i - 1];
}
理论极限： 每个元素至少需要 1 个 CPU 周期。因此在 4 GHz 处理器上，每秒最多处理 40 亿个整数值。
SIMD 优化策略
关键创新：使用 NEON 的交错加载（interleaved load/store）同时处理 16 个值：
// 原始数据: ABCD EFGH IJKL MNOP // 加载后: AEIM BFJN CGKO DHLP // (每列单独做前缀和)
性能对比 (Apple M4 @ 4.5 GHz)
| 方法 | 吞吐量 (十亿值/秒) |
|---|---|
| 标量 (scalar) | 3.9 |
| 朴素 SIMD | 3.6 |
| 快速 SIMD | 8.9 |
结论： 优化的 SIMD 方法比标量方法快 2.3 倍，达到惊人的 8.9 十亿值/秒！
技术细节
核心算法使用：
vld4q_u32- 16 值交错加载vaddq_u32- SIMD 加法vextq_u32- 向量移位vdupq_laneq_u32- 广播最后元素
启示
这个案例说明：
- 简单的 SIMD 优化可能比不优化更慢
- 需要算法级创新（如交错加载）才能获得显著提升
- 现代处理器的性能潜力远超我们的直觉