logo标签列表

优化C++ 2维数组

c++linuxoptimizationgccstl
7
我需要一种在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的经验吗？

10个回答
8

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

然而，STL还定义了一种专门用于非可调整大小的数字数组的类型：valarray。您还可以进行各种针对原地操作的优化。

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

valarray<double> a;

然后，您可以使用切片、间接数组等方式，当然，您还可以继承valarray并为2D数组定义自己的operator()(int i, int j)。

我的点赞是给valarray的，而不是一定要制作自定义矩阵类型。当然，自定义矩阵类型也可以工作，但仍应基于valarray而不是vector（valarray支持切片，这使得获取列与获取行一样容易）。 - C. K. Young
如果我理解正确的话，您可以使用私有继承来继承“不适合继承”的类，例如：class matrix : private std::valarray<double> 或类似的情况。基本上，您不依赖于任何虚拟行为。 - C. K. Young
1
请注意，即使您不添加成员数据，如果析构函数是非虚拟的，则通过指向基类型的指针删除派生对象是未定义的行为。 - Iraimbilanja
如果你是为了行为而继承，而不是为了指针/向上转型，那么这不会成为问题。然而，对于这样的目的，组合更有效（除了不得不重新声明整个类接口之外）。 - Luis Machuca
@Iraimbilanja - 你从哪里得到的？显然，由于叶子类的析构函数不会被调用，因此在那里没有任何事情需要处理。这意味着：没有虚方法，没有成员变量。否则，我看不出有什么问题。 - PierreBdR
显示剩余4条评论
8

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

-fipa-matrix-reorg

执行矩阵展平和转置。矩阵展平尝试使用等效的n维矩阵替换m维矩阵，其中n < m。这减少了访问矩阵元素所需的间接级别。第二个优化是矩阵转置，它试图改变矩阵维度的顺序以提高缓存局部性。这两种优化都需要设置fwhole-program标志。仅在可用的分析信息下启用转置。请注意，此选项不会由-O2或-O3启用，您需要自己传递该选项。
的确是令人惊奇和可怕的。 - peterchen
7
很可能这是一个局部引用问题。 vector 使用 new 来分配其内部数组，因此每行由于每个块的头而至少有一点在内存中分开；如果内存在分配它们时已经碎片化，那么它们可能会相距很远。数组的不同行很可能至少会遇到缓存行故障，并可能遇到页面故障；如果你很不幸，两个相邻的行可能在共享一个 TLB 插槽的内存行上，访问一个会驱逐另一个。
相比之下，你的其他解决方案保证所有数据都是相邻的。如果你使结构尽可能跨越较少的缓存行，它可能有助于提高性能。 vector 是为可调整大小的数组设计的。如果你不需要调整数组大小，请使用常规的 C++ 数组。STL 操作通常可以在 C++ 数组上运行。
确保按正确的方向遍历数组，即横向（连续的内存地址）而非纵向。这将减少缓存故障。
我没有考虑到向量解决方案中的块头。不过我知道走错路可能会导致潜在的减速：我的速度测试表明，走错路可能比正确方式慢四倍！ - Chris Johnson
6

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

我应该澄清一下，虽然我在处理矩阵，但我执行的操作并不是典型的线性代数运算。UBLAS 在线性代数方面非常出色，但如果我只是将其用作二维数组存储的话，可能有些过于复杂了。 - Chris Johnson
我尝试过各种线性代数库来处理二维数据（地图），但它们不方便用于非线性代数目的，也不比向量数组更快。UBLAS（和其他库）仅适用于乘法和其他“典型”矩阵用途，而不太适用于访问。 - Roel
1
1

公平起见，这取决于您在矩阵上使用的算法。

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

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

尝试进行一些针对您正在使用的用途和算法的研究。如果矩阵非常大，则特别重要，因为缓存未命中可能会比需要1或2个额外的数学运算来访问每个地址更严重地影响性能。

1

你同样可以使用 vector< double >( n*m );

0
0

我曾经针对原始图像做过这件事，通过声明自己的二维数组类。

在普通的2D数组中，您可以像这样访问元素：

array[2][3]。现在要达到这个效果，您将拥有一个具有重载 [] 数组访问器的类数组。但是，这实质上会返回另一个数组，从而为您提供第二个维度。

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

我的方法是使用 () 形式的重载。

所以，不是array[2][3]，我将其更改为array(2,3)。

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

请参阅此链接了解该概念的一般概念：http://www.learncpp.com/cpp-tutorial/99-overloading-the-parenthesis-operator/

如果需要，您可以对类型进行模板化。
我的区别在于我的数组是动态的。我有一块char内存块，我会声明它。我使用了列缓存，所以我知道下一行在字节序列中的位置。访问被优化为访问相邻值，因为我将其用于图像处理。

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

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接