一个数组遍历慢了 10 倍
同样是对一个二维数组求和,把循环顺序调换一下,耗时能差出 10 倍以上。这不是编译器优化的问题,而是 CPU 缓存行(cache line) 在作祟。
缓存行是什么
CPU 从内存取数据时不是按字节,而是按 64 字节一行的粒度搬进 L1/L2/L3 缓存。当你访问 a[i][j] 时,它所在的整行以及相邻的 7 个元素都会一起被载入缓存。
// 行优先:连续访问,缓存命中率高
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum += a[i][j];
// 列优先:每次跳跃一整行,缓存反复失效
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum += a[i][j];
实测数据
| N | 行优先 | 列优先 | 倍数 |
|---|---|---|---|
| 1024 | 3.1 ms | 11.2 ms | 3.6× |
| 4096 | 51 ms | 560 ms | 11× |
| 8192 | 205 ms | 2.4 s | 11.7× |
伪共享(False Sharing)
多线程时另一个坑:两个线程分别修改两个“不同”的变量,但它们恰好落在同一条缓存行里。CPU 的缓存一致性协议会让这条行在两个核心之间来回“抢夺”,性能反而比单线程更差。
// 两个计数器相邻,位于同一条 64 字节缓存行
struct { long a; long b; } counters;
// 解决:填充到不同缓存行
struct { long a; char pad[56]; long b; } padded;
性能问题先测量再优化:perf stat 看 cache-misses,比直觉可靠得多。
— 完 —