数组迭代中的CPU空间缓存局部性

Question

我对L1缓存的理解是内存提取加载了缓存行.假设高速缓存行大小为64个字节,如果我在地址访问存储器p,它将从加载整个块p到p + 64到缓存中.因此,最好从左到右(而不是从右到左)迭代一个数组,以最大化缓存局部性.

但是,我编写了一个示例C代码,它分配了一个包含1亿个字符的数组,将随机值写入其中并对其求和(下面复制以供参考).一个版本的代码从左到右,另一个从右到左.当我对它进行基准测试时,我得到了非常类似的结果(其中"时钟周期"是根据测量的clock.代码是在没有优化的情况下编译的.

所以我的问题是:现代处理器做的不仅仅是"缓存读取+ 64字节"吗？他们是向前和向后缓存吗？编译器可以"告诉"处理器代码向后迭代吗？

作为参考,我正在Mac OS X 10.13.3使用gcc-7 (Homebrew GCC 7.2.0_1) 7.2.0具有64字节缓存行的x86-64 Intel处理器.

Benchmakrs:

$ ./a.out
Backward Iterating...took 150101 clock cycles

$ ./a.out
Forward Iterating...took 146545 clock cycles

我希望前向迭代速度大约快64倍,因为每64个元素应该是缓存命中,而对于反向迭代,每个元素应该是缓存未命中.

所以,我打电话给cachegrind.两者的缓存命中率几乎相同:

# Left to right iteration
==21773==
==21773== I   refs:      4,006,996,067
==21773== I1  misses:            5,183
==21773== LLi misses:            3,019
==21773== I1  miss rate:          0.00%
==21773== LLi miss rate:          0.00%
==21773==
==21773== D   refs:      1,802,393,260  (1,401,627,925 rd   + 400,765,335 wr)
==21773== D1  misses:        3,153,101  (    1,588,104 rd   +   1,564,997 wr)
==21773== LLd misses:        3,004,885  (    1,440,660 rd   +   1,564,225 wr)
==21773== D1  miss rate:           0.2% (          0.1%     +         0.4%  )
==21773== LLd miss rate:           0.2% (          0.1%     +         0.4%  )
==21773==
==21773== LL refs:           3,158,284  (    1,593,287 rd   +   1,564,997 wr)
==21773== LL misses:         3,007,904  (    1,443,679 rd   +   1,564,225 wr)
==21773== LL miss rate:            0.1% (          0.0%     +         0.4%  )

# Right to left iteration
==21931==
==21931== I   refs:      4,006,996,453
==21931== I1  misses:            5,198
==21931== LLi misses:            3,045
==21931== I1  miss rate:          0.00%
==21931== LLi miss rate:          0.00%
==21931==
==21931== D   refs:      1,802,393,428  (1,401,628,038 rd   + 400,765,390 wr)
==21931== D1  misses:        3,153,113  (    1,588,079 rd   +   1,565,034 wr)
==21931== LLd misses:        3,135,505  (    1,571,219 rd   +   1,564,286 wr)
==21931== D1  miss rate:           0.2% (          0.1%     +         0.4%  )
==21931== LLd miss rate:           0.2% (          0.1%     +         0.4%  )
==21931==
==21931== LL refs:           3,158,311  (    1,593,277 rd   +   1,565,034 wr)
==21931== LL misses:         3,138,550  (    1,574,264 rd   +   1,564,286 wr)
==21931== LL miss rate:            0.1% (          0.0%     +         0.4%  )

码:

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

#define BUF_SIZE 100000000

int main() {
  srand(time(NULL));
  uint8_t *buf1 = (uint8_t *)malloc(BUF_SIZE);
  // Fill the buf with random data
  for (size_t i = 0; i < BUF_SIZE; ++i) {
    buf1[i] = rand();
  }

#ifdef BACKWARDS
  printf("Backward Iterating...");
#else
  printf("Forward Iterating...");
#endif

  uint64_t sum = 0;
  clock_t start = clock();
#ifdef BACKWARDS
  for (size_t i = BUF_SIZE - 1; i != ~0; --i) {
#else
  for (size_t i = 0; i < BUF_SIZE; ++i) {
#endif
    sum += buf1[i];
  }
  clock_t end = clock();
  printf("took %lu clock cycles\n", end - start);
  printf("sum: %llu\n", sum);
  free(buf1);
}

Answer 1

要扩展上一个答案:

加载一个完整的缓存行粒度意味着前进或后退并不重要,一旦你击中该行的一侧就可以得到所有这些.这当然只适用于可缓存的加载和memtypes(+仍然在缓冲区中时可能会遇到的流情况).

然而,这不是完整的故事.现代CPU采用非常善于处理空间局部性的硬件预取程序 - 这些将通过在您正在进行的同一方向上预取额外的高速缓存行来增加粒度.退出预取程序取决于您使用的确切体系结构,但常见的体系结构包括下一行,相邻行(+/- 1行),下一行流或基于IP的步幅.更多信息在这里.

这些预取器应该是对称的,但我们不确定(确切的细节没有公开),它们可能有不同的方向或不同方向的阈值.

另一点是cachegrind只是一个缓存模拟,它不包括预取等效果,甚至不建模准确的缓存(大小应该没问题,但是替换策略和其他微架构细节不能保证是相同的),所以你不会看到完整的效果.使用perf计数器查看实际的HW行为可能更好.