为什么在 x86 上访问其他缓存行的速度较慢，与 Intel 记录的缓存行为不匹配？

Question

根据Intel的优化手册，L1数据缓存为32KiB，8路关联，64字节行。我写了以下微基准来测试内存读取性能。

我假设如果我们只访问可以放入 32 KiB 缓存的块，每次内存访问都会很快，但如果我们超过该缓存大小，访问会突然变慢。当 skip 为 1 时，基准测试按顺序访问每一行。

void benchmark(int bs, int nb, int trials, int skip)
{
  printf("block size: %d, blocks: %d, skip: %d, trials: %d\n", bs, nb, skip, trials);
  printf("total data size: %d\n", nb*bs*skip);
  printf("accessed data size: %d\n", nb*bs);
  uint8_t volatile data[nb*bs*skip];
  clock_t before = clock();
  for (int i = 0; i < trials; ++i) {
    for (int block = 0; block < nb; ++block) {
      data[block * bs * skip];
    }
  }
  clock_t after = clock() - before;
  double ns_per_access = (double)after/CLOCKS_PER_SEC/nb/trials * 1000000000;
  printf("%f ns per memory access\n", ns_per_access);
}

再次使用skip = 1，结果符合我的假设：

~ ❯❯❯ ./bm -s 64 -b 128 -t 10000000 -k 1
block size: 64, blocks: 128, skip: 1, trials: 10000000
total data size: 8192
accessed data size: 8192
0.269054 ns per memory access
~ ❯❯❯ ./bm -s 64 -b 256 -t 10000000 -k 1
block size: 64, blocks: 256, skip: 1, trials: 10000000
total data size: 16384
accessed data size: 16384
0.278184 ns per memory access
~ ❯❯❯ ./bm -s 64 -b 512 -t 10000000 -k 1
block size: 64, blocks: 512, skip: 1, trials: 10000000
total data size: 32768
accessed data size: 32768
0.245591 ns per memory access
~ ❯❯❯ ./bm -s 64 -b 1024 -t 10000000 -k 1
block size: 64, blocks: 1024, skip: 1, trials: 10000000
total data size: 65536
accessed data size: 65536
0.582870 ns per memory access

到目前为止，还不错：当一切都适合 L1 缓存时，内部循环大约每纳秒运行 4 次，或者每个时钟周期运行多于一次。当我们使数据太大时，需要更长的时间。这完全符合我对缓存应该如何工作的理解。

现在让我们通过让 skip 为 2.

来访问每个 other 块

~ ❯❯❯ ./bm -s 64 -b 512 -t 10000000 -k 2
block size: 64, blocks: 512, skip: 2, trials: 10000000
total data size: 65536
accessed data size: 32768
0.582181 ns per memory access

这违反了我的理解！这对于直接映射缓存是有意义的，但由于我们的缓存是关联的，我不明白为什么这些行应该相互冲突。为什么访问每隔一个块会变慢？

但如果我将 skip 设置为 3，事情又变快了。事实上，skip 的任何奇数都很快；任何偶数都很慢。例如：

~ ❯❯❯ ./bm -s 64 -b 512 -t 10000000 -k 7
block size: 64, blocks: 512, skip: 7, trials: 10000000
total data size: 229376
accessed data size: 32768
0.265338 ns per memory access
~ ❯❯❯ ./bm -s 64 -b 512 -t 10000000 -k 12
block size: 64, blocks: 512, skip: 12, trials: 10000000
total data size: 393216
accessed data size: 32768
0.616013 ns per memory access

为什么会这样？

为了完整性：我使用的是 2015 年中期的 MacBook Pro 运行 macOS 10.13.4。我的完整 CPU 品牌字符串是 Intel(R) Core(TM) i7-4980HQ CPU @ 2.80GHz。我正在编译 cc -O3 -o bm bm.c;编译器是 Xcode 9.4.1 附带的编译器。我省略了 main 函数；它所做的只是解析命令行选项并调用 benchmark.

Answer 1

缓存不是全关联的，它是set-associative，意思是每个地址映射到某个集合，关联性只在映射到相同的行之间起作用设置。

通过使步长等于 2，您可以将一半的集合排除在游戏之外，因此您有效访问 32K 并不重要 - 您只有 16k 可用（例如偶数集合），所以您仍然超出你的能力并开始颠簸（结束从下一级获取数据）。

步数为3时，问题解决了，绕一圈就可以使用所有set了。任何素数也是如此（这就是为什么它有时用于地址哈希）

为什么在 x86 上访问其他缓存行的速度较慢，与 Intel 记录的缓存行为不匹配？

Why is accessing every other cache line slower on x86, not matching Intel's documented cache behavior?

benchmarking

x86-64

cpu-cache