为什么第二个程序执行得更差，即使它应该有相当少的缓存未命中？

Question

考虑以下程序：

#include <stdio.h>
#include <stdlib.h>

typedef unsigned long long u64;

int program_1(u64* a, u64* b)
{
  const u64 lim = 50l * 1000l * 1000l;
  // Reads arrays
  u64 sum = 0;
  for (u64 i = 0; i < lim * 100; ++i) {
    sum += a[i % lim];
    sum += b[i % lim];
  }

  printf("%llu\n", sum);
  return 0;
}


int program_2(u64* a, u64* b)
{
  const u64 lim = 50l * 1000l * 1000l;
  // Reads arrays
  u64 sum = 0;
  for (u64 i = 0; i < lim * 100; ++i) {
    sum += a[i % lim];
  }
  for (u64 i = 0; i < lim * 100; ++i) {
    sum += b[i % lim];
  }

  printf("%llu\n", sum);
  return 0;
}

这两个程序是相同的：它们用 1 填充一个数组，然后读取每个元素 100 次，添加到一个计数器中。唯一的区别是第一个融合加法器循环，而第二个执行两个单独的传递。鉴于 M1 有 64KB 的 L1 数据缓存，我的理解是会发生以下情况：

节目 1

sum += a[0] // CACHE MISS. Load a[0..8192] on L1.
sum += b[0] // CACHE MISS. Load b[0..8192] on L1.
sum += a[1] // CACHE MISS. Load a[0..8192] on L1.
sum += b[1] // CACHE MISS. Load b[0..8192] on L1.
sum += a[2] // CACHE MISS. Load a[0..8192] on L1.
sum += b[2] // CACHE MISS. Load b[0..8192] on L1.
(...)

计划 2

sum += a[0] // CACHE MISS. Load a[0..8192] on L1.
sum += a[1] // CACHE HIT!
sum += a[2] // CACHE HIT!
sum += a[3] // CACHE HIT!
sum += a[4] // CACHE HIT!
...
sum += a[8192] // CACHE MISS. Load a[8192..16384] on L1.
sum += a[8193] // CACHE HIT!
sum += a[8194] // CACHE HIT!
sum += a[8195] // CACHE HIT!
sum += a[8196] // CACHE HIT!
...
...
sum += b[0] // CACHE MISS. Load b[0..8192] on L1.
sum += b[1] // CACHE HIT!
sum += b[2] // CACHE HIT!
sum += b[3] // CACHE HIT!
sum += b[4] // CACHE HIT!
...

这会让我相信第一个程序比较慢，因为每次读取都是缓存未命中，而第二个主要是缓存命中。但是，结果有所不同。运行在 Macbook Pro M1 上，clang -O2，第一个程序需要 2.8 秒才能完成，而第二个程序大约需要 3.8 秒。

我对 L1 缓存工作原理的心智模型有什么问题？

Answer 1

我预计：

a) 当 CPU 正在等待将 sum += a[i % lim]; 的数据提取到 L1 时，它可以请求将 sum += b[i % lim]; 的数据提取到 L1。本质上;程序 1 并行等待 2 次缓存未命中，而程序 2 一次等待 1 次缓存未命中，速度可能会慢两倍。

b) 循环开销（for (u64 i = 0; i < lim * 100; ++i) {中的所有工作）和索引（计算i%lim）在程序2中重复；导致程序 2 执行几乎两倍的额外工作（这与缓存未命中无关）。

c) 编译器不善于优化。我很惊讶没有为两个版本生成相同的代码。我很震惊 CLANG 和 GCC 都无法自动矢量化（使用 SIMD）。一个非常假设的理想化完美编译器应该能够将两个版本一直优化到 write(STDOUT_FILENO, "10000000000\n", 12); return 0.

What is wrong about my mental model of how the L1 cache works?

您似乎认为缓存一次只能缓存一件事。对于计划 1，它更像是：

sum += a[0] // CACHE MISS
sum += b[0] // CACHE MISS
sum += a[1] // CACHE HIT (data still in cache)
sum += b[1] // CACHE HIT (data still in cache)
sum += a[2] // CACHE HIT (data still in cache)
sum += b[2] // CACHE HIT (data still in cache)
sum += a[3] // CACHE HIT (data still in cache)
sum += b[3] // CACHE HIT (data still in cache)
sum += a[4] // CACHE HIT (data still in cache)
sum += b[4] // CACHE HIT (data still in cache)
sum += a[5] // CACHE HIT (data still in cache)
sum += b[5] // CACHE HIT (data still in cache)
sum += a[6] // CACHE HIT (data still in cache)
sum += b[6] // CACHE HIT (data still in cache)
sum += a[7] // CACHE HIT (data still in cache)
sum += b[7] // CACHE HIT (data still in cache)

sum += a[8] // CACHE MISS
sum += b[8] // CACHE MISS

对于程序 2，它可能（见注释）以不同的顺序出现相同数量的缓存未命中：

sum += a[0] // CACHE MISS
sum += a[1] // CACHE HIT (data still in cache)
sum += a[2] // CACHE HIT (data still in cache)
sum += a[3] // CACHE HIT (data still in cache)
sum += a[4] // CACHE HIT (data still in cache)
sum += a[5] // CACHE HIT (data still in cache)
sum += a[6] // CACHE HIT (data still in cache)
sum += a[7] // CACHE HIT (data still in cache)

sum += a[8] // CACHE MISS

..然后：

sum += b[0] // CACHE MISS
sum += b[1] // CACHE HIT (data still in cache)
sum += b[2] // CACHE HIT (data still in cache)
sum += b[3] // CACHE HIT (data still in cache)
sum += b[4] // CACHE HIT (data still in cache)
sum += b[5] // CACHE HIT (data still in cache)
sum += b[6] // CACHE HIT (data still in cache)
sum += b[7] // CACHE HIT (data still in cache)

sum += b[8] // CACHE MISS

注意：我假设任何数组都大于缓存。如果缓存足够大以容纳整个数组但又太小而无法容纳两个数组；那么程序 2 可能会比程序 1 快。这是程序 2 会更快的唯一情况。

为什么第二个程序执行得更差，即使它应该有相当少的缓存未命中？

Why the second program performs worse, even though it should have considerably less cache misses?

c

c++

performance

caching

节目 1

计划 2