优化C++ 2-D数组

我需要一种方法来表示C++中的双精度二维数组(密集矩阵),具有绝对最小的访问开销.

我已经在各种linux/unix机器和gcc版本上做了一些时间.向量的STL向量,声明为:

vector > matrix(n,vector(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的经验？

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

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

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

valarray a;

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

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

-fipa-matrix-reorg

执行矩阵展平和转置.矩阵展平尝试用等效的n维矩阵替换m维矩阵,其中n

请注意,-O2或-O3未启用此选项.你必须自己传递它.

很可能这是一个参考地点问题.vector用于new分配其内部数组,因此由于每个块的头部,每行在内存中至少相隔一点; 如果分配它们时内存已经碎片化,它可能相距很远.阵列的不同行可能至少会导致缓存线故障,并可能导致页面错误; 如果你真的不走运,两个相邻的行可能在共享一个TLB插槽的内存行上,而访问一个将驱逐另一个.

相比之下,您的其他解决方案可确保所有数据都相邻.如果您对齐结构以使其跨越尽可能少的缓存行,它可以帮助您的性能.

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

确保以正确的方向走数组,即跨越(连续的内存地址)而不是向下.这将减少缓存故障.

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