让我们考虑一个矩阵
std::vector<std::vector<int>> matrix;
每行长度相同，我将每个std :: vector<int>称为一列。
为什么用外循环迭代外部维度比用内循环更快？
第一个程序：首先迭代列
int sum = 0;
for (int col = 0 ; col < matrix.size() ; col++)
{
for (int row = 0 ; row < matrix[0].size() ; row++)
{
sum += matrix[col][row];
}
}
第二个程序：先迭代行
int sum = 0;
for (int row = 0 ; row < matrix[0].size() ; row++) // Assuming there is at least one element in matrix
{
for (int col = 0 ; col < matrix.size() ; col++)
{
sum += matrix[col][row];
}
}
以下是我的猜测：
跳转内存
我有一种模糊的直觉，认为在内存中跳转需要比读取连续的内存更多的时间，但我认为RAM的内存访问时间是恒定的。此外，DRAM中没有移动部件，我不明白如果两个int是连续的，为什么会更快地读取它们？
总线宽度
一个int占用2个字节（尽管根据数据模型可能会有所变化）。在一台具有8字节宽总线的机器上，我可以想象，如果int在内存中是连续的，那么每个时钟周期最终可能会将4个int（根据数据模型）发送到处理器，而如果它们不是连续的，则每个时钟周期只能发送一个int。
如果是这样的话，那么如果矩阵包含长度为8字节的long long int，则我们将不再看到两个程序之间的任何区别（我还没有测试过）。
缓存
我不确定为什么，但我感觉缓存可能是第二个程序速度较慢的原因。缓存的效果可能与我上面提到的总线大小参数有关。可能只有在DRAM中连续的内存才能加载到缓存中，但我不知道为什么会这样。