迭代一次和迭代两次的性能差异？

Question

考虑诸如...

for (int i = 0; i < test.size(); ++i) {
        test[i].foo();
        test[i].bar();
}

现在考虑..

for (int i = 0; i < test.size(); ++i) {
        test[i].foo();
}
for (int i = 0; i < test.size(); ++i) {
        test[i].bar();
}

这两者之间花费的时间是否有很大差异？即实际迭代的成本是多少？似乎您重复的唯一实际操作是增量和比较（尽管我认为这对于非常大的 n 来说会变得很重要）。我错过了什么吗？

Answer 1

首先，如上所述，如果您的编译器无法优化 size() 方法，因此它仅被调用一次，或者只不过是一次读取（没有函数调用开销），那么它将伤害。

不过，您可能还需要关心第二个影响。如果您的容器大小足够大，那么第一种情况执行速度会更快。这是因为，当它到达 test[i].bar() 时，test[i] 将被缓存。第二种情况，使用分割循环，将会破坏缓存，因为每个函数总是需要从主内存重新加载 test[i] 。

更糟糕的是，如果您的容器（我猜是 std::vector ）有太多项目，以至于无法全部放入内存，并且其中一些必须位于磁盘上的交换中，那么差异将会很大，因为您必须从磁盘加载内容两次。

但是，您必须考虑最后一件事：只有在函数调用之间（实际上，容器中的不同对象之间）不存在顺序依赖性时，所有这一切才会产生影响。因为，如果你计算出来，第一种情况会：

test[0].foo();
test[0].bar();
test[1].foo();
test[1].bar();
test[2].foo();
test[2].bar();
// ...
test[test.size()-1].foo();
test[test.size()-1].bar();

而第二种情况会：

test[0].foo();
test[1].foo();
test[2].foo();
// ...
test[test.size()-1].foo();
test[0].bar();
test[1].bar();
test[2].bar();
// ...
test[test.size()-1].bar();

因此，如果您的 bar() 假定所有 foo() 都已运行，那么您如果将第二种情况更改为第一种情况，则会破坏它。同样，如果 bar() 假设 foo() 尚未在后面的对象上运行，那么从第二种情况转移到第一种情况将会破坏您的代码。

所以要小心并记录你所做的事情。

Answer 2

这样的比较有很多方面。

首先，两个选项的复杂度都是O(n)，所以有区别反正也不是很大。我的意思是，如果您编写具有大量 n 和“繁重”操作 .foo() 和 bar( 的相当大且复杂的程序，您一定不必关心它）。因此，只有在非常小的简单程序（例如，这是一种用于嵌入式设备的程序）的情况下，您才必须关心它。

其次，这取决于编程语言和编译器。例如，我确信大多数 C++ 编译器都会优化您的第二个选项，以生成与第一个选项相同的代码。

第三，如果编译器没有优化您的代码，性能差异将在很大程度上取决于目标处理器。考虑汇编命令术语中的循环 - 它看起来像这样（伪汇编语言）：

LABEL L1:
          do this    ;; some commands
          call that
          IF condition
          goto L1
          ;; some more instructions, ELSE part

即每个循环段落只是 IF 语句。但现代处理器不喜欢IF。这是因为处理器可能会重新排列指令以预先执行它们或只是为了避免空闲。使用IF（事实上，条件跳转或跳转）指令，处理器不知道它们是否可以重新安排操作。
还有一种称为分支预测器的机制。 来自维基百科的材料：

分支预测器是一个数字电路，试图猜测分支的方向分支（例如 if-then-else 结构）将在确定之前进行。

如果预测器的猜测是错误的，则 IF 的这种“软化”效果，不会将进行优化。

因此，您可以看到这两个选项都有大量条件：目标语言和编译器、目标机器、处理器和分支预测器。这一切使得系统变得非常复杂，你无法预见会得到什么确切的结果。我相信，如果您不处理嵌入式系统或类似的东西，最好的解决方案就是使用您更喜欢的形式。

Answer 3

对于您的示例，您还需要额外关注 .size() 的成本，因为在大多数语言中，都会对每次 i 递增进行比较。

有多贵？好吧，这取决于情况，这当然都是相对的。如果 .foo() 和 .bar() 很昂贵，那么相比之下，实际迭代的成本可能微不足道。如果它们非常轻量级，那么它将占您执行时间的较大比例。如果您想了解特定案例测试它，这是确定您的具体场景的唯一方法。

就我个人而言，我肯定会选择单次迭代来降低成本（除非您需要在 .bar() 之前进行 .foo() 调用来电）。

Answer 4

我假设 .size() 将是不变的。否则，第一个代码示例可能与第二个代码示例不同。

大多数编译器可能会在循环开始之前将 .size() 存储在变量中，因此 .size() 时间将会减少。

因此，两个 for 循环内的内容的时间将是相同的，但其他部分将是两倍。

Answer 5

性能标签，对。

只要您专注于这个或那个次要代码段的“成本”，您就不会注意到更大的图景（隔离）；你的目的是证明某些在更高层次上（在你孤立的背景之外）的做法是正确的，这只是不好的做法，并且违反了指导方针。这个问题的级别太低，因此太孤立。由一组集成组件组成的系统或程序比一组独立组件的性能要好得多。

当循环本身不必要地重复时，这个或那个隔离组件（在循环内工作）的速度或更快是无关紧要的，因此会花费两倍的时间。

假设你有一辆家用车（CPU），你到底为什么要：

• 坐在家里让你的妻子出去买东西
• 等她回来
• 自己开车，出去买东西
• 让她等你回来
  如果需要说明的话，您将花费 (a) 几乎一半来之不易的资源来同时执行一次旅行和购物，以及 (b) 回家后可以利用这些资源一起享受乐趣。

它与周六 9:00 的汽油价格、咖啡馆磨咖啡的时间或每次迭代的成本无关。

是的，时间和使用的资源存在很大差异。但成本不仅仅在于每次迭代的开销；还在于每次迭代的开销。这是一次有组织的旅行与两次连续旅行的总成本。

性能与架构有关；永远不要做任何事情两次（你可以做一次），这是更高层次的组织；将组成整体的部分整合起来。这并不是要在 Bowser 上数几便士或每次迭代的周期；而是要计算每个迭代的周期数。这些是较低级别的组织；它调整了零散部分的集合（而不是系统性的整体）。

Masseratis 无法比旅行车更快地通过交通拥堵。

Answer 6

它确实加起来。这是 Javascript 运行时两种情况之间的区别。花费了几乎两倍的时间。

然而，有时我仍然会循环两次，以提高可读性和可维护性，因为必须循环遍历少量元素。