了解 2D 阵列的高效连续内存分配-解网

问：

以下代码来自《并行和高性能计算》的第 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# 引用第一个代码中的行。

C 多维阵列 malloc

但是，如果您要使用 MPI 之类的东西，您就不必进行样式索引了吗？因为 MPI 原语期望发送和接收指向连续内存块的指针，所以即使你从可以很好地索引的东西开始，比如第一个函数，在子进程中，你最终也会被迫做索引，对吧？无论如何，也许有任何性能提升？似乎不会有，但idk。作者肯定提到这种风格的数组是有原因的。但这对我来说并不明显arr[i * nrows +j]i*nrows+jarr[i][j]

4赞 tstanisl 12/26/2022

通过使用指向 VLA 的指针，可以充分利用两全其美（连续分配和良好的索引）。只是做：.double (*arr)[ncols] = calloc(nrows, sizeof *arr);

0赞 0___________ 12/26/2022

@tstanisl IMO的最佳方式。避免两个级别的间接

0赞 Andrew Henle 1/1/2023

请参阅正确分配多维数组

答：

5赞 Eric Postpischil 12/26/2022 #1

该书指出，这提高了内存分配和缓存效率。

与经常看到的单独分配指针的方法相比，本书的代码提高了效率，如下所示：

double **x = malloc(nrows * sizeof *x);
for (size_t i = 0; i < nrows; ++i)
    x[i] = malloc(ncols * sizeof *x[i]);

（请注意，所有方法都应测试结果并处理分配失败。此处的讨论省略了这一点。malloc

该方法单独分配每一行（从其他行和指针）。本书的方法有一些好处，即只进行一次分配，并且数组的内存是连续的。此外，不同行中元素之间的关系是已知的，这可能允许程序员在设计适用于缓存和内存访问的算法时利用这些关系。

有什么理由在效率上更喜欢第一个代码而不是下面的代码？

不是为了效率，不。本书的方法和上面的方法都有一个缺点，即它们通常需要对每个数组访问进行指针查找（除了基指针，）。在处理器可以从行的内存中获取元素之前，它必须从内存中获取行的地址。x

使用您显示的方法，不需要进行此额外的查找。此外，处理器和/或编译器可能能够预测有关访问的某些事情。例如，使用您的方法，编译器可能能够看到是与不同的元素，而 with 和，它通常无法知道这两个指针并且是不同的。M[(i+1)*ncols + j]M[(i+2)*cols + j]x[i+1][j]x[i+2][j]x[i+1]x[i+2]

这本书的代码也有缺陷。它分配的字节数为。假设 r 是， c 是， p 是和 d 是。然后代码分配 rp + rcd 字节。然后，代码设置为。因为它强制转换为，所以加法是以指向类型的单位完成的。因此，这会将 rd 字节添加到起始地址。之后，它期望拥有数组的所有元素，即 rcd 字节。因此，即使代码分配了 rp + rcd，代码也使用 rd + rcd 字节。如果 p > d，则数组末尾的某些元素将位于分配的内存之外。在当前的普通 C 实现中，大小小于或等于的大小，但不应依赖此。它应该计算，而不是设置为，加上类型元素的大小加上足够的填充，以达到的对齐要求，并且它应该在分配中包含该填充。nrows*sizeof(double*) + nrows*ncols*sizeof(double)nrowsncolssizeof(double*)sizeof(double)x[0](double *)x + nrowsdouble *nrowsdoubledouble *doublex[0](double *)x + nrows;xnrowsdouble *double

如果我们不能使用可变长度数组，那么数组索引可以由宏提供，例如定义一个用替换的宏，例如。x(i, j)x[i*ncols+j]#define x(i, j) x[(i)*ncols + (j)]

这是一个非常彻底的答案。我唯一有点困惑的部分是“书的代码是有缺陷的部分”。我认为关于字节对齐的讨论类似于这个 stackoverflow 问题;但是，在当前代码的上下文中，我仍然没有真正理解它。我担心我的心智模型（如我所包含的图所示）是错误的，因为我没有发现这个问题，如果可能的话，我想纠正我的理解。你能再解释一下吗？

0赞 Jared Frazier 12/26/2022

另外，w.r.t 定义一个被替换为的宏，你怎么能在 C 中做到这一点？我以前做过这种风格的索引，只需定义一个函数，如和然后。x(i,j)x[i*ncols+j]size_t ix(size_t i, size_t j, size_t ncols) { return i*ncols+j; }x[ix(i, j, ncols)]

0赞 Eric Postpischil 12/26/2022

@JaredFrazier：我错误地描述了书中代码中的缺陷。我已经更新了答案。我添加了一个宏定义，显示了如何完成数组索引。

上一个：在 C 中创建 2D 数组时检查 malloc 失败 [已关闭]

下一个：如何使用双指针在 C 中创建二维数组

了解 2D 阵列的高效连续内存分配

Understanding efficient contiguous memory allocation for a 2D array

评论

评论