我需要一种用绝对最小的访问开销来表示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的经验？

解决方案

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

但是，STL还定义了专门用于不可调整大小的数字数组的类型：valarray。我们还可以就地操作进行各种优化。

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

valarray<double> a;

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

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

这很可能是引用位置问题。 " vector"使用" new"分配其内部数组，因此由于每个块的标头，每一行在内存中至少间隔很小。如果分配内存时内存已经碎片化，则可能相距很远。阵列的不同行可能至少会导致高速缓存行错误并可能导致页面错误。如果我们真的不走运，则相邻的两行可能位于共享TLB插槽的内存行中，而访问其中一行将驱逐另一行。

相反，其他解决方案则保证所有数据都是相邻的。如果我们对齐结构，这样它可以越过尽可能少的高速缓存行，这可能对性能有所帮助。

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

确保以正确的方向(即连续(连续的存储器地址))而不是向下移动阵列。这将减少缓存故障。

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

-fipa-matrix-reorg

Perform matrix flattening and
  transposing. Matrix flattening tries
  to replace a m-dimensional matrix with
  its equivalent n-dimensional matrix,
  where n < m. This reduces the level of
  indirection needed for accessing the
  elements of the matrix. The second
  optimization is matrix transposing
  that attemps to change the order of
  the matrix's dimensions in order to
  improve cache locality. Both
  optimizations need fwhole-program
  flag. Transposing is enabled only if
  profiling information is avaliable.

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

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

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

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

尝试针对使用类型和使用的算法进行一些研究。如果矩阵很大，这一点尤其重要，因为高速缓存未命中可能对性能造成的损害比需要额外进行1或者2个额外的数学运算来访问每个地址更重要。

我们可以轻松地执行vector <double>(n * m);

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

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

我们可能需要查看Eigen C ++模板库，网址为http://eigen.tuxfamily.org/。它生成AltiVec或者sse2代码以优化矢量/矩阵计算。

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

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

我已经通过声明自己的二维数组类来对原始图像进行了一段时间。

在普通的2D数组中，我们可以访问以下元素：

数组[2] [3]。现在要获得效果，我们将拥有一个带有重载的类数组
[]数组访问器。但是，这实际上将返回另一个数组，从而使
你是第二个维度。

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

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

所以代替
array [2] [3]，更改我让它执行了这种样式array(2,3)。

()函数很小，我确保它已内联。

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

我们可以根据需要对类型进行模板化。
我的不同之处在于我的数组是动态的。我声明了一个char内存块。而且我使用了列缓存，因此我知道下一行从字节序列的何处开始。 Access已针对访问相邻值进行了优化，因为我正在使用它进行图像处理。

没有代码很难解释，但是从本质上讲，结果与C一样快，并且更易于理解和使用。