优化C++ 2-d阵列

我需要一种方法来代表用C双打的2 d阵列（致密基质）++，具有绝对最小访问开销。优化C++ 2-d阵列

我已经做了各种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。 n个指针的数组的每一行的开始处，或在堆栈上限定整个事情作为恒定大小matrix[n][n] - - 运行在几乎完全相同的速度指数函数法排列2-d阵列而不STL的其它方式。

当开启优化时，最近的GCC版本（> 4.0）似乎能够将STL向量向量编译成几乎与非STL代码相同的效率，但这与机器相关。

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

来源

2008-09-30 Chris Johnson

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

-fipa-matrix-reorg

执行矩阵平整和移调。矩阵展平尝试用其等价的n维矩阵替换m维矩阵，其中n为<米。这降低了访问矩阵元素所需的间接寻址级别。第二个优化是矩阵转置，试图改变矩阵的维度的顺序，以便改善缓存局部性。两个优化都需要编程标志。仅当分析信息可用时才能启用转置。

请注意，此选项不由-O2或-O3启用。你必须自己传递它。

来源

2008-09-30 12:19:53

对于矩阵，我的猜测是最快的是使用1D STL数组并重写（）运算符以将其用作2D矩阵。

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

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

valarray<double> a;

然后，您可以用切片的，间接的阵列，...当然，你可以继承的valarray和定义自己的操作符（）（INT i，int j）for 2D arrays ...

来源

2008-09-30 12:08:52 PierreBdR

我给予好评是的valarray，不一定要做出一个自定义的矩阵类型。那么，自定义矩阵类型可以工作，但仍然应该基于valarray而不是矢量（valarray支持切片，这使得获得一列就像获得一行一样简单）。 – 2008-09-30 12:12:56

小心继承std :: valarray;它不是为继承而设计的，因为大部分的“STL”。 – 2008-09-30 13:15:16

只要不向其中添加数据，就可以继承任何类的STL，因为构造函数不会被调用。虽然没有pb添加方法。 – PierreBdR 2008-09-30 13:33:52

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

来源

2008-09-30 12:08:57

很可能这是局部性的，参考的问题。 vector使用new来分配它的内部数组，所以每行在内存中至少会因为每个数据块的头部而分开;如果在分配内存时内存已经碎片化，它可能会有很长的距离。阵列的不同行可能至少会导致缓存行故障，并可能导致页面错误;如果你真的不走运，两条相邻的行可能在共享一个TLB槽的存储器行上，而访问它们将会驱逐另一行。

相反的其他解决方案保证所有的数据是相邻的。如果您调整结构以便尽可能少地使用缓存行，它可以帮助您提高性能。

vector是专为调整大小的阵列。如果您不需要调整数组大小，请使用常规C++数组。 STL操作通常可以在C++数组上运行。

确保以正确的方向走过阵列，即跨过（连续的存储器地址）而不是向下走。这将减少缓存故障。

来源

2008-09-30 12:17:09