5

为了提高应用程序的性能，我们必须在开发阶段考虑循环优化技术。

我想向您展示一些迭代简单的不同方法std::vector<uint32_t> v：

  1. 带索引的未优化循环：

    uint64_t sum = 0;
for (unsigned int i = 0; i < v.size(); i++)
    sum += v[i];

  2. 带有迭代器的未优化循环：

    uint64_t sum = 0;
std::vector<uint32_t>::const_iterator it;
for (it = v.begin(); it != v.end(); it++)
    sum += *it;

  3. 缓存std::vector::end迭代器：

    uint64_t sum = 0;
std::vector<uint32_t>::const_iterator it, end(v.end());
for (it = v.begin(); it != end; it++)
    sum += *it;

  4. 预增量迭代器：

    uint64_t sum = 0;
std::vector<uint32_t>::const_iterator it, end(v.end());
for (it = v.begin(); it != end; ++it)
    sum += *it;

  5. 基于范围的循环：

    uint64_t sum = 0;
for (auto const &x : v)
    sum += x;

还有其他方法可以在 C++ 中构建循环；例如通过使用std::for_each,BOOST_FOREACH等...

在您看来，提高性能的最佳方法是什么？为什么？

此外，在性能关键的应用程序中，展开循环可能很有用：同样，您会建议哪种方法？

4

5 回答 5

8

没有硬性规定，因为它取决于实施。然而，如果我几年前所做的措施是典型的：唯一不同的是缓存结束迭代器。无论容器和迭代器类型如何，修复前或修复后都没有区别。

当时，我没有测量索引（因为我也在比较不同类型容器的迭代器，并不是所有的都支持索引）。但我猜如果你使用索引，你也应该缓存结果v.size()。

当然，这些措施适用于一个系统上的一个编译器 (g++)，具有特定的硬件。您可以了解您的环境的唯一方法是衡量自己。

请注意：您确定您已开启全面优化。我的测量显示 3 和 4 之间没有区别，我怀疑编译器今天优化得更少。

对于这里的优化来说，函数实际上是内联的，这一点非常重要。如果不是，则后增量确实需要一些额外的复制，并且通常还需要额外的函数调用（对迭代器的复制构造函数）。然而，一旦函数被内联，编译器可以很容易地看到所有这些都是不必要的，并且（至少在我尝试它时）在两种情况下都生成完全相同的代码。（无论如何我都会使用预增量。不是因为它会产生影响，而是因为如果你不这样做，一些白痴会声称它会，尽管你采取了措施。或者他们可能不是白痴，但只是在使用一个特别愚蠢的编译器。）

说实话，当我进行测量时，我很惊讶缓存结束迭代器会产生影响，即使对于向量来说也是如此，因为前增量和后增量之间没有区别，即使对于映射中的反向迭代器也是如此。毕竟，end()它也是内联的；事实上，我的测试中使用的每一个函数都是内联的。

至于展开循环：我可能会做这样的事情：

std::vector<uint32_t>::const_iterator current = v.begin();
std::vector<uint32_t>::const_iterator end = v.end();
switch ( (end - current) % 4 ) {
case 3:
    sum += *current ++;
case 2:
    sum += *current ++;
case 1:
    sum += *current ++;
case 0:
}
while ( current != end ) {
    sum += current[0] + current[1] + current[2] + current[3];
    current += 4;
}

（这是 4 倍。如有必要，您可以轻松增加它。）

于 2013-08-13T15:51:47.663 回答
2

我假设您很清楚过早进行微优化的弊端，并且您已经通过分析和其他所有操作确定了代码中的热点。我还假设您只关心速度方面的性能。也就是说，您并不十分关心生成的代码或内存使用的大小。

您提供的代码片段将产生大致相同的结果，但缓存的end()迭代器除外。除了尽可能多地缓存和内联之外，您无法调整上述循环的结构以显着提高性能。

在关键路径中编写高性能代码首先依赖于为工作选择最佳算法。如果您有性能问题，请先仔细查看算法。编译器在微优化您编写的代码方面通常会做得比您希望的要好得多。

说了这么多，你可以做一些事情来给你的编译器一点帮助。

  • 尽可能缓存所有内容
  • 将小分配保持在最低限度，尤其是在循环内
  • 尽可能多地做东西const。这为编译器提供了额外的微优化机会。
  • 好好学习你的工具链并利用这些知识
  • 好好学习你的架构并利用这些知识
  • 学习阅读汇编代码并检查编译器的汇编输出

学习你的工具链和架构将产生最大的好处。例如，GCC 有许多选项可以启用以提高性能，包括循环展开。见这里。在迭代数据集时，保持每个项目与缓存行的大小对齐通常是有益的。在现代架构中，这通常意味着 64 字节，但请了解您的架构。

这是在英特尔环境中编写高性能 C++ 的绝佳指南。

一旦你了解了你的架构和工具链，你可能会发现你最初选择的算法在你的现实世界中并不是最优的。面对新数据，保持开放的态度。

于 2013-08-13T16:33:56.660 回答
2

现代编译器很可能会为您上面给出的方法生成相同的程序集。您应该查看实际的程序集（启用优化后）以查看。

当您担心循环的速度时，您应该真正考虑您的算法是否真正是最优的。如果您确信它是，那么您需要考虑（并利用）数据结构的底层实现。 std::vector在下面使用一个数组，并且根据编译器和函数中的其他代码，指针别名可能会阻止编译器完全优化您的代码。

有大量关于指针别名的信息（包括什么是严格的别名规则？ ），但 Mike Acton 有一些关于指针别名的精彩信息。

restrict关键字（参见What does the restrict keyword mean in C++? or, again, Mike Acton），多年来可通过编译器扩展使用并在 C99 中编码（目前仅作为 C++ 中的编译器扩展提供），旨在处理此问题. 在您的代码中使用它的方式更像 C，但可能允许编译器更好地优化您的循环，至少对于您给出的示例：

uint64_t sum = 0;
uint32_t *restrict velt = &v[0];
uint32_t *restrict vend = velt + v.size();
while(velt < vend) {
  sum += *velt;
  velt++;
}

但是，要查看这是否提供了差异，您确实需要针对您的实际问题分析不同的方法，并可能查看生成的底层程序集。如果您要对简单数据类型求和，这可能会对您有所帮助。如果您正在做任何更复杂的事情，包括调用无法在循环中内联的函数，则根本不可能有任何不同。

于 2013-08-13T16:39:22.833 回答
2

如果您使用的是 clang，则将这些标志传递给它：

  -Rpass-missed=loop-vectorize
  -Rpass-analysis=loop-vectorize

在 Visual C++ 中，将此添加到构建中：

  /Qvec-report:2

这些标志将告诉您循环是否无法矢量化（并给您一个经常神秘的信息来解释原因）。

但总的来说，更喜欢选项 4 和 5（或 std::for_each）。虽然 clang 和 gcc 在大多数情况下通常会做得不错，但可悲的是，Visual C++ 倾向于谨慎行事。如果变量的范围未知（例如，传递给函数的引用或指针，或 this 指针），则向量化通常会失败（本地范围内的容器几乎总是会向量化）。

#include <vector>
#include <cmath>

// fails to vectorise in Visual C++ and /O2
void func1(std::vector<float>& v)
{
  for(size_t i = 0; i < v.size(); ++i)
  {
    v[i] = std::sqrt(v[i]);
  }
}

// this will vectorise with sqrtps
void func2(std::vector<float>& v)
{
  for(std::vector<float>::iterator it = v.begin(), e = v.end(); it != e; ++it)
  {
    *it = std::sqrt(*it);
  }
}

Clang 和 gcc 也不能幸免于这些问题。如果您总是复制开始/结束，那么这不是问题。

这是另一个可悲地影响许多编译器的经典之作（clang 3.5.0 未能通过这个微不足道的测试，但它在 clang 4.0 中得到了修复）。它突然出现了很多！

struct Foo
{
  void func3();
  void func4();
  std::vector<float> v;
  float f;
};

// will not vectorise
void Foo::func3()
{
  // this->v.end() !!
  for(std::vector<float>::iterator it = v.begin(); it != v.end(); ++it)
  {
    *it *= f;  // this->f !!
  }
}

void Foo::func4()
{
  // you need to take a local copy of v.end(), and 'f'.
  const float temp = f;
  for(std::vector<float>::iterator it = v.begin(), e = v.end(); it != e; ++it)
  {
    *it *= temp;
  }
}

最后，如果这是您关心的事情，请使用编译器的矢量化报告来修复您的代码。如上所述，这基本上是指针别名的问题。您可以使用restrict 关键字来帮助解决其中一些问题（但我发现将restrict 应用于“this”通常没那么有用）。

于 2017-06-20T07:22:08.023 回答
0

默认情况下使用基于范围，因为它将为编译器提供最直接的优化信息（例如，编译器知道它可以缓存结束迭代器）。然后分析并仅在您发现重大瓶颈时进一步优化。在现实世界中，这些不同的循环变体会产生有意义的性能差异的情况很少。编译器非常擅长循环优化，您更有可能将优化工作集中在其他地方（例如选择更好的算法或专注于优化循环体）。

于 2013-10-25T23:48:10.907 回答