二维矩阵遍历顺序调整后perf统计cache-references升高原因

实验背景 #

我偶然发现了一个介绍缓存感知编程的GitHub仓库，它关联了一篇同主题的博客文章。文章对比了数组内数据分布与缓存行大小的不同匹配关系下，perf输出中cache-references和cache-misses的数量差异。我希望自行完成类似实验，编写的初始行优先遍历代码如下：

// depth_first.c
#include <stdint.h>
#include <stdlib.h>
#define ROWS 100000
#define COLS 64

int main() {
    uint8_t (*mat)[COLS] = malloc(sizeof(uint8_t[ROWS][COLS])); // 分配二维矩阵

    uint8_t sum = 0;

    for(int row_idx = 0; row_idx < ROWS; row_idx++) {
        for(int col_idx = 0; col_idx < COLS; col_idx++) {
            sum += mat[row_idx][col_idx];
        }
    }

    free(mat);
}

注：我清楚malloc后未初始化数组属于未定义行为，但我不关心实际运算取值，且判断该操作不会影响缓存性能测试结果。

我动态分配了uint8_t类型的二维数组mat，维度为100000行、单行列宽64字节，数组内存布局如下：

[ Row 0, 64 bytes ][ Row 1, 64 bytes ][ Row 2, 64 bytes ]...[ Row 99999, 64 bytes ]

每一行占用连续内存空间，我特意选择64字节作为列宽——该值与我所用CPU的缓存行大小一致，单行数据可以完整放入单个缓存行。

实验设计 #

我准备了两个版本的遍历逻辑：

• 深度优先（行优先）遍历：访问完第一行的所有列元素后再移动到第二行，即上述初始代码的逻辑
• 广度优先（列优先）遍历：先遍历所有行的第一个元素，再遍历所有行的第二个元素，以此类推，对应循环代码如下：

// breadth_first.c 循环部分
for(int col_idx = 0; col_idx < COLS; col_idx++) { // 列索引作为外层循环
    for(int row_idx = 0; row_idx < ROWS; row_idx++) { // 行索引作为内层循环
        sum += mat[row_idx][col_idx];
    }
}

我使用无优化选项编译两个版本的代码：

gcc -O0 breadth_first.c -o breadth_first
gcc -O0 depth_first.c -o depth_first

之后使用perf工具开展测试：

perf stat -e cache-references,cache-misses ./breadth_first
perf stat -e cache-references,cache-misses ./depth_first

得到的测试输出如下（多次运行的数值和占比仅有小幅波动）：

Performance counter stats for './breadth_first':

        12 654 452      cache-references:u                                          
           106 456      cache-misses:u            #    0,841 % of all cache refs    

       0,015068004 seconds time elapsed

       0,015102000 seconds user
       0,000000000 seconds sys



 Performance counter stats for './depth_first':

           213 178      cache-references:u                                          
             5 901      cache-misses:u            #    2,768 % of all cache refs    

       0,026617312 seconds time elapsed

       0,026690000 seconds user
       0,000000000 seconds sys

预期与实际结果偏差 #

我原本预期两个版本的cache-references数量相近，列优先版本的cache-misses数量、占比更高。做出该预期的依据是两段代码逻辑等价，对二维数组的总内存访问次数完全一致。

但实际测试结果中，列优先版本的cache-references数量出现了大幅增长，尽管cache-misses绝对数量也有所上升，但列优先版本的缓存未命中占比反而更低（我推测大概率是因为总引用数基数过大，单独的占比数据不具备参考价值）。

环境补充 #

测试所用CPU为AMD品牌，我已经在内核源码中找到了perf事件ID到硬件事件ID的对应规则，目前正在查阅AMD官方处理器编程参考文档的对应章节，确认底层硬件事件的具体定义。

问题原因解答 #

核心原因是对perf通用事件cache-references的计数逻辑存在认知偏差，结合AMD处理器的缓存层级设计，具体可以拆为三点：

• cache-references不是总内存/缓存访问计数
  这个通用perf事件没有跨架构的统一定义，在AMD x86平台上，它映射的是L2缓存的接入请求数，既不统计L1缓存命中的访问，也不覆盖所有内存层级的操作。之前假设它统计所有缓存访问，是推导错误的根源。对应的cache-misses事件，在AMD平台上统计的是L2缓存未命中、需要向L3/内存发起请求的次数，也不是全局的缓存未命中总数。

• 两种遍历模式下L1缓存的命中率差异巨大，直接决定L2请求数

  • 行优先遍历是连续地址访问：每访问1个字节，硬件预取器会直接把整段64字节缓存行拉到L1数据缓存，后续同缓存行的63次访问全部在L1命中，根本不需要向L2发请求，只有每次缓存行换入、预取的时候才会产生L2访问，因此统计到的cache-references数值极低。
  • 列优先遍历的访问步长为64字节：每次访问都跳转到下一行的同列位置，也就是每一次访问都属于不同的缓存行。AMD消费级处理器的L1数据缓存通常为32KB，仅能容纳512个64字节缓存行，完全装不下遍历过程中跳着访问的10万个缓存行，因此绝大多数访问都会在L1未命中，必须向L2发起读请求，这些请求全部被计入cache-references，直接导致该数值暴涨到千万级。

• 低未命中率来自L2层的硬件预取
  列优先遍历的访问是固定64字节的规则步长，L2缓存的硬件流预取器很容易识别这个访问模式，提前把后续需要的缓存行拉到L2中，因此虽然发往L2的请求总数多，但绝大多数都能在L2命中，只有极少部分需要向下访问L3或内存，最终算出来的未命中占比反而更低——这个占比的分母是L2请求数，不是总内存访问数，自然和预期的结果不符。

另外补充两个实验设计的问题：

• 用-O0编译的代码循环寄存器分配、地址计算的开销占比极高，最终统计的运行时间参考价值很低，看到列优先版本运行时间更短就是编译优化没开导致的偏差。做缓存相关实验至少要开-O2优化，同时要避免编译器把遍历循环直接优化掉，可以把sum声明为volatile，或者最终打印sum的值。
• 未初始化的malloc内存默认映射到系统的零页写时复制区域，虽然不影响缓存计数逻辑，但部分平台的预取器对零页有特殊优化，最好还是给数组填个固定值再测试。

如果要统计真正的L1总访问数，不要用通用的cache-references事件，要查询所用AMD CPU型号的原生PMU事件，比如L1数据缓存访问事件，这类原生事件的计数两个版本应该基本一致，都在640万左右（100000行*64列的总访问次数）。

内容的提问来源于stack exchange，提问作者msaw328