了解二维数组的高效连续内存分配
Jar*_*ier 2 c malloc multidimensional-array
以下代码来自pg. 93并行和高性能计算，是 2D 数组的单个连续内存分配：
double **malloc_2D(int nrows, int ncols) {
double **x = (double **)malloc(
nrows*sizeof(double*)
+ nrows*ncols*sizeof(double)); // L1
x[0] = (double *)x + nrows; // L2
for (int j = 1; j < nrows; j++) { // L3
x[j] = x[j-1] + ncols;
}
return x;
}
书中指出，这提高了内存分配和缓存效率。是否有任何理由在效率方面更喜欢第一个代码而不是下面的代码？看起来下面的代码更具可读性，并且也可以轻松地与 MPI 一起使用（我只提到这一点，因为本书稍后也介绍了 MPI）。
double *malloc_2D(int nrows, int ncols) {
double *M = (double *)malloc(nrows * ncols * sizeof(double))
return M
}
我添加了下图，以确保我的第一个代码的思维模型是正确的。如果不是，请在答案中提及。该图像是调用第一个函数创建 5 x 2 矩阵的结果。请注意，为了清楚起见，我只是将索引写在下图中的框中，当然，存储在这些内存位置的值不会是 0 到 14。另请注意，L#指的是第一个代码中的行。
\n\n书中指出，这提高了内存分配和缓存效率。
\n
book\xe2\x80\x99s 代码相对于常见的单独分配指针的方法提高了效率，如下所示：
\ndouble **x = malloc(nrows * sizeof *x);\nfor (size_t i = 0; i < nrows; ++i)\n x[i] = malloc(ncols * sizeof *x[i]);\n（请注意，所有方法都应测试结果malloc并处理分配失败。此处的讨论省略了这一点。）
该方法单独分配每一行（与其他行和指针）。book\xe2\x80\x99s 方法有一些好处，即只完成一次分配，并且数组的内存是连续的。此外，不同行中的元素之间的关系是已知的，这可以允许程序员在设计与高速缓存和内存访问配合良好的算法时利用这些关系。
\n\n\n是否有任何理由在效率方面更喜欢第一个代码而不是下面的代码？
\n
不是为了效率，不是。book\xe2\x80\x99s 方法和上面的方法都有缺点，它们通常需要为每个数组访问进行指针查找（除了基指针x）。在处理器可以从内存中获取行的元素之前，它必须从内存中获取该行的地址。
使用您展示的方法，不需要进行这种额外的查找。此外，处理器和/或编译器可能能够预测有关访问的一些事情。例如，对于您的方法，编译器可能能够看到 是M[(i+1)*ncols + j]与 不同的元素M[(i+2)*cols + j]，而对于x[i+1][j]和x[i+2][j]，它通常无法知道这两个指针x[i+1]并且x[i+2]是不同的。
book\xe2\x80\x99s 代码也有缺陷。它分配的字节数是nrows*sizeof(double*) + nrows*ncols*sizeof(double)。可以说r是nrows，c是ncols，p是sizeof(double*)，d是sizeof(double)。然后代码分配rp + rcd字节。然后代码设置x[0]为(double *)x + nrows. 因为它强制转换为double *，所以 的加法nrows是以指向类型 的单位完成的double。所以这会将rd字节添加到起始地址。之后，它期望拥有数组的所有元素，即rcd字节。因此，代码使用rd + rcd字节，即使它分配了rp + rcd。如果p > d，则数组末尾的某些元素将位于分配的内存之外。在当前普通 C 实现中， 的大小double *小于或等于 的大小double，但这不应依赖。它应该计算加上x[0]类型元素的大小加上足够的填充来达到对齐要求，而不是设置为(double *)x + nrows;xnrowsdouble *double，而不是设置为 ，并且应该在分配中包含该填充。
如果我们不能使用可变长度数组，则可以通过宏提供数组索引，例如定义一个替换为 的宏x(i, j)，x[i*ncols+j]例如#define x(i, j) x[(i)*ncols + (j)]。