为什么像这样初始化一个二维数组会更糟​​? [英] 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.

您的代码比它需要的慢的原因是它没有按顺序访问数组元素.在 C 中，2D 数组以 row-major order 排列，这意味着内存是排列为

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] ...

因此，如果你使用这个 for 循环:

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++ 代码时，尝试以行优先顺序而不是列优先顺序进行迭代.您可以在程序中获得明显的加速.

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屋！