从寄存器移动到频繁访问的变量时性能出乎意料地缓慢

Question

我正在使用以下示例了解缓存的工作原理：

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

typedef uint32_t data_t;
const int U = 10000000;   // size of the array. 10 million vals ~= 40MB
const int N = 100000000;  // number of searches to perform

int main() {
  data_t* data = (data_t*) malloc(U * sizeof(data_t));
  if (data == NULL) {
    free(data);
    printf("Error: not enough memory\n");
    exit(-1);
  }

  // fill up the array with sequential (sorted) values.
  int i;
  for (i = 0; i < U; i++) {
    data[i] = i;
  }

  printf("Allocated array of size %d\n", U);
  printf("Summing %d random values...\n", N);

  data_t val = 0;
  data_t seed = 42;
  for (i = 0; i < N; i++) {
    int l = rand_r(&seed) % U;
    val = (val + data[l]);
  }

  free(data);
  printf("Done. Value = %d\n", val);
  return 0;
}

慢速随机访问循环的相关注释，使用perf record ./sum，然后perf report找到，是

  0.05 │       mov    -0x18(%rbp),%eax                                                                 ▒
  0.07 │       mov    -0x10(%rbp),%rcx                                                                 ▒
       │       movslq -0x20(%rbp),%rdx                                                                 ▒
  0.03 │       add    (%rcx,%rdx,4),%eax                                                               ▒
 95.39 │       mov    %eax,-0x18(%rbp)                                                                 ▒
  1.34 │       mov    -0x14(%rbp),%eax                                                                 ▒
       │       add    $0x1,%eax                                                                        ◆
       │       mov    %eax,-0x14(%rbp)

此时，

-0x18

保持

val

，

-0x10

保持

data

，

-0x14

保持

i

，

-0x20

保持

l

。左列的数字显示该指令所花费的时间百分比。我预计该行

add (%rcx, %rdx, 4), %eax

会占用最多时间，因为它必须对

data[l]

执行随机访问负载（这只是

(%rcx, %rdx, 4)

）。这应该只在大约 16k/U = 0.16% 的时间出现在 L1 缓存中，因为我的 L1 缓存大小为 64k 字节或 16k 整数。所以这个操作应该很慢。相反，显然很慢的操作只是从寄存器

%eax

移动到

val

，该寄存器经常使用，因此肯定在缓存中。谁能解释一下这是怎么回事吗？

Answer 1

硬件性能计数器通常“归咎于”等待缓慢结果的指令（

store

），而不是缓慢生成结果的指令。（微融合到加载+中的内存源

add

添加微操作）。

和/或无论数据依赖性如何，它们都会在缓存未命中加载后归咎于下一条指令。这称为“打滑”或“歪斜”。例如，请参阅 https://easyperf.net/blog/2018/08/29/Understanding-performance-events-skid 和 https://www.brendangregg.com/perf.html

我对造成这种影响的假设是，我认为 Intel CPU 在引发中断时等待 ROB 中最旧的指令退出，也许是为了避免在高中断情况下使主线程挨饿。对于最终导致无序执行停止的缓存未命中加载，它将是 ROB 中最旧的，在加载数据到达之前无法退出（因为 x86 的强有序内存模型不会让加载在此之前退出） ，即使它们被认为是无故障的，与 ARM 不同）。因此，当“cycles”事件的计数器下降到零并触发样本时，缓存未命中加载就会退出，程序顺序中的下一条指令将受到该样本的“指责”。

对于旨在附加到特定指令的事件（例如

mem_load_retired.l3_miss

），打滑会带来更大的问题，但英特尔 PEBS 避免了这种情况。在上一段中，我讨论的是“周期”事件，该事件在停滞时每个周期都会滴答作响，但您可能会在

mem_load_retired.l3_miss

中得到相同的结果，直到从 L3 切片中听到反馈后才能检测到该事件。

在不停止的代码中，一组指令中在同一周期内全部退出的第一条或第二条指令可能会受到指责。 CPU 必须从管道中正在运行的所有指令中选择一条指令来负责。无论是在何处引发中断（非 PEBS），还是哪个指令地址进入 PEBS 缓冲区。

---

另请参阅不一致的“perf annotate”内存加载/存储时间报告，这是一个不太简单/明显的情况，但归咎于等待缓慢结果的指令是其中的关键部分。

Answer 2

这就是我认为正在发生的事情......

首先要注意的是，

int l = rand_r(&seed) % U;

线是不变的。也就是说，它总是被计算为相同的东西。因此，编译器已将该值缓存在

%rcx

或

%rdx

中。

考虑到这一点，让我们看看这些行......

  0.03 │       add    (%rcx,%rdx,4),%eax                                                               
 95.39 │       mov    %eax,-0x18(%rbp)

第一个将

data[l]

和

val

加在一起，将结果存储在

%eax

中。由于

data[l]

永远不会改变，因此它将始终从同一内存位置加载值。该值可能会被硬件缓存。第二个是将总和写入堆栈上的局部变量：

val

。

将值写入堆栈需要花费大量时间。这里使用的缓存类型可以是直写式的，因此每次该值发生变化时都会更新后备内存。

每次迭代都需要更新

val

吗？不。但这样做并没有错。