将内存分配给C中的二维数组的最佳方法？

Question

从two-d array和speed两个角度来看，向C中的memory-management分配内存的最佳方法是什么？

另外，使用two-d array (并将内存分配给它)还是double pointer更好呢？有人能详细解释一下，里面发生了什么，为什么一种方法比另一种更好？

Answer 1

为了获得最佳性能和最佳可读性，此类数组应该始终作为一个连续的内存块分配：

type (*array) [X][Y] = malloc( sizeof(type[X][Y]) );

你应该避免这样做：

// BAD METHOD, not a real array

type** lookup_table = malloc( X*sizeof(type*) );
for(size_t i=0; i<Y; i++)
{
  lookup_table[i] = malloc( Y*sizeof(type) );
}

前者速度更快，原因很多。它是在一个连续的内存块中分配的，而不是在整个堆中分割。分段版本阻止了所有形式的代码优化和高效的片上数据缓存的使用，而且实际的分配也要慢得多。

不过，上面的“坏”版本有一个优点，那就是当您希望单个维度具有可变长度时，例如在为字符串创建一个查找表时。那你就得用那个表格。但是如果你想要一个真正的二维数组，没有理由不使用前者。

请注意，第一个版本通常编写为

type (*array) [Y] = malloc( sizeof(type[X][Y]) );

允许更方便地使用：array[i][j]，而不是可读性较低的(*array)[i][j]。

Answer 2

给定一个固定的大小，您可以简单地说twoDimArray[100][100]，它将在堆栈上分配它。但是，在堆上分配时(无论是因为大小很大还是因为大小是动态的)，您有更多的选项。

您可以分配一个指针数组，然后循环为每一行分配内存。这对于缓存局部性来说是有问题的，但如果大小非常大且您的访问是连续的，那么这是很好的；它允许在不影响性能的情况下进行合理的分割，因为数组数组可以与数组本身分离，而数组本身可以彼此分离。在线性访问场景中，大多数情况下，您不会在内存区域之间跳转；相反，在可能移动到新区域之前，您将跨越整条线进行访问。

第二种方法是将访问线性化并立即分配；也就是说，为sizex * sizey分配足够的内存，然后用(positiony * sizex) + positionx对其进行索引；也就是说，将一些行数下来，然后跨某些列进行索引。这对于随机访问很好，并且提高了缓存的局部性，因为内存是连续的，但是如果没有足够的连续内存可用(如果需要比缓存更多的内存，缓存局部性的好处就不适用了)。