1

很久以前，受“C 中的数值配方”的启发，我开始使用以下结构来存储矩阵（二维数组）。

double **allocate_matrix(int NumRows, int NumCol)
{
  double **x;
  int i;

  x = (double **)malloc(NumRows * sizeof(double *));
  for (i = 0; i < NumRows; ++i) x[i] = (double *)calloc(NumCol, sizeof(double));
  return x;
}

double **x = allocate_matrix(1000,2000);
x[m][n] = ...;

但是最近注意到很多人实现矩阵如下

double *x = (double *)malloc(NumRows * NumCols * sizeof(double));
x[NumCol * m + n] = ...;

从局部性的角度来看，第二种方法似乎很完美，但可读性很差......所以我开始怀疑，我的第一种存储辅助数组或**double指针的方法真的很糟糕，还是编译器最终会优化它，这样它会更还是在性能上不及第二种方法？我很怀疑，因为我认为在第一种方法中，在访问值时会进行两次跳转，x[m]然后x[m][n]每次 CPU 都有可能先加载x数组，然后再加载x[m]数组。

ps 不用担心额外的存储空间**double，对于大型矩阵来说，这只是一小部分。

PPS 因为很多人不太了解我的问题，所以我会尝试重新塑造它：我是否理解正确，第一种方法是一种局部性地狱，当每次x[m][n]访问时，第一个x数组将被加载到 CPU 缓存中并然后x[m]将加载数组，从而以与 RAM 通信的速度进行每次访问。还是我错了，从数据局部性的角度来看，第一种方法也可以？

4

5 回答 5

3

对于 C 风格的分配，您实际上可以两全其美：

double **allocate_matrix(int NumRows, int NumCol)
{
  double **x;
  int i;

  x = (double **)malloc(NumRows * sizeof(double *));
  x[0] = (double *)calloc(NumRows * NumCol, sizeof(double)); // <<< single contiguous memory allocation for entire array
  for (i = 1; i < NumRows; ++i) x[i] = x[i - 1] + NumCols;
  return x;
}

通过这种方式，您可以获得数据局部性及其相关的缓存/内存访问优势，并且您可以将数组视为可互换的double **或扁平的二维数组 ( )。您的/调用array[i * NumCols + j]次数也更少（与 相比）。callocfree2NumRows + 1

于 2017-05-17T16:36:13.550 回答
1

无需猜测编译器是否会优化第一种方法。只需使用您知道速度很快的第二种方法，并使用实现例如这些方法的包装类：

double& operator(int x, int y);
double const& operator(int x, int y) const;

...并像这样访问您的对象：

arr(2, 3) = 5;

或者，如果您可以在包装类中承担更多代码复杂性，您可以实现一个可以使用更传统arr[2][3] = 5;语法访问的类。这是在 Boost.MultiArray 库中以与维度无关的方式实现的，但您也可以使用代理类进行自己的简单实现。

注意：考虑到您使用 C 风格（硬编码的非泛型“double”类型、纯指针、函数开头的变量声明和malloc），您可能需要更多地了解 C++ 构造，然后才能实现我提及。

于 2017-05-17T16:23:45.753 回答
1

这两种方法是完全不同的。

  • 虽然第一种方法允许通过添加另一个间接（数组，因此您需要 1+N 个 malloc）来更轻松地直接访问值double**，...
  • 第二种方法保证所有值都是连续存储的，并且只需要一个 malloc。

我认为第二种方法总是更好。Malloc 是一项昂贵的操作，而连续内存是一个巨大的优势，具体取决于应用程序。

在 C++ 中，您只需像这样实现它：

std::vector<double> matrix(NumRows * NumCols);
matrix[y * numCols + x] = value;  // Access

如果您担心必须自己计算索引的不便，请添加一个实现operator(int x, int y)它的包装器。

你也是对的，第一种方法在访问值时更昂贵。因为您需要两次内存查找，如您所描述x[m]的，然后x[m][n]. 编译器不可能“优化掉它”。第一个数组，取决于它的大小，将被缓存，并且性能影响可能不是那么糟糕。在第二种情况下，您需要一个额外的乘法来直接访问。

于 2017-05-17T16:32:38.737 回答
0

如果NumCol是编译时常量，或者如果您使用启用了语言扩展的 GCC，那么您可以执行以下操作：

double (*x)[NumCol] = (double (*)[NumCol]) malloc(NumRows * sizeof (double[NumCol]));

然后x用作二维数组，编译器将为您执行索引算法。需要注意的是，除非 NumCol 是编译时常量，否则 ISO C++ 不允许您这样做，并且如果您使用 GCC 语言扩展，您将无法将代码移植到另一个编译器。

于 2017-05-17T17:32:36.243 回答
0

在您使用的第一种方法double*中，主数组中的 指向逻辑列（大小为 的数组NumCol）。

因此，如果您编写类似下面的内容，您将在某种意义上获得数据局部性的好处（伪代码）：

foreach(row in rows):
    foreach(elem in row):
        //Do something

如果您用第二种方法尝试了同样的事情，并且如果元素访问是按照您指定的方式完成的（即x[NumCol*m + n]），您仍然可以获得相同的好处。这是因为您将数组视为行优先顺序。如果您在以列优先顺序访问元素时尝试了相同的伪代码，我假设您会遇到缓存未命中，因为数组大小足够大。

除此之外，第二种方法具有作为单个连续内存块的额外理想属性，即使在循环多行时也可以进一步提高性能（与第一种方法不同）。

因此，总而言之，第二种方法在性能方面应该要好得多。

于 2017-05-17T16:35:27.857 回答