CPU缓存如何影响C程序的性能
How does the CPU cache affect the performance of a C program
我想更多地了解 CPU 缓存如何影响性能。作为一个简单的测试，我将总列数不同的矩阵第一列的值相加。
// compiled with: gcc -Wall -Wextra -Ofast -march=native cache.c
// tested with: for n in {1..100}; do ./a.out $n; done | tee out.csv
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
double sum_column(uint64_t ni, uint64_t nj, double const data[ni][nj])
{
double sum = 0.0;
for (uint64_t i = 0; i < ni; ++i) {
sum += data[i][0];
}
return sum;
}
int compare(void const* _a, void const* _b)
{
double const a = *((double*)_a);
double const b = *((double*)_b);
return (a > b) - (a < b);
}
int main(int argc, char** argv)
{
// set sizes
assert(argc == 2);
uint64_t const iter_max = 101;
uint64_t const ni = 1000000;
uint64_t const nj = strtol(argv[1], 0, 10);
// initialize data
double(*data)[nj] = calloc(ni, sizeof(*data));
for (uint64_t i = 0; i < ni; ++i) {
for (uint64_t j = 0; j < nj; ++j) {
data[i][j] = rand() / (double)RAND_MAX;
}
}
// test performance
double* dt = calloc(iter_max, sizeof(*dt));
double const sum0 = sum_column(ni, nj, data);
for (uint64_t iter = 0; iter < iter_max; ++iter) {
clock_t const t_start = clock();
double const sum = sum_column(ni, nj, data);
clock_t const t_stop = clock();
assert(sum == sum0);
dt[iter] = (t_stop - t_start) / (double)CLOCKS_PER_SEC;
}
// sort dt
qsort(dt, iter_max, sizeof(*dt), compare);
// compute mean dt
double dt_mean = 0.0;
for (uint64_t iter = 0; iter < iter_max; ++iter) {
dt_mean += dt[iter];
}
dt_mean /= iter_max;
// print results
printf("%2lu %.8e %.8e %.8e %.8e\n", nj, dt[iter_max / 2], dt_mean, dt[0],
dt[iter_max - 1]);
// free memory
free(data);
}
然而，结果与我预期的不太一样：
据我了解，当 CPU 从 data 加载一个值时，它还会将 data 的以下一些值放入缓存中。确切的数字取决于缓存行大小（在我的机器上是 64 字节）。这可以解释，为什么随着 nj 的增长，解决方案的时间首先线性增加并在某个值处趋于平稳。如果 nj == 1，一次加载会将接下来的 7 个值放入缓存中，因此我们只需要每第 8 个值从 RAM 加载一次。如果 nj == 2，遵循相同的逻辑，我们需要每 4 个值访问一次 RAM。在一定大小之后，我们将不得不为每个值访问 RAM，这应该会导致性能趋于平稳。我的猜测是，为什么图表的线性部分比 4 更远是因为实际上这里有多个级别的缓存在工作，并且值在这些缓存中结束的方式比我在这里解释的要复杂一些。
我无法解释的是为什么这些性能峰值出现在 16 的倍数处。
稍微思考一下这个问题后，我决定检查 nj 的较高值是否也会出现这种情况：
事实上，确实如此。而且，还有更多：为什么性能在 ~250 之后再次提升？
有人可以向我解释一下，或者给我一些适当的参考，为什么会有这些峰值以及为什么性能会随着 nj 的更高值而提高。
如果您想自己尝试代码，为了方便起见，我还会附上我的绘图脚本：
import numpy as np
import matplotlib.pyplot as plt
data = np.genfromtxt("out.csv")
data[:,1:] /= data[0,1]
dy = np.diff(data[:,2]) / np.diff(data[:,0])
for i in range(len(dy) - 1):
if dy[i] - dy[i + 1] > (dy.max() - dy.min()) / 2:
plt.axvline(data[i + 1,0], color='gray', linestyle='--')
plt.text(data[i + 1,0], 1.5 * data[0,3], f"{int(data[i + 1,0])}",
rotation=0, ha="center", va="center",
bbox=dict(boxstyle="round", ec='gray', fc='w'))
plt.fill_between(data[:,0], data[:,3], data[:,4], color='gray')
plt.plot(data[:,0], data[:,1], label="median")
plt.plot(data[:,0], data[:,2], label="mean")
plt.legend(loc="upper left")
plt.xlabel("nj")
plt.ylabel("dt / dt$_0$")
plt.savefig("out.pdf")
这些图显示了几种复杂 low-level 影响的组合（主要是 缓存垃圾处理 和 预取 问题）。我假设目标平台是具有 64 字节高速缓存行的主流现代处理器（通常是 x86 处理器）。
我可以在我的 i5-9600KF 处理器上重现该问题。这是结果图：
首先，当nj较小时，获取地址之间的差距（即步幅）较小，缓存行的使用效率相对较高。例如，当nj = 1时，访问是连续的。在这种情况下，处理器可以有效地预取 DRAM 中的高速缓存行，从而隐藏其高延迟。还有一个很好的 空间缓存位置 因为许多连续的项目共享相同的缓存行。当nj=2时，只使用缓存行的一半值。这意味着对于相同数量的操作，请求的缓存行数量是原来的两倍。话虽这么说，由于添加两个 floating-point 数字 导致 compute-bound[=121 的相对 高延迟，时间并没有增加很多=] 代码。您可以 展开循环 4 次并使用 4 个不同的总和变量，以便（主流的现代）处理器可以并行添加多个值。请注意，大多数处理器还可以在每个周期从缓存中加载多个值。当 nj = 4 每 2 个周期请求一个新的缓存行（因为 double 占用 8 个字节）。结果，内存吞吐量会变得如此之大，以至于计算量变成 memory-bound。人们可能期望 nj >= 8 的时间稳定，因为请求的缓存行的数量应该相同，但实际上处理器 预取多个连续的缓存行 所以不要支付DRAM 延迟的开销在这种情况下是巨大的。预取缓存行的数量通常在 2 到 4 之间（据我所知，当步幅大于 512 时，英特尔处理器会禁用这种预取策略，因此当 nj >= 64 时）。这解释了为什么当 [=21 时时间急剧增加=] 并且它们在 32 <= nj <= 256 时变得相对稳定，但峰值除外。
当 nj 是 16 的倍数时出现的常规峰值是由于称为 缓存抖动 的复杂缓存效应造成的。现代缓存 N-way associative，N 通常在 4 到 16 之间。例如，这里是我的 i5-9600KF 处理器的统计数据：
Cache 0: L1 data cache, line size 64, 8-ways, 64 sets, size 32k
Cache 1: L1 instruction cache, line size 64, 8-ways, 64 sets, size 32k
Cache 2: L2 unified cache, line size 64, 4-ways, 1024 sets, size 256k
Cache 3: L3 unified cache, line size 64, 12-ways, 12288 sets, size 9216k
这意味着如果 (A1 % 32768) / 64 == (A2 % 32768) / 64，从具有各自地址 A1 和 A2 的 DRAM 中获取的两个值可能会导致我的 L1 缓存发生冲突。在这种情况下，处理器需要从一组 N=8 缓存行中选择要 替换 的缓存行。有很多cache replacement policy and none is perfect. Thus, some useful cache line are sometime evicted too early resulting in additional cache misses required later. In pathological cases, many DRAM locations can compete for the same cache lines resulting in excessive cache misses. More information about this can be found also in this post.
关于nj步幅，一级缓存中可以有效使用的缓存行数是有限的。例如，如果所有获取的值都具有相同的地址模缓存大小，那么实际上只有 N 个缓存行（对于我的处理器是 8 个）可以用来存储所有值。可用的缓存行较少是一个大问题，因为 预取器需要在缓存 中有相当大的 space 以便存储以后需要的许多缓存行。 并发取数越小，内存吞吐量越低。这在这里尤其如此，因为从 DRAM 中获取 1 个缓存行的延迟大约是几十纳秒（例如 ~70 ns），而其带宽大约是几十 GiB/s（例如 ~40 GiB/s): 应该同时获取数十个缓存行（例如~40），以隐藏延迟并使 DRAM 饱和。
这里是模拟我的一级缓存实际可以使用的缓存行数关于nj的值：
nj #cache-lines
1 512
2 512
3 512
4 512
5 512
6 512
7 512
8 512
9 512
10 512
11 512
12 512
13 512
14 512
15 512
16 256 <----
17 512
18 512
19 512
20 512
21 512
22 512
23 512
24 512
25 512
26 512
27 512
28 512
29 512
30 512
31 512
32 128 <----
33 512
34 512
35 512
36 512
37 512
38 512
39 512
40 512
41 512
42 512
43 512
44 512
45 512
46 512
47 512
48 256 <----
49 512
50 512
51 512
52 512
53 512
54 512
55 512
56 512
57 512
58 512
59 512
60 512
61 512
62 512
63 512
64 64 <----
==============
80 256
96 128
112 256
128 32
144 256
160 128
176 256
192 64
208 256
224 128
240 256
256 16
384 32
512 8
1024 4
我们可以看到，当 nj 是 16 的倍数时，可用缓存行的数量较少。在这种情况下，prefetecher 会将数据预加载到缓存行中，这些缓存行可能会被后续提取的 (同时进行）。在代码中执行的加载指令 在可用缓存行数较少时更有可能导致缓存未命中 。当发生缓存未命中时，需要再次从 L2 甚至 L3 中获取值，从而导致执行速度变慢。请注意，L2 缓存也受到相同的影响，尽管它由于更大而不太明显。 现代 x86 处理器的 L3 缓存利用散列来更好地分布事物以减少固定步幅的冲突（至少在英特尔处理器上，当然在 AMD 上也是如此，尽管据我所知这是 not documented).
这是我机器上某些峰值的时间：
32 4.63600000e-03 4.62298020e-03 4.06400000e-03 4.97300000e-03
48 4.95800000e-03 4.96994059e-03 4.60400000e-03 5.59800000e-03
64 5.01600000e-03 5.00479208e-03 4.26900000e-03 5.33100000e-03
96 4.99300000e-03 5.02284158e-03 4.94700000e-03 5.29700000e-03
128 5.23300000e-03 5.26405941e-03 4.93200000e-03 5.85100000e-03
192 4.76900000e-03 4.78833663e-03 4.60100000e-03 5.01600000e-03
256 5.78500000e-03 5.81666337e-03 5.77600000e-03 6.35300000e-03
384 5.25900000e-03 5.32504950e-03 5.22800000e-03 6.75800000e-03
512 5.02700000e-03 5.05165347e-03 5.02100000e-03 5.34400000e-03
1024 5.29200000e-03 5.33059406e-03 5.28700000e-03 5.65700000e-03
正如预期的那样，在可用缓存行数少得多的情况下，实践中的时间总体上更大。然而，当 nj >= 512 时，结果令人惊讶，因为它们比其他方法快得多。这是可用缓存行数等于的情况结合律的方式数 (N)。我的猜测是，这是因为英特尔处理器肯定会检测到这种病态情况并优化预取以减少缓存未命中的次数（使用 line-fill 缓冲区绕过 L1 缓存 - 见下文）。
最后，对于较大的 nj 步幅，更大的 nj 应该会导致更高的开销，这主要是由于 translation lookaside buffer (TLB)：有更多的页面地址需要用更大的nj 并且 TLB 条目的数量是有限的。事实上，这就是我在我的机器上观察到的情况：与您的目标平台不同，计时往往会以非常稳定的方式缓慢增加。
我还不能真正解释这种非常奇怪的行为。
以下是一些大胆的猜测：
- OS 当
nj 很大时，OS 可能倾向于使用更多大页面（以减少 TLB 的开销），因为分配了更宽的块。这可能会导致预取器的并发性更高，因为 AFAIK 它不能跨页
界限。您可以尝试检查已分配（透明）huge-pages 的数量（通过查看 AnonHugePages in /proc/meminfo in Linux）或在这种情况下强制使用它们（使用显式 memmap)，或者可能通过禁用它们。我的系统似乎独立于 nj 值使用 2 MiB 透明 huge-pages。
- 如果目标架构是 NUMA 架构（例如，新的 AMD 处理器或具有多个处理器的服务器有自己的内存），那么 OS 可以分配物理存储在另一个 NUMA 节点上的页面，因为有less space 在当前 NUMA 节点上可用。由于更大的吞吐量（尽管延迟更高），这可能会导致更高的性能。您可以在 Linux 上使用
numactl 控制此策略，以便强制进行本地分配。
有关此主题的更多信息，请阅读精彩文档 What Every Programmer Should Know About Memory. Moreover, a very good post about how x86 cache works in practice is available 。
去除峰
要消除 x86 处理器上缓存垃圾造成的峰值，您可以使用 non-temporal 软件预取指令，这样缓存行就可以在 non-temporal 缓存结构并放入靠近处理器的位置，该位置不应导致 L1 中的缓存垃圾（如果可能）。这种缓存结构通常是 Intel 处理器上的 line-fill buffers (LFB) 和 AMD Zen 处理器上的（等效）未命中地址缓冲区 (MAB)。有关 non-temporal 指令和 LFB 的更多信息，请阅读 and 。这是修改后的代码，其中还包括循环展开优化，以在 nj 较小时加快代码速度：
double sum_column(uint64_t ni, uint64_t nj, double* const data)
{
double sum0 = 0.0;
double sum1 = 0.0;
double sum2 = 0.0;
double sum3 = 0.0;
if(nj % 16 == 0)
{
// Cache-bypassing prefetch to avoid cache trashing
const size_t distance = 12;
for (uint64_t i = 0; i < ni; ++i) {
_mm_prefetch(&data[(i+distance)*nj+0], _MM_HINT_NTA);
sum0 += data[i*nj+0];
}
}
else
{
// Unrolling is much better for small strides
for (uint64_t i = 0; i < ni; i+=4) {
sum0 += data[(i+0)*nj+0];
sum1 += data[(i+1)*nj+0];
sum2 += data[(i+2)*nj+0];
sum3 += data[(i+3)*nj+0];
}
}
return sum0 + sum1 + sum2 + sum3;
}
修改后的代码结果如下：
我们可以看到峰值不再出现在时序中。我们还可以看到，由于 dt0 小了大约 4 倍（由于循环展开），这些值要大得多。
请注意，在实践中（至少在 Intel 处理器上），使用此方法无法避免 L2 缓存中的缓存垃圾。这意味着效果仍然存在，在我的机器上 nj 跨度是 512 (4 KiB) 的倍数（实际上比以前慢了，尤其是 nj >= 2048 时）。在 x86 处理器上 (nj%512) == 0 && nj >= 512 时停止预取可能是个好主意。影响 AFAIK，没有办法解决这个问题。也就是说，对 very-large 数据结构执行如此大的跨步访问是一个非常糟糕的主意。
请注意，应谨慎选择 distance，因为提前预取可能会导致缓存行在实际使用之前被逐出（因此需要再次获取它们），而延迟预取则用处不大。我认为使用接近 LFB/MAB 中条目数的值是个好主意（例如 Skylake/KabyLake/CannonLake 上的 12，Zen-2 上的 22）。
我想更多地了解 CPU 缓存如何影响性能。作为一个简单的测试，我将总列数不同的矩阵第一列的值相加。
// compiled with: gcc -Wall -Wextra -Ofast -march=native cache.c
// tested with: for n in {1..100}; do ./a.out $n; done | tee out.csv
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
double sum_column(uint64_t ni, uint64_t nj, double const data[ni][nj])
{
double sum = 0.0;
for (uint64_t i = 0; i < ni; ++i) {
sum += data[i][0];
}
return sum;
}
int compare(void const* _a, void const* _b)
{
double const a = *((double*)_a);
double const b = *((double*)_b);
return (a > b) - (a < b);
}
int main(int argc, char** argv)
{
// set sizes
assert(argc == 2);
uint64_t const iter_max = 101;
uint64_t const ni = 1000000;
uint64_t const nj = strtol(argv[1], 0, 10);
// initialize data
double(*data)[nj] = calloc(ni, sizeof(*data));
for (uint64_t i = 0; i < ni; ++i) {
for (uint64_t j = 0; j < nj; ++j) {
data[i][j] = rand() / (double)RAND_MAX;
}
}
// test performance
double* dt = calloc(iter_max, sizeof(*dt));
double const sum0 = sum_column(ni, nj, data);
for (uint64_t iter = 0; iter < iter_max; ++iter) {
clock_t const t_start = clock();
double const sum = sum_column(ni, nj, data);
clock_t const t_stop = clock();
assert(sum == sum0);
dt[iter] = (t_stop - t_start) / (double)CLOCKS_PER_SEC;
}
// sort dt
qsort(dt, iter_max, sizeof(*dt), compare);
// compute mean dt
double dt_mean = 0.0;
for (uint64_t iter = 0; iter < iter_max; ++iter) {
dt_mean += dt[iter];
}
dt_mean /= iter_max;
// print results
printf("%2lu %.8e %.8e %.8e %.8e\n", nj, dt[iter_max / 2], dt_mean, dt[0],
dt[iter_max - 1]);
// free memory
free(data);
}
然而，结果与我预期的不太一样：
据我了解，当 CPU 从 data 加载一个值时，它还会将 data 的以下一些值放入缓存中。确切的数字取决于缓存行大小（在我的机器上是 64 字节）。这可以解释，为什么随着 nj 的增长，解决方案的时间首先线性增加并在某个值处趋于平稳。如果 nj == 1，一次加载会将接下来的 7 个值放入缓存中，因此我们只需要每第 8 个值从 RAM 加载一次。如果 nj == 2，遵循相同的逻辑，我们需要每 4 个值访问一次 RAM。在一定大小之后，我们将不得不为每个值访问 RAM，这应该会导致性能趋于平稳。我的猜测是，为什么图表的线性部分比 4 更远是因为实际上这里有多个级别的缓存在工作，并且值在这些缓存中结束的方式比我在这里解释的要复杂一些。
我无法解释的是为什么这些性能峰值出现在 16 的倍数处。
稍微思考一下这个问题后，我决定检查 nj 的较高值是否也会出现这种情况：
事实上，确实如此。而且，还有更多：为什么性能在 ~250 之后再次提升？
有人可以向我解释一下，或者给我一些适当的参考，为什么会有这些峰值以及为什么性能会随着 nj 的更高值而提高。
如果您想自己尝试代码，为了方便起见，我还会附上我的绘图脚本：
import numpy as np
import matplotlib.pyplot as plt
data = np.genfromtxt("out.csv")
data[:,1:] /= data[0,1]
dy = np.diff(data[:,2]) / np.diff(data[:,0])
for i in range(len(dy) - 1):
if dy[i] - dy[i + 1] > (dy.max() - dy.min()) / 2:
plt.axvline(data[i + 1,0], color='gray', linestyle='--')
plt.text(data[i + 1,0], 1.5 * data[0,3], f"{int(data[i + 1,0])}",
rotation=0, ha="center", va="center",
bbox=dict(boxstyle="round", ec='gray', fc='w'))
plt.fill_between(data[:,0], data[:,3], data[:,4], color='gray')
plt.plot(data[:,0], data[:,1], label="median")
plt.plot(data[:,0], data[:,2], label="mean")
plt.legend(loc="upper left")
plt.xlabel("nj")
plt.ylabel("dt / dt$_0$")
plt.savefig("out.pdf")
这些图显示了几种复杂 low-level 影响的组合（主要是 缓存垃圾处理 和 预取 问题）。我假设目标平台是具有 64 字节高速缓存行的主流现代处理器（通常是 x86 处理器）。
我可以在我的 i5-9600KF 处理器上重现该问题。这是结果图：
首先，当nj较小时，获取地址之间的差距（即步幅）较小，缓存行的使用效率相对较高。例如，当nj = 1时，访问是连续的。在这种情况下，处理器可以有效地预取 DRAM 中的高速缓存行，从而隐藏其高延迟。还有一个很好的 空间缓存位置 因为许多连续的项目共享相同的缓存行。当nj=2时，只使用缓存行的一半值。这意味着对于相同数量的操作，请求的缓存行数量是原来的两倍。话虽这么说，由于添加两个 floating-point 数字 导致 compute-bound[=121 的相对 高延迟，时间并没有增加很多=] 代码。您可以 展开循环 4 次并使用 4 个不同的总和变量，以便（主流的现代）处理器可以并行添加多个值。请注意，大多数处理器还可以在每个周期从缓存中加载多个值。当 nj = 4 每 2 个周期请求一个新的缓存行（因为 double 占用 8 个字节）。结果，内存吞吐量会变得如此之大，以至于计算量变成 memory-bound。人们可能期望 nj >= 8 的时间稳定，因为请求的缓存行的数量应该相同，但实际上处理器 预取多个连续的缓存行 所以不要支付DRAM 延迟的开销在这种情况下是巨大的。预取缓存行的数量通常在 2 到 4 之间（据我所知，当步幅大于 512 时，英特尔处理器会禁用这种预取策略，因此当 nj >= 64 时）。这解释了为什么当 [=21 时时间急剧增加=] 并且它们在 32 <= nj <= 256 时变得相对稳定，但峰值除外。
当 nj 是 16 的倍数时出现的常规峰值是由于称为 缓存抖动 的复杂缓存效应造成的。现代缓存 N-way associative，N 通常在 4 到 16 之间。例如，这里是我的 i5-9600KF 处理器的统计数据：
Cache 0: L1 data cache, line size 64, 8-ways, 64 sets, size 32k
Cache 1: L1 instruction cache, line size 64, 8-ways, 64 sets, size 32k
Cache 2: L2 unified cache, line size 64, 4-ways, 1024 sets, size 256k
Cache 3: L3 unified cache, line size 64, 12-ways, 12288 sets, size 9216k
这意味着如果 (A1 % 32768) / 64 == (A2 % 32768) / 64，从具有各自地址 A1 和 A2 的 DRAM 中获取的两个值可能会导致我的 L1 缓存发生冲突。在这种情况下，处理器需要从一组 N=8 缓存行中选择要 替换 的缓存行。有很多cache replacement policy and none is perfect. Thus, some useful cache line are sometime evicted too early resulting in additional cache misses required later. In pathological cases, many DRAM locations can compete for the same cache lines resulting in excessive cache misses. More information about this can be found also in this post.
关于nj步幅，一级缓存中可以有效使用的缓存行数是有限的。例如，如果所有获取的值都具有相同的地址模缓存大小，那么实际上只有 N 个缓存行（对于我的处理器是 8 个）可以用来存储所有值。可用的缓存行较少是一个大问题，因为 预取器需要在缓存 中有相当大的 space 以便存储以后需要的许多缓存行。 并发取数越小，内存吞吐量越低。这在这里尤其如此，因为从 DRAM 中获取 1 个缓存行的延迟大约是几十纳秒（例如 ~70 ns），而其带宽大约是几十 GiB/s（例如 ~40 GiB/s): 应该同时获取数十个缓存行（例如~40），以隐藏延迟并使 DRAM 饱和。
这里是模拟我的一级缓存实际可以使用的缓存行数关于nj的值：
nj #cache-lines
1 512
2 512
3 512
4 512
5 512
6 512
7 512
8 512
9 512
10 512
11 512
12 512
13 512
14 512
15 512
16 256 <----
17 512
18 512
19 512
20 512
21 512
22 512
23 512
24 512
25 512
26 512
27 512
28 512
29 512
30 512
31 512
32 128 <----
33 512
34 512
35 512
36 512
37 512
38 512
39 512
40 512
41 512
42 512
43 512
44 512
45 512
46 512
47 512
48 256 <----
49 512
50 512
51 512
52 512
53 512
54 512
55 512
56 512
57 512
58 512
59 512
60 512
61 512
62 512
63 512
64 64 <----
==============
80 256
96 128
112 256
128 32
144 256
160 128
176 256
192 64
208 256
224 128
240 256
256 16
384 32
512 8
1024 4
我们可以看到，当 nj 是 16 的倍数时，可用缓存行的数量较少。在这种情况下，prefetecher 会将数据预加载到缓存行中，这些缓存行可能会被后续提取的 (同时进行）。在代码中执行的加载指令 在可用缓存行数较少时更有可能导致缓存未命中 。当发生缓存未命中时，需要再次从 L2 甚至 L3 中获取值，从而导致执行速度变慢。请注意，L2 缓存也受到相同的影响，尽管它由于更大而不太明显。 现代 x86 处理器的 L3 缓存利用散列来更好地分布事物以减少固定步幅的冲突（至少在英特尔处理器上，当然在 AMD 上也是如此，尽管据我所知这是 not documented).
这是我机器上某些峰值的时间：
32 4.63600000e-03 4.62298020e-03 4.06400000e-03 4.97300000e-03
48 4.95800000e-03 4.96994059e-03 4.60400000e-03 5.59800000e-03
64 5.01600000e-03 5.00479208e-03 4.26900000e-03 5.33100000e-03
96 4.99300000e-03 5.02284158e-03 4.94700000e-03 5.29700000e-03
128 5.23300000e-03 5.26405941e-03 4.93200000e-03 5.85100000e-03
192 4.76900000e-03 4.78833663e-03 4.60100000e-03 5.01600000e-03
256 5.78500000e-03 5.81666337e-03 5.77600000e-03 6.35300000e-03
384 5.25900000e-03 5.32504950e-03 5.22800000e-03 6.75800000e-03
512 5.02700000e-03 5.05165347e-03 5.02100000e-03 5.34400000e-03
1024 5.29200000e-03 5.33059406e-03 5.28700000e-03 5.65700000e-03
正如预期的那样，在可用缓存行数少得多的情况下，实践中的时间总体上更大。然而，当 nj >= 512 时，结果令人惊讶，因为它们比其他方法快得多。这是可用缓存行数等于的情况结合律的方式数 (N)。我的猜测是，这是因为英特尔处理器肯定会检测到这种病态情况并优化预取以减少缓存未命中的次数（使用 line-fill 缓冲区绕过 L1 缓存 - 见下文）。
最后，对于较大的 nj 步幅，更大的 nj 应该会导致更高的开销，这主要是由于 translation lookaside buffer (TLB)：有更多的页面地址需要用更大的nj 并且 TLB 条目的数量是有限的。事实上，这就是我在我的机器上观察到的情况：与您的目标平台不同，计时往往会以非常稳定的方式缓慢增加。
我还不能真正解释这种非常奇怪的行为。 以下是一些大胆的猜测：
- OS 当
nj很大时，OS 可能倾向于使用更多大页面（以减少 TLB 的开销），因为分配了更宽的块。这可能会导致预取器的并发性更高，因为 AFAIK 它不能跨页 界限。您可以尝试检查已分配（透明）huge-pages 的数量（通过查看AnonHugePagesin/proc/meminfoin Linux）或在这种情况下强制使用它们（使用显式memmap)，或者可能通过禁用它们。我的系统似乎独立于nj值使用 2 MiB 透明 huge-pages。 - 如果目标架构是 NUMA 架构（例如，新的 AMD 处理器或具有多个处理器的服务器有自己的内存），那么 OS 可以分配物理存储在另一个 NUMA 节点上的页面，因为有less space 在当前 NUMA 节点上可用。由于更大的吞吐量（尽管延迟更高），这可能会导致更高的性能。您可以在 Linux 上使用
numactl控制此策略，以便强制进行本地分配。
有关此主题的更多信息，请阅读精彩文档 What Every Programmer Should Know About Memory. Moreover, a very good post about how x86 cache works in practice is available
去除峰
要消除 x86 处理器上缓存垃圾造成的峰值，您可以使用 non-temporal 软件预取指令，这样缓存行就可以在 non-temporal 缓存结构并放入靠近处理器的位置，该位置不应导致 L1 中的缓存垃圾（如果可能）。这种缓存结构通常是 Intel 处理器上的 line-fill buffers (LFB) 和 AMD Zen 处理器上的（等效）未命中地址缓冲区 (MAB)。有关 non-temporal 指令和 LFB 的更多信息，请阅读 nj 较小时加快代码速度：
double sum_column(uint64_t ni, uint64_t nj, double* const data)
{
double sum0 = 0.0;
double sum1 = 0.0;
double sum2 = 0.0;
double sum3 = 0.0;
if(nj % 16 == 0)
{
// Cache-bypassing prefetch to avoid cache trashing
const size_t distance = 12;
for (uint64_t i = 0; i < ni; ++i) {
_mm_prefetch(&data[(i+distance)*nj+0], _MM_HINT_NTA);
sum0 += data[i*nj+0];
}
}
else
{
// Unrolling is much better for small strides
for (uint64_t i = 0; i < ni; i+=4) {
sum0 += data[(i+0)*nj+0];
sum1 += data[(i+1)*nj+0];
sum2 += data[(i+2)*nj+0];
sum3 += data[(i+3)*nj+0];
}
}
return sum0 + sum1 + sum2 + sum3;
}
修改后的代码结果如下：
我们可以看到峰值不再出现在时序中。我们还可以看到，由于 dt0 小了大约 4 倍（由于循环展开），这些值要大得多。
请注意，在实践中（至少在 Intel 处理器上），使用此方法无法避免 L2 缓存中的缓存垃圾。这意味着效果仍然存在，在我的机器上 nj 跨度是 512 (4 KiB) 的倍数（实际上比以前慢了，尤其是 nj >= 2048 时）。在 x86 处理器上 (nj%512) == 0 && nj >= 512 时停止预取可能是个好主意。影响 AFAIK，没有办法解决这个问题。也就是说，对 very-large 数据结构执行如此大的跨步访问是一个非常糟糕的主意。
请注意，应谨慎选择 distance，因为提前预取可能会导致缓存行在实际使用之前被逐出（因此需要再次获取它们），而延迟预取则用处不大。我认为使用接近 LFB/MAB 中条目数的值是个好主意（例如 Skylake/KabyLake/CannonLake 上的 12，Zen-2 上的 22）。