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

Question

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

另外，最好使用哪个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) );
}

出于许多原因，前者更快。它被分配在一大堆内存中，而不是在整个堆中分割。分段版本阻止了所有形式的代码优化和有效的片上数据缓存的使用，加上实际分配也要慢得多。

上面的"不良"版本具有一个优势，那就是您希望单个维度具有可变长度的时候，例如为字符串制作查找表时。然后，您必须使用该表格。但是，如果您想要一个真正的2D数组，就永远没有理由不使用前者。

---

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

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

允许更方便的用途：array[i][j]，而不是不太可读的(*array)[i][j]。

Answer 2

data_type (*mat)[size_2] = malloc(size_1 * size_2 * sizeof(data_type));

将为数组数组（" 2D数组"）分配连续内存。如果您不需要荒谬的 ¹ 数量的空间，那么这是必经之路。您将减少内存碎片，增加缓存友好性并避免使用malloc。

---

¹ _{对于某些（应用程序特定）荒谬的定义}

Answer 3

给定固定尺寸，您可以简单地说twoDimArray[100][100]，它将在堆栈上分配。但是，当在堆上分配时（无论是因为大小很大还是因为大小是动态的），您都有更多选择。

您可以分配一系列指针，然后循环通过为每行分配内存。这对于缓存局部性来说是有问题的，但是如果大小很大并且访问是顺序的，则非常好；它允许合理的碎片化，而不会对性能产生巨大影响，因为阵列的数组可以与数组本身分开，它们可以彼此分开。在线性访问方案中，您将主要是在内存区域之间跳跃。相反，您将在整个生产线上访问，甚至可能移至新区域。

第二种方法是使访问访问并立即分配。即，为sizex * sizey分配足够的内存，然后用(positiony * sizex) + positionx索引。也就是说，倒数一些行，然后在某些列上计数。这对于随机访问非常有用并改善缓存局部性，因为内存是连续的，但是如果没有足够的连续内存可用（如果您需要更多的内存比CACHE）。p>