为什么这个C ++ for循环的执行时间有显着的不同？
我正在经历循环，并发现访问循环的重大差异。 我无法理解在这两种情况下造成这种差异的原因是什么？
第一个例子：
执行时间处理时间; 8秒
for (int kk = 0; kk < 1000; kk++) { sum = 0; for (int i = 0; i < 1024; i++) for (int j = 0; j < 1024; j++) { sum += matrix[i][j]; } } 第二个例子：
执行时间：23秒
for (int kk = 0; kk < 1000; kk++) { sum = 0; for (int i = 0; i < 1024; i++) for (int j = 0; j < 1024; j++) { sum += matrix[j][i]; } }
什么原因造成如此之多的执行时差才换来
matrix[i][j]
至
matrix[j][i]
？
这是一个内存caching的问题。
matrix[i][j]比matrix[j][i] matrix[i][j]具有更好的caching命中，因为matrix[i][j]具有更多连续的存储器访问机会。
例如，当我们访问matrix[i][0] ，caching可以加载包含matrix[i][0]的连续存储段，从而访问matrix[i][1] ， matrix[i][2] ，…将受益于caching速度，因为matrix[i][1] ， matrix[i][2] ，…接近于matrix[i][0] 。
然而，当我们访问matrix[j][0] ，它离matrix[j - 1][0]很远，可能没有被caching，也不能从caching速度中受益。 特别是，matrix通常作为一个连续的大段内存来存储，而Cacher可能会预测内存访问的行为，并总是caching内存。
这就是为什么matrix[i][j]更快。 这在基于CPU高速caching的性能优化中是典型的。
性能的差异是由计算机的caching策略造成的。
二维数组matrix[i][j]被表示为存储器中的一长串值。
例如数组A[3][4]看起来像：
1 1 1 1 2 2 2 2 3 3 3 3
在这个例子中，A [0] [x]的每个条目设置为1，A [1] [x]的每个条目设置为2，…
如果你的第一个循环被应用到这个matrix，访问顺序是这样的：
1 2 3 4 5 6 7 8 9 10 11 12
而第二个循环访问顺序如下所示：
1 4 7 10 2 5 8 11 3 6 9 12
当程序访问数组的一个元素时，它也会加载后续的元素。
例如，如果您访问A[0][1] ，则加载A[0][2]和A[0][3] 。
因此，第一个循环必须执行较less的加载操作，因为有些元素在需要时已经在caching中。 第二个循环将当前不需要的条目加载到caching中，从而导致更多的加载操作。
其他人已经做了很好的解释，为什么一种forms的代码比另一种forms更有效地使用内存caching。 我想添加一些你可能不知道的背景信息：你可能没有意识到现在主存访问是多么昂贵 。
在这个问题上张贴的数字看起来对我来说是正确的，我要在这里重现它们，因为它们非常重要：
Core i7 Xeon 5500 Series Data Source Latency (approximate) L1 CACHE hit, ~4 cycles L2 CACHE hit, ~10 cycles L3 CACHE hit, line unshared ~40 cycles L3 CACHE hit, shared line in another core ~65 cycles L3 CACHE hit, modified in another core ~75 cycles remote remote L3 CACHE ~100-300 cycles Local Dram ~60 ns Remote Dram ~100 ns
请注意最后两个条目的单位更改。 具体取决于您使用的是哪种型号，该处理器运行在2.9-3.2 GHz; 为了使math变得更简单，我们就把它叫做3GHz。 所以一个周期是0.33333纳秒。 所以DRAM访问也是100-300个周期。
重点在于CPU可以在从主存储器读取一条caching行的时间内执行数百条指令。 这就是所谓的记忆墙 。 因此，有效使用内存caching比现代CPU的整体性能中的其他因素更重要。
答案取决于如何定义matrix 。 在完全dynamic分配的数组中，您将拥有：
T **matrix; matrix = new T*[n]; for(i = 0; i < n; i++) { t[i] = new T[m]; }
所以，每个matrix[j]将需要一个新的内存查找指针。 如果在外部执行j循环，则内部循环可以在整个内部循环中重复使用matrix[j]的指针。
如果matrix是一个简单的二维数组：
T matrix[n][m];
那么matrix[j]将简单地乘以1024 * sizeof(T) – 这可以通过在优化的代码中添加1024 * sizeof(T)循环索引来实现，所以应该相对较快。
最重要的是，我们有caching局部性因素。 高速caching有“行”数据，每行通常为32到128字节。 所以，如果你的代码读取地址X ，caching将加载X值为32到128字节的值。 所以如果你需要的下一件事情是从当前位置只有sizeof(T) ，它很可能已经在caching中[现代处理器也检测到你正在循环读取每个内存位置，并预加载数据]。
在j内部循环的情况下，您正在读取每个循环的sizeof(T)*1024距离的新位置[或者如果dynamic分配，则可能会有更大的距离]。 这意味着被加载的数据在下一个循环中将不会有用，因为它不在下一个32到128个字节中。
最后，由于SSE指令或类似指令，第一个循环更加优化是完全可能的，这使得运算速度更快。 但是对于如此庞大的matrix来说，这可能是微不足道的，因为性能在这个尺寸下是高度受限的。
内存硬件没有经过优化来提供单独的地址，而是倾向于在称为高速caching行的大块连续内存上运行。 每当读取matrix的一个条目时，它所在的整个caching行也会随同它一起被加载到caching中。
更快的循环顺序设置为按顺序读取内存; 每次加载caching行时，都使用该caching行中的所有条目。 每一个通过外部循环，你只读一次matrix条目。
然而，较慢的循环sorting只能在每个caching行中使用单个条目，然后才能继续。 因此，每个高速caching行必须多次加载，每行一个matrix条目。 例如，如果double是8个字节并且高速caching行是64个字节长，那么每个通过外部循环的每个必须读取每个matrix条目8次，而不是一次。
所有这一切，如果你已经开始优化，你可能会看到没有什么区别：优化器理解这种现象，好的能够认识到，他们可以交换哪个循环是内部循环，哪个循环是这个特定的外部循环代码片段。
（同样，一个好的优化器只会在最外层的循环中执行一次，因为它认识到前999次与sum的最终值无关）
matrix作为一个向量存储在内存中。 以第一种方式访问存储器。 以第二种方式访问它需要跳过内存位置。 请参阅http://en.wikipedia.org/wiki/Row-major_order
如果访问j – i，j维将被caching，所以机器代码不必每次都改变它，第二维不会被caching，所以每次导致差异的时候都会删除caching。
基于引用的局部性的概念，一段代码很可能访问相邻的存储器位置。 所以更多的值被加载到caching中比要求。 这意味着更多的caching命中。 你的第一个例子是满足这个好，而你在第二个例子中的代码不是。
