比随机访问还慢 33%：一步步把现代 CPU 的缓存体系榨干

原文：Data Access Patterns That Makes Your CPU Really Angry — weineng / 2026-06-26

给定一个大数组，最慢的求和方式是什么？从左到右顺序加？随机跳着加？答案是——还能比随机访问再慢 33%。

这篇文章从一个看似无聊的问题出发，一步步拆解现代 CPU 的每一层缓存机制，最终构建出一个让所有硬件加速手段集体罢工的访问模式。过程比结论更有意思。

先约定规则。测试用 2^26 个 uint32_t 整数（65536 页 × 每页 1024 个），关闭大页，用 rdtsc 指令计 cycle 数。求和函数固定不变，我们只能改 positions 数组的内容——也就是访问顺序：

constexpr int ELEMENT_COUNT = (1 << 16) * (PAGE_SIZE / sizeof(uint32_t));  // 2^26

uint32_t accumulator(uint32_t const* data, uint32_t const* positions) {
    uint32_t total = 0;
    for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) {
        uint32_t pos = positions[i];
        total += data[pos];
    }
    return total;
}

测试机的 CPU 是 Intel Core Ultra 7 268V（Lunar Lake），8 核，L1d 48KB/12-way，L2 2.5MB/10-way，L3 12MB/12-way。

基准线：顺序访问 vs 随机访问

void linear(...) {
    for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) {
        positions[i] = i;
    }
}

顺序访问的耗时是 1.33 亿 cycles。CPU 的硬件预取器和缓存策略对顺序访问做了重度优化，这在意料之中。

Fisher-Yates 洗牌打乱访问顺序后：

void fisher_yates_shuffle(...) {
    linear(data, positions);
    uint32_t remaining = ELEMENT_COUNT;
    for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) {
        uint32_t random = rand() % remaining;
        // swap positions[i] and positions[i + random]
        ...
        --remaining;
    }
}

随机访问耗时 15.7 亿 cycles，已经是顺序访问的 10 倍以上。CPU 无法预测下一次访问的位置，预取器形同虚设。

第一刀：按 cache line 错开

CPU 的缓存以 64 字节的 cache line 为最小单位调度。如果连续两次访问间隔一个 cache line（每个 cache line 含 16 个 uint32_t），程序的行为变成这样：用掉一个 cache line 的一个 4 字节整数就跳到下一个，等回头再用这个 cache line 时，它早就被逐出了。

// 先把所有 cache line 的第一个元素遍历完，再遍历所有 cache line 的第二个元素……
void separated_by_a_cacheline(...) {
    constexpr int element_count_per_cacheline = CACHELINE_SIZE / sizeof(uint32_t);
    constexpr int cacheline_count = ELEMENT_COUNT / element_count_per_cacheline;
    int current = 0;
    for (int element_index = 0; element_index < element_count_per_cacheline; ++element_index) {
        for (int cacheline_index = 0; cacheline_index < cacheline_count; ++cacheline_index) {
            positions[current] = cacheline_index * element_count_per_cacheline + element_index;
            ++current;
        }
    }
}

结果：7.19 亿 cycles，已经是顺序访问的 4 倍——但还不到随机访问的一半。

硬件预取器还能识别这种步进式的 stream 模式，提前把未来的 cache line 拉进来。不过 Intel 的硬件预取器大多不会跨 4KB 页边界做预取——跨页意味着需要另一次虚拟地址到物理地址的转换，相邻虚拟页未必对应相邻物理页，做跨页投机预取风险太高。

第二刀：按页错开

既然跨 cache line 还不足以废掉预取器，那就跨页——每个页 4096 字节，每次间隔一整个页。

void separated_by_a_page(...) {
    constexpr int element_count_per_page = PAGE_SIZE / sizeof(uint32_t);
    constexpr int page_count = ELEMENT_COUNT / element_count_per_page;
    int current = 0;
    for (int element_index = 0; element_index < element_count_per_page; ++element_index) {
        for (int page_index = 0; page_index < page_count; ++page_index) {
            positions[current] = page_index * element_count_per_page + element_index;
            ++current;
        }
    }
}

耗时显著恶化到 14.1 亿 cycles。除了预取器被废掉之外，还有另一层效应——组相联缓存的 placement policy。

大多数家用 CPU 的缓存采用组相联策略。给定地址的 cache line 只能映射到特定的 cache set。这台机器的 L1d 有 64 个 set，每个 set 有 12 个 way（槽位）。地址 A 和 A+4096（64 sets × 64B cache line）会映射到同一个 L1d set，必须竞争这 12 个槽位。

按页步进时，内层循环反复命中同一个 set，而不是均匀分布到 64 个 set 上。L1d 名义上有 48KB 容量，在这种访问模式下实际可用的只有 768B（12 way × 64B）。

第三刀：同时按页和 cache line 错开

当前的访问模式是：

page 0, cacheline 0, elem 0
page 1, cacheline 0, elem 0
...
page 65535, cacheline 0, elem 0
page 0, cacheline 0, elem 1
...

每访问 65536 个 cache line 后回到同一个 cache line。cache line 重用距离是 65536 次访问。

可以把这个距离拉得更大——把 cache line 也交错进来：

void separated_by_a_page_and_cacheline(...) {
    for (int element_index_in_cacheline = 0; ...) {
        for (int cacheline_index_in_page = 0; ...) {
            for (int page_index = 0; page_index < page_count; ++page_index) {
                positions[current++] = page_index * elements_per_page
                    + cacheline_index_in_page * elements_per_cacheline
                    + element_index_in_cacheline;
            }
        }
    }
}

cache line 重用距离暴增到 400 万（65536 pages × 4096 / 64）。但实测结果却是没变，还是 14.1 亿 cycles。

原因在于这台机器的缓存拓扑。测试用的 core 3 有 2.5MB L2 + 48KB L1d，总共约 2.5MB 私有缓存。遍历 65536 个页已经触及 4MB 的数据量，超出了私有缓存的覆盖范围。所以不管重用距离是 6 万还是 400 万，需要的 cache line 都已经不在 L1/L2 里了。L3 虽然更大，但延迟更高，且受限于自己的组相联和替换策略。

第四刀：8 页步进——废掉页表缓存

当前访问模式按连续页遍历。把步长从 1 改成 N，让页面跨越更大：

template <int page_stride>
void separated_by_stride_pages_and_cacheline(...) {
    for (int element_index_in_cacheline = 0; ...) {
        for (int cacheline_index_in_page = 0; ...) {
            for (int page_start = 0; page_start < page_stride; ++page_start) {
                for (int page_index = page_start; page_index < page_count; page_index += page_stride) {
                    positions[current++] = page_index * elements_per_page + ...;
                }
            }
        }
    }
}

不同步长下的 cycle 数：

page stride	cycles
1	14.1 亿
2	~17 亿
4	~19 亿
8	20.6 亿
16	~18 亿
32	~15 亿

步长 8 是个明显的峰值，比随机访问还慢 31%。

这个现象的根因在页表条目（PTE）。每次访问虚拟地址时，MMU 都要查页表做地址翻译。PTE 占 8 字节，一个 cache line 能装 8 个 PTE。以 8 页步进时，每次数据访问都恰好需要加载一个新的 cache line 来做地址翻译——也就是说，每访问一个数据，就要额外访问一次内存来查页表。数据和页表条目一起把缓存撑爆了。

第五刀：DRAM row buffer 冲突

到此为止，缓存体系已经被榨得差不多了。还剩一层可以攻击——DRAM 控制器。

DRAM 内部按 channel → rank → chip → bank → row → column 的层次组织。每个 bank 有自己的 row buffer（行缓冲区）。访问同一行的不同列时是 row buffer hit，延迟很低。切换到不同行时，必须先 precharge 关闭当前行、再 activate 新行，延迟暴涨。

同一个 rank 的不同 bank 可以并行操作。从 DRAM 控制器的角度看，把请求均匀分布到多个 bank 上能最大化吞吐。要让它难受，就应该把请求全部集中在同一个 bank 里，且每次都访问不同 row，强制产生 row buffer miss。

问题在于：物理地址到 DRAM channel/rank/bank/row 的映射关系是未文档化的，随 CPU 型号、BIOS 设置、通道配置而变。作者参考 DRAMA 论文做了一些本地实验来估算映射关系：

constexpr uint32_t DRAM_BANK_GROUP_COUNT = 4;
constexpr uint32_t DRAM_BANK_COUNT_PER_GROUP = 4;
constexpr uint32_t DRAM_ROW_SHIFT = 18;  // 实测 15~19 范围

DramLocation physical_address_to_dram_location(uint64_t physical_address, uint32_t page_index) {
    uint64_t bg0 = get_bit(7) ^ get_bit(14);
    uint64_t bg1 = get_bit(15) ^ get_bit(19);
    uint64_t bg = bg1 * 2 + bg0;
    uint64_t ba0 = get_bit(17) ^ get_bit(21);
    uint64_t ba1 = get_bit(18) ^ get_bit(22);
    uint64_t ba = ba1 * 2 + ba0;
    return {
        .bank_index = bg * DRAM_BANK_COUNT_PER_GROUP + ba,
        .rank = 0,
        .channel = 0,
        .row_index = physical_address >> DRAM_ROW_SHIFT,
    };
}

加上 DRAM bank 冲突模式后，最终耗时 20.8 亿 cycles——相比纯 8 页步进只有小幅提升。原因有二：一是 bank hash 函数和 row shift 参数只是近似值；二是 8 页步进（约 32KB 间隔）的数据本来就不会落在同一个 DRAM row 里，row buffer 冲突并不多。Intel 的 bank hash 仍然让请求分散到了多个 bank，没法完全收窄到单个 bank。

最终战报

linear:                                     132,752,394  (1.0×)
separated_by_a_cacheline:                   718,804,156  (5.4×)
separated_by_a_page:                      1,411,153,154  (10.6×)
separated_by_a_page_and_cacheline:        1,408,519,172  (10.6×)
fisher_yates_shuffle:                     1,572,108,618  (11.8×)
stride=8 separated_by_stride_pages...:    2,058,425,640  (15.5×)
stride=8 + bank conflicts:                2,082,308,014  (15.7×)

从顺序访问的 1.33 亿 cycles 到最终的 20.8 亿 cycles，慢了 15 倍多。比「直觉上最慢」的随机访问还差了 33%。

攻击路径从高到低：cache line 粒度 → 页粒度预取器 → L1d 组相联冲突 → PTE 缓存污染 → DRAM row buffer 冲突。每一层挨个打穿。

附录：Lobsters 评论区讨论摘要

文章在 Lobsters 上 43 个赞，5 条评论。几个值得提的讨论：

1. Windows 11 性能梗

benj 调侃：“原来 Windows 11 内部性能研究的日常就是这样啊（/s）。有趣的一篇！”

2. 前 AI 时代的缓存探测工具

ob 分享了他的 cache 仓库，核心代码手写于 2009 年左右，远在 AI 辅助编程之前。Sietsebb 追问 README 中两处引用的关系——Computer Architecture: A Quantitative Approach 教材里的练习 vs Saavedra-Barrera 的博士论文。ob 回复确认教材引用了论文，他追踪到了原始出处；README 里的混乱措辞他承认是 Claude 改出来的问题，已修正。

ob 说了一个有趣的用法：他每换一台新机器，都会跑这套分析来摸清内存层次和延迟特征。这思路和原文的攻击实验异曲同工——只不过一个是”怎么让它快”，一个是”怎么让它慢”。

3. Java 移植对比

trenchant 用 Claude 把 benchmark 翻译到了 Java，用了 SafeNumber 包装类。结果：C++ 线性访问 1026 万 ns，Java 版本 3674 万 ns（3.6×）；Fisher-Yates 随机化后 C++ 2.65 亿 ns，Java 5.36 亿 ns（只有 2× 差距了）。随机访问下装箱开销的相对占比下降了很多——因为 cache miss 成了主导因素，语言层面的差异被内存延迟淹没了。

原文链接：blog.weineng.me/posts/slowest_add

Lobsters 讨论：lobste.rs/s/xmsj3r

相关仓库：github.com/ob/cache — 内存层次探测工具

以上分析基于原文和 Lobsters 社区的公开讨论。如果你有更深的一手经验或发现了更慢的访问模式，欢迎讨论。