c - 为什么在跨步预取时循环顺序很重要？

Question

在 C 中，您被告知以行优先顺序遍历矩阵，因为这就是数组在引擎盖下的存储方式，行优先迭代利用整个缓存行，从而减少缓存未命中。事实上，我确实在我的机器上看到了行优先和列优先迭代之间的巨大性能差异。测试代码:

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

#include <time.h>
#include <sys/resource.h>

int getTime()
{
  struct timespec tsi;

  clock_gettime(CLOCK_MONOTONIC, &tsi);
  double elaps_s = tsi.tv_sec;
  long elaps_ns = tsi.tv_nsec;
  return (int) ((elaps_s + ((double)elaps_ns) / 1.0e9) * 1.0e3);
}

#define N 1000000
#define M 100

void main()
{
  int *src = malloc(sizeof(int) * N * M);
  int **arr = malloc(sizeof(int*) * N);
  for(int i = 0; i < N; ++i)
    arr[i] = &src[i * M];

  for(int i = 0; i < N; ++i)
    for(int j = 0; j < M; ++j)
      arr[i][j] = 1;

  int total = 0;

  int pre = getTime();


  for(int j = 0; j < M; ++j)
    for(int i = 0; i < N; ++i)
      total += arr[i][j];

  /*
  for(int i = 0; i < N; ++i)
    for(int j = 0; j < M; ++j)
      total += arr[i][j];
  */

  int post = getTime();

  printf("Result: %d, took: %d ms\n", total, post - pre);
}

但是，现代内存系统具有预取器，可以预测跨步访问，并且当您遍历列时，您将遵循非常规则的模式。这难道不应该让列优先迭代的执行类似于行优先迭代吗？

Answer 1

缓存行具有一定的大小(例如 64 字节)，处理器读取和写入完整的缓存行。比较处理的字节数和读取和写入的字节数。