一次循环执行两个操作 VS 两次循环执行一个操作的性能问题？

Question

我很久以前就对这个新手问题感兴趣了。

例如，我们有两种情况：

1. I have one any loop with two functions. (While or For does not matter).

   for (int i = 0; i < 1000; i++)
   {
       Function_1();
       Function_2();
   }
   

2. I have two loops with one action each.

   for (int i = 0; i < 1000; i++)
   {
       Function_1();
   }
   
   for (int i = 0; i < 1000; i++)
   {
       Function_2();
   }
   

我知道第一种方法的运行速度更快。

但是这两种情况之间的性能差异是多少？（以百分比表示）

如果最大循环次数增加，性能会降低多少？

在这些情况下，处理器或RAM哪个负载更大？

- denismart

---

除了@Servy所说的，没有普遍正确的答案，因为结果会因机器和功能而异。 - recursive

这个问题涉及到算法复杂度分析和大O符号。我建议看一下这个网站http://discrete.gr/complexity/，那里的第一部分非常清楚地回答了你的问题。 - Louie Bacaj

@recursive，提出一个没有普遍正确答案的问题既不违反SO规则，也不会使它成为一个糟糕的问题。这只是一个理论性问题。 - cowlinator

Answer 1

从纯理论角度来看，这两者之间没有区别。无论哪种方式，时间复杂度都是O(N)，就是这样。

从更实际的角度来看，缓存可以大大改变这个简单答案。可能会有一种比另一种更有效地使用缓存。但那不一定是你展示的第一种。

在现代计算机上，基本上就是一个关于哪个更有效地利用缓存的问题。

这取决于Function_1和Function_2各自使用了多少什么类型的内存。如果Function_1和Function_2都涉及执行相当多的代码，使得它们中的每一个都适合于L1指令缓存，但是它们两个加起来就不行，那么第二个版本很可能会更快。在这种情况下，第一个版本（在两个函数之间交替）每次执行时都必须从主内存加载每个函数，所以你需要从主内存加载代码约2000次。而在第二个版本中，你只需从内存中加载一次Function_1的代码，然后从缓存中执行1000次，接着再对Function_2做同样的操作。总共只需要从主内存加载2次。

换个方向想，假设Function_1和Function_2的代码都能够适应指令缓存，但Function_1和Function_2都作用于相同的数据，而这些数据的总量过大，无法适应数据缓存。

这通常会颠倒情况：对一块数据执行Function_1，然后再对同一块数据执行Function_2，只需从内存中加载一次该数据，然后进行所有必要的计算，接着再加载下一块数据，以此类推。每块数据只需要从主内存加载一次。

在这种情况下，你的第二个代码版本可能会慢大约2倍--它将加载一个内存块并在其上执行Function_1。然后它将加载第二个内存块，并在其中执行Function_1，以此类推。一旦所有内存都用Function_1处理完毕，它将重新加载所有相同的内存块以在它们上面执行Function_2。

当然，在现代处理器中，情况也不是那么简单。我们现在经常有2或3级缓存，通常具有不同的驱逐策略。第一级通常分为指令缓存和数据缓存，但通常还至少有一个统一的级别。这并没有消除上述因素，但可能会使情况变得更加复杂。

有一个完整的研究领域涉及到诸如缓存感知和缓存无关算法等内容，以帮助做出智能选择来处理像你这样的案例。缓存感知算法基于（更详细版本的）以上模型，选择如何组织计算以适应缓存组织。缓存无关算法则更多地针对缓存的相对通用模型，并提供良好的性能，几乎不考虑具体缓存的组织方式。

- Jerry Coffin