性能工程的绝对宝藏资源。

我正在研读 Algorithmica 的高性能计算系列，其中关于 CPU 缓存的部分尤为出色。

它详细解析了缓存延迟、内存访问模式、指针追踪、预取机制以及底层运作原理。

如果你致力于编写更高效的软件，请务必收藏此资源。

https://en.algorithmica.org/hpc/cpu-cache/latency/…

内存延迟 - Algorithmica

来源：https://en.algorithmica.org/hpc/cpu-cache/latency/ 尽管带宽 (https://en.algorithmica.org/hpc/cpu-cache/bandwidth) 是更复杂的概念，但相比延迟它更容易观测和测量：只需执行一系列独立的读或写查询，调度器可以提前获知这些操作，并对其进行重排序和并行处理，从而隐藏延迟并最大化总吞吐量。

为了测量延迟，我们需要设计一个让 CPU 无法通过提前知晓内存请求地址来“作弊“的实验。确保这一点的方法之一是生成一个大小为 N 的随机排列，并使其构成一个循环，然后反复追踪该排列：

`` int p[N], q[N];

// 生成随机排列 iota(p, p + N, 0); random_shuffle(p, p + N);

// 该排列可能包含多个循环， // 因此我们用它来构建另一个单循环排列 int k = p[N - 1]; for (int i = 0; i < N; i++) k = q[k] = p[i];

for (int t = 0; t < K; t++) for (int i = 0; i < N; i++) k = q[k]; ``

与线性遍历相比，用这种方式访问数组所有元素会慢得多——达到数个数量级。这不仅使得 SIMD (https://en.algorithmica.org/hpc/simd) 无法发挥作用，还会导致流水线停顿 (https://en.algorithmica.org/hpc/pipelining)，造成大量指令拥堵，所有指令都在等待从内存中获取单个数据。

这种性能反模式被称为指针追踪，在数据结构中非常常见，尤其常见于高级语言编写的程序，这些程序大量使用堆分配的对象及为其动态类型系统所必需的指针。

讨论延迟时，使用周期或纳秒比吞吐量单位更有意义，因此我们用倒数图替换此图：

请注意，两张图上的“悬崖“不如带宽图那样明显。这是因为即使数组无法完全放入某层缓存，我们仍有概率命中其上一层缓存。

# (https://en.algorithmica.org/hpc/cpu-cache/latency/#theoretical-latency)理论延迟

更形式化地描述，如果缓存层次结构中有 k 级，各级大小为 s\_i，延迟为 l\_i，那么预期延迟并非等于最慢访问的延迟，而是：

E\[L\] = \\frac\{ s\_1 \\cdot l\_1 \+ \(s\_2 \- s\_1\) \\cdot l\_2 % \+ \(s\_3 \- s\_2\) \cdot l\_3 \+ \\ldots \+ \(N \- s\_k\) \\cdot l\_\{RAM\} \}\{N\} 如果我们抽象掉最慢缓存层之前的所有过程，可以将公式简化为： E\[L\] = \\frac\{N \\cdot l\_\{last\} \- C\}\{N\} = l\_\{last\} \- \\frac\{C\}\{N\} 随着 N 增大，预期延迟逐渐接近 l\_\{last\}，如果你仔细观察，吞吐量（延迟的倒数）的图像看起来大致像由几个转置和缩放的双曲线组成： \\begin\{aligned\} E\[L\]^\{\-1\} &= \\frac\{1\}\{l\_\{last\} \- \\frac\{C\}\{N\}\} \\\\ &= \\frac\{N\}\{N \\cdot l\_\{last\} \- C\} \\\\ &= \\frac\{1\}\{l\_\{last\}\} \\cdot \\frac\{N \+ \\frac\{C\}\{l\_\{last\}\} \- \\frac\{C\}\{l\_\{last\}\}\}\{N \- \\frac\{C\}\{l\_\{last\}\}\} \\\\ &= \\frac\{1\}\{l\_\{last\}\} \\cdot \\left\(\\frac\{1\}\{N \\cdot \\frac\{l\_\{last\}\}\{C\} \- 1\} \+ 1\\right\) \\\\ &= \\frac\{1\}\{k \\cdot \(x \- x\_0\)\} \+ y\_0 \\end\{aligned\} 要获得实际延迟数值，我们可以迭代应用第一个公式推导出 l\_1，然后是 l\_2，依此类推。或者直接查看悬崖前的数值——它们应在真实延迟的 10-15% 误差范围内。

测量延迟还有更直接的方法，包括使用非时间性读操作 (https://en.algorithmica.org/hpc/cpu-cache/bandwidth)，但此基准测试更能反映实际的访问模式。

# (https://en.algorithmica.org/hpc/cpu-cache/latency/#frequency-scaling)频率缩放

与带宽类似，所有 CPU 缓存的延迟会随其时钟频率成比例缩放，而 RAM 则不会。当我们通过开启睿频改变频率时，也能观察到这种差异。

将图表绘制为相对加速比后，会更有意义。

对于完全放入 CPU 缓存的数组大小，你预期会有 2 倍速率提升，但对于存储在 RAM 中的数组则大致相同。但实际情况并非完全如此：即使对于 RAM 访问，在较低时钟频率下运行仍存在一个固定的延迟开销。这是因为 CPU 在向主存发送读取查询前，必须先检查其缓存——以节省 RAM 带宽给其他可能需要它的进程。

内存延迟还轻微受到虚拟内存实现细节 (https://en.algorithmica.org/hpc/cpu-cache/paging) 和 RAM 特定时序 (https://en.algorithmica.org/hpc/cpu-cache/mlp) 的影响，我们稍后将讨论这些内容。