用于高性能计算的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;
};

更广泛地说，您的问题涉及缓存未命中的想法。由于一个缓存未命中要比一个L1引用（链接）贵200倍，如果你的数据布局优化到你的计算，那么你就真的可以节省时间。然而，正如上面所暗示的，很少会出现这样的情况：简单地重新排列你的数据就神奇地使一切变得更快。考虑矩阵乘法。这是一个完美的例子，因为按照资源的要求，数据以单个数组的形式进行布局。然而，对于一个简单的三循环matmult GEMM实现，仍然有6种方法来安排您的循环。其中一些方法比其他方法效率高得多，但没有一种方法能给您提供接近峰值的性能。阅读本文对matmult的逐步解释，以更好地理解获得良好性能所需的所有算法优化。

上面应该说明的是，即使我们只有几个数组按照您的资源建议进行布局，单靠布局并不能给我们提供速度。好的算法可以。数据布局考虑因素（如果有的话）来自我们选择的算法和更高级别的硬件约束。

如果对于简单的数组和像矩阵乘法这样的操作是这样的话，那么通过扩展，您也应该期望对于“高级数据结构”也是这样。