STL 算法中跨函数边界的循环重新排序

Question

为了简单起见，我们假设我有一个由 N 矩阵组成的向量，每行 M 行。我正在使用 STL std::accumulate 来计算所有矩阵的总和。我传递一个二元函子，它接受两个矩阵（通过引用）并返回它们的总和（通过引用）。完全披露：我正在使用 libstdc++ 并行模式。在函子内部，我逐个循环行以计算总和。

尽管每个矩阵都太大而无法放入缓存，但一行却非常适合。因此，对循环进行重新排序是有利的，以便外部循环在 M 行上索引，内部循环在 N 矩阵上索引。除了定义内联函子之外，我还能做些什么来鼓励这种跨函数边界循环重新排序。我当然可以重构代码，但我理想地希望保留使用 STL 算法所提供的简单结构。如果有一些特定于 gcc 的东西，我也不介意。

我实际上并没有处理矩阵，这只是一个例子，但同样的问题结构也适用。主要问题是性能问题。解释实际场景会太麻烦，但核心问题是：STL 的累积需要在嵌套循环之间进行排序，这对缓存不太友好，因为它试图在移动到下一个对象之前完成两个对象的添加。单个对象太大而无法保存在缓存中，但它的一部分可以。因此，如果一次计算一个“部分”的“加法”（针对所有对象），则可以加快执行速度。手动重新排序循环可以显着提高 FLOPS。但我理想地希望编译器进行重新排序，以便我可以在 STL 级别进行编码（尽可能）。所以我正在寻找技巧来做到这一点。

Answer 1

class Matrix;
class Row;
struct SumNRow {
  int _rowidx;
//  Row _tempRow; //For return by reference left out for simplicity
  SumNRow(int iRowIdx): _rowIdx(iRowIdx) {}
  Row operator(const Matrix & iMarix1, const Matrix iMatrix2) {
    return iMarix1[_rowIdx] + iMatrix2[_rowIdx];
  }
};

template<class MatrixIterator>
void sum(const MatrixIterator & iMarixStart, const MatrixIterator & iMatrixEnd, Matrix & oMarix) {
  for (int i = 0; i < iMarixStart->rowCount(); ++i) {
    oMarix[i]=std::accumulate(iMarixStart, iMatrixEnd, SumNRow(i));
  }
}

Answer 2

我无法想象编译器会解决这个问题，除非所有内容都是内联的并且 M 和 N 是常量。即便如此，这也将是一个漫长的过程。

为了保持 STL 算法风格，请在累加上使用 foreach M 并让函子对一行求和。

Answer 3

编写新算法，或将内容包装在 for 循环或 std::for_each() 调用中。这比寻找适应 std::accumulate() 的方法要容易得多。我认为这里唯一的其他选择是向库引入一个新的抽象级别，超越迭代器。编写一个新算法或引入一个额外的循环会更容易。