为什么现代编译器不能优化循环中的行主顺序访问？

Question

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

#define N 30000

int a[N][N] = { 0 };

int main() {
  srand(time(NULL));

  int sum = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      a[i][j] = rand() % 99;
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      sum += a[i][j];
    }
  }
}

在我的系统上，行-主顺序访问平均花费8.42s(n=5试用），而列-主顺序访问在我的系统上花费30.12s(n=5试用），这是相当重要的。

从表面上看，这应该是一件非常简单的事情来优化。

为什么现代编译器不优化这些场景？

Answer 1

大多数循环不是由简单的和语句组成，而是有副作用和循环迭代之间的依赖关系。

不是循环中的所有操作都是交换的，所以优化器必须真正理解循环中发生的所有操作，以确保它不会改变其含义，包括调用的任何系统API的内容、动态加载库中的代码等。

现在这只是一个猜测，但我希望有人尝试过，意识到优化没有足够的关于正在运行的代码的信息来触发大多数次，然后关注并行执行优化，这可能是大多数代码库中更大的优化机会。