c++ - 优化 C++ 二维数组

Question

我需要一种方法来表示 C++ 中双精度数的二维数组（密集矩阵），并且访问开销绝对最小。

我在各种 linux/unix 机器和 gcc 版本上做了一些计时。向量的 STL 向量，声明为：

vector<vector<double> > matrix(n,vector<double>(n));

并且通过matrix[i][j]访问比声明为的数组慢 5% 到 100% 访问：

double *matrix = new double[n*n];

通过内联索引函数访问matrix[index(i,j)]，index(i,j)计算结果为 i+n*j。在没有 STL 的情况下安排二维数组的其他方法——一个指向每行开头的 n 个指针的数组，或者将堆栈上的整个事物定义为一个常数大小matrix[n][n]——以与索引函数方法几乎完全相同的速度运行。

最近的 GCC 版本 (> 4.0) 似乎能够在打开优化时将 STL 向量的向量编译到与非 STL 代码几乎相同的效率，但这在某种程度上取决于机器。

如果可能，我想使用 STL，但必须选择最快的解决方案。有没有人有使用 GCC 优化 STL 的经验？

score 8 · Accepted Answer

对于矩阵，我的猜测是最快的，使用 1D STL 数组并覆盖 () 运算符以将其用作 2D 矩阵。

但是，STL 还专门为不可调整大小的数值数组定义了一种类型：valarray。您还可以对就地操作进行各种优化。

valarray 接受数值类型作为参数：

valarray<double> a;

然后，您可以使用切片、间接数组...当然，您可以继承 valarray 并为二维数组定义自己的 operator()(int i, int j) ...

score 8 · Accepted Answer

如果您使用 GCC，编译器可以分析您的矩阵访问并在某些情况下更改内存中的顺序。魔术编译器标志定义为：

-fipa-matrix-reorg

执行矩阵展平和转置。矩阵展平尝试将 m 维矩阵替换为其等效的 n 维矩阵，其中 n < m。这降低了访问矩阵元素所需的间接级别。第二个优化是矩阵转置，它试图改变矩阵维度的顺序以提高缓存局部性。两种优化都需要 fhole-program 标志。仅当分析信息可用时才启用转置。

请注意，-O2 或 -O3 不会启用此选项。你必须自己通过。

score 7 · Accepted Answer

很可能这是一个参考位置问题。vector用于new分配其内部数组，因此由于每个块的标题，每一行在内存中至少会分开一点；如果分配时内存已经碎片化，则可能相距很远。数组的不同行可能至少会导致缓存行错误并且可能会导致页面错误；如果你真的很不幸，两个相邻的行可能在共享一个 TLB 插槽的内存线上，访问一个会驱逐另一个。

相比之下，您的其他解决方案保证所有数据都是相邻的。如果您对齐结构以使其越过尽可能少的缓存行，它可以帮助您提高性能。

vector专为可调整大小的数组而设计。如果您不需要调整数组大小，请使用常规 C++ 数组。STL 操作通常可以对 C++ 数组进行操作。

一定要沿着正确的方向走阵列，即穿过（连续的内存地址）而不是向下。这将减少缓存故障。

score 6 · Accepted Answer

6

我的建议是使用 Boost.UBLAS，它提供了快速的矩阵/向量类。

于 2008-09-30T12:08:57.980 回答

score 1 · Accepted Answer

公平地说，取决于您在矩阵上使用的算法。

当您按行访问数据时，双重名称 [n*m] 格式非常快，因为除了乘法和加法之外几乎没有开销，而且因为您的行是在缓存中保持一致的打包数据。

如果您的算法访问按列排序的数据，那么其他布局可能具有更好的缓存一致性。如果您的算法访问矩阵象限中的数据，那么其他布局可能会更好。

尝试针对您正在使用的使用类型和算法进行一些研究。如果矩阵非常大，这一点尤其重要，因为缓存未命中可能会损害您的性能，而不是需要 1 或 2 次额外的数学运算来访问每个地址。

score 1 · Accepted Answer

1

你可以很容易地做 vector< double >( n*m );

于 2008-09-30T17:37:05.943 回答

score 1 · Accepted Answer

您可能想查看http://eigen.tuxfamily.org/上的 Eigen C++ 模板库。它生成 AltiVec 或 sse2 代码以优化向量/矩阵计算。

score 0 · Accepted Answer

Boost中有uBLAS实现。值得一看。

http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/matrix.htm

score 0 · Accepted Answer

另一个相关的库是 Blitz++：http ://www.oonumerics.org/blitz/docs/blitz.html

Blitz++ 旨在优化数组操作。

score 0 · Accepted Answer

通过声明我自己的二维数组类，我已经为原始图像做了这个。

在普通的二维数组中，您可以访问以下元素：

数组[2][3]。现在要获得这种效果，您将拥有一个带有重载 [] 数组访问器的类数组。但是，这实际上会返回另一个数组，从而为您提供第二维。

这种方法的问题在于它具有双重函数调用开销。

我这样做的方式是使用 () 样式重载。

所以不是array[2][3]，而是改变我让它做这种风格的array(2,3)。

那个 () 函数非常小，我确保它是内联的。

有关一般概念，请参阅此链接：http: //www.learncpp.com/cpp-tutorial/99-overloading-the-parenthesis-operator/

如果需要，您可以对类型进行模板化。
我的不同之处在于我的数组是动态的。我有一块我要声明的 char 内存。而且我使用了列缓存，所以我知道下一行在我的字节序列中从哪里开始。Access 已针对访问相邻值进行了优化，因为我将其用于图像处理。

没有代码很难解释，但本质上结果和 C 一样快，而且更容易理解和使用。

c++ - 优化 C++ 二维数组

10 回答 10

Related

Reference