为什么糟糕的初始化这样的二维数组？ [英] Why is it worse to initialize a two dimensional array like this?

问题描述

for(int i = 0; i<100; i++)

    for(int j = 0; j<100; j++)

         array[j][i] = 0;
         // array[i][j] = 0;

我的教授说，这是更昂贵的第一种方式来初始化的二维阵列，而不是第二个。有人能解释这是怎么回事，这使得该情况下，引擎盖底下？或者说，初始化两种方法有相同的性能？

My professor said it was much more costly to initialize a two dimensional array in the first way as opposed to the second. Can someone explain what is going on underneath the hood which makes that the case? Or, do the two means of initialization have equal performance?

推荐答案

如前所述@dlev，这是由于的的引用的局部性 的，并与如何计算机工程物理硬件做的。

As @dlev mentioned, this is due to locality of reference and has to do with how the physical hardware in the computer works.

计算机内，也有许多不同类型的存储器。通常情况下，只有特定的存储单元（寄存器）可以对他们进行实际操作;的其余时间，如果你对数据进行操作，你必须从内存中加载到寄存器中，执行一些计算，然后将它写回。

Inside the computer, there are many different types of memory. Typically, only certain memory locations (registers) can have actual operations performed on them; the rest of the time, if you're performing operations on data, you have to load it from memory into a register, perform some computation, then write it back.

主存储器（RAM）是多少，比寄存器慢得多，通常由数百至数千的一个因素。因此，从存储器中读出应该避免，如果在所有可能的。为了解决这个问题，大多数计算机通常有记忆称为缓存的特殊地区。高速缓存的工作是认为最近已经从存储器存取的数据，使得如果该同一存储器区域被再次访问，该值可以从高速缓存（快）拉出，而不是从主存储器（缓动）。通常情况下，高速缓存被设计成，如果一个值被从内存中，该值，加上一大堆相邻值的读入，被拉入高速缓存中。这样一来，如果迭代数组，则读取第一个值之后，从阵列中的值的其余部分将被坐在缓存，并且可以更有效地进行访问。

Main memory (RAM) is much, much slower than registers, often by a factor of hundreds to thousands. Consequently, reading from memory should be avoided if at all possible. To address this, most computers typically have special regions of memory called caches. The job of the cache is to hold data that has recently been accessed from memory such that if that same memory region is accessed again, the value can be pulled from the cache (fast) rather than from main memory (slow). Typically, caches are designed so that if a value is read in from memory, that value, plus a whole bunch of adjacent values, are pulled into the cache. That way, if you iterate over an array, then after reading the first value, the rest of the values from the array will be sitting in the cache and can be accessed more efficiently.

的原因，并且code是慢于它需要的是，它不按顺序访问的数组元素。在C语言中，二维数组在行主要订单布局，这意味着内存安排

The reason that your code is slower than it needs to be is that it doesn't access the array elements sequentially. In C, 2D arrays are laid out in row-major order, meaning that the memory is arranged as

A[0][0] A[0][4] A[0][5] ... A[1][0] A[1][6] A[1][7] ... A[2][0] A[2][8] A[2][9] ...

因此​​，如果您使用的循环：

Consequently, if you use this for loop:

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        // Do something with A[i][j]
    }
}

然后你得到优秀的地方，因为你将访问在它们出现在内存中的顺序数组元素。这使得主内存的读取次数非常少，因为一切是典型的高速缓存，并准备去。

Then you get excellent locality, because you will be accessing array elements in the order in which they appear in memory. This makes the number of reads of main memory very small, since everything is typically in cache and ready to go.

不过，如果你交换的循环，因为你做了，你的访问跳来跳去在内存中，不一定是连续的。这意味着你将有很多的缓存未命中的在你下次读取内存地址不在缓存中。这增加了高速缓存负载的数量，从而可以在节目显着减缓。

However, if you interchange the loops, as you've done, your accesses jump around in memory and are not necessarily consecutive. This means that you will have a lot of cache misses in which the memory address you read next isn't in the cache. This increases the number of cache loads, which can dramatically slow down the program.

编译器开始变得足够聪明的自动交换这样的循环，但我们还是有办法远离能够忽略这些细节。作为一般规则，编写C或C ++ code多维数组时，尝试在行优先顺序排列，而不是列主顺序进行迭代。你可以得到显着的速度提升到程序中。

Compilers are starting to get smart enough to interchange loops like this automatically, but we're still a ways away from being able to ignore these details. As a general rule, when writing C or C++ code for multidimensional arrays, try to iterate in row-major order rather than column-major order. You can get noticeable speedups in your program.

希望这有助于！

这篇关于为什么糟糕的初始化这样的二维数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！