用于高性能计算的 C++ 类

Question

最简单的经验法则之一是记住硬件喜欢数组，并且针对数组迭代进行了高度优化。对于许多问题来说，一个简单的优化就是停止使用花哨的数据结构，而只使用普通数组（或 C++ 中的 std::vectors）。这可能需要一些时间来适应。

C++ 类是那些“奇特的数据结构”之一吗？即一种可以用数组替换以在 C++ 程序中实现更高性能的数据类型？

Answer 1

如果你的类看起来像这样：

struct Person {
  double age;
  double income;
  size_t location;
};

那么你可能会受益于重新安排

std::vector<double> ages;
std::vector<double> incomes;
std::vector<size_t> locations;

但这取决于您的访问模式。如果您经常一次访问一个人的多个元素，那么将这些元素锁定在一起是有意义的。

如果你的类看起来像这样：

struct Population {
  std::vector<double> many_ages;
  std::vector<double> many_incomes;
  std::vector<size_t> many_locations;
};

然后，您可以使用资源推荐的表格。单独使用这些数组中的任何一个比使用第一类要快，但同时使用所有三个数组中的元素可能会慢于第二类。

最终，您应该将代码构建得尽可能干净和直观。速度的最大来源将是对算法的深入理解和适当使用，而不是内存布局。我建议忽略这一点，除非您已经拥有强大的 HPC 技能并且需要从计算机中获得最大性能。在几乎所有其他情况下，您的开发时间和理智远比节省几个时钟周期更有价值。

更广泛地

与此相关的一篇有趣的论文是SLIDE: In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems。将 ML 算法映射到 GPU 已经做了大量工作，对于 ML 应用程序来说，正确的内存布局确实会产生真正的影响，因为训练花费了大量时间，而且 GPU 专门针对连续数组处理进行了优化。但是，该论文的作者认为，即使在这里，如果你很好地理解算法，你也可以通过优化内存布局击败专用硬件，他们通过让 CPU 的训练速度比 GPU 快 3.5 倍来证明这一点。
更广泛地说，您的问题涉及缓存未命中的概念。由于缓存未命中的成本比 L1 引用（链接）高 200 倍，因此如果您的数据布局针对您的计算进行了优化，那么您确实可以节省时间。然而，正如上面所暗示的，很少有情况是简单地重新排列数据就能神奇地让一切变得更快。考虑矩阵乘法。这是一个完美的示例，因为数据按照您的资源的要求布置在单个数组中。然而，对于简单的三循环 matmult GEMM 实现，仍然有 6 种方法来安排循环。其中一些方法比其他方法更有效，但它们都无法为您带来接近峰值性能的效果。阅读matmult 的分步说明，以更好地了解获得良好性能所需的所有算法优化。

上面应该证明的是，即使我们只有几个数组完全按照您的资源建议的方式布局，布局本身也无法给我们带来速度。好的算法可以做到这一点。数据布局考虑因素（如果有的话）来自我们选择的算法和更高级别的硬件限制。

如果对于简单的数组和矩阵乘法之类的运算是这样，那么通过扩展，您也应该期望对于“奇特的数据结构”也是如此。