有条件地向后或向前迭代的最快方法

Question

我至少可以想到三种选择循环方向的方法。

两个循环，一开始有一个条件（也许是最快的？）：

if (!backwards)
  for (int i = 0; i <= end; i++) {
  // code
  }
else
  for (int i = end; i >= 0; i--){
  // code
  }

循环多个元素，在内部进行测试和增量（我使用这个）：

for (int l = 0; l < max_len; l++) {
  // code
  if (!backward)
    i++;
  else
    i--;
}

使用可变增量和最终值（也许是最糟糕的？）

if (backward)
  inc = -1;
else
  inc = 1;
for (int i = 0; i != end; i += inc) {
  // code
}

哪种方式更快？编译器是否在每种情况下都对其进行优化？

Answer 1

在没有特定系统的情况下讨论性能是没有多大意义的。对于“通用计算机”，这里要考虑的事情是

改进机器代码的一种旧方法是尽可能编写递减计数循环，因为这会导致“如果为零则分支”指令，该指令比“如果等于则分支”指令稍快。然而，这种技术起源于编译器很糟糕的黑暗时代。对于现代的优化编译器，迭代顺序不应该成为性能问题。所以这个技巧基本上已经过时了。

除此之外，不同的循环可能会产生稍微更高/更低效率的代码，具体取决于系统。您可以拆解不同的版本并检查，但这是一个非常小的问题。

关于分支，第三个版本显然比其他版本好得多，因为它只包含一个分支 - 对循环迭代器的检查，它给出了循环本身。第一个版本更糟糕，第二个版本更糟糕。

然而，根据循环的实际作用，第三个版本可能不适合数据缓存。不可能说。

总的来说，这两个版本之一可能是最有效的：

for(size_t i=start; i!=end; i+=inc)

或者可能

size_t offset = backwards ? n-1 : 0;
for(size_t i=0; i<n; i++)
{
  size_t index = i - offset;
  arr[index] = something;
}

但唯一的判断方法是实际进行基准测试和反汇编。为此，您需要指定一个特定的系统。