4

考虑以下两个循环，其中 N = 10^9 或大到足以注意到效率低下的东西。

Loop x = 1 to N
    total += A(x)
    total += B(x)

或者

Loop x = 1 to N
    total += A(x)

Loop x=1 to N
    total += B(x)

每个函数采用 x，执行一些任意算术计算（例如 x^2 和 3x^3 或其他东西，无关紧要），并返回一个值。

整体运行时间是否会有任何差异，如果有的话，什么时候不会出现这种情况？

4

6 回答 6

2

每个循环需要四个动作：

  1. 准备（每个循环一次）
  2. 检查停止条件（每次迭代一次）
  3. 执行循环体（每次迭代一次）
  4. 调整用于确定迭代是否应继续的值（每次迭代一次）

当您有一个循环时，您只需为第 1、2 和 4 项“支付”一次；当你有两个循环时，你为所有东西“支付”了两次。

假设调用这两个函数的顺序并不重要，那么在大多数常见情况下差异不会很明显。但是，在非常罕见的非常紧凑的循环情况下，单个循环将占用更少的 CPU 资源。实际上，循环展开的一种常用技术依赖于通过多次重复主体来减少循环期间每次迭代检查和设置操作在整个 CPU 负载中的份额，并通过相应的因子减少迭代次数。

于 2013-03-03T20:08:57.843 回答
2

有几件事需要考虑。x一个是您在第二个版本中为循环本身（条件检查、递增等）执行了两倍的指令。如果你的功能真的很微不足道，那可能是一个很大的成本。

然而，在更现实的情况下，缓存性能、寄存器共享和类似的事情会产生更大的影响。例如，如果两个函数都需要使用大量寄存器，您可能会发现第二个版本的性能比第一个版本差，因为编译器需要将更多的寄存器溢出到内存中，因为它每个循环都执行一次。或者，如果A两者B都访问相同的内存，则第二个版本可能比第二个版本更快，因为所有B' 的访问都将是第二个版本中的缓存命中，但在第一个版本中未命中。

所有这些都是高度特定于程序和平台的。如果您要优化某些特定程序，则需要对其进行基准测试。

于 2013-03-03T20:11:39.657 回答
1

主要区别在于第一个测试 X 与 N、N 次，而第二个测试 X 与 N、2N 次。

于 2013-03-03T20:06:15.773 回答
0

循环本身有一点开销。

在每次迭代中，您至少需要执行 2 次操作，增加计数器，然后将其与最终值进行比较。

所以你正在做 2*10^9 更多的操作。

于 2013-03-03T20:07:03.220 回答
0

如果两个函数都使用了大量内存，例如他们创建了一些大数组，并在每次迭代中递归地修改它，那么由于内存缓存等原因，第一个循环可能会更慢。

于 2013-03-03T20:12:06.463 回答
0

有很多潜在的因素需要考虑；

1）迭代次数——循环设置是否支配任务 2）循环比较惩罚与任务复杂性

for (i=0;i<2;i++) a[i]=b[i];

3) 功能的一般复杂性 - 有两个复杂功能，其中一个可能会用完寄存器

4）注册依赖或本质上是任务序列 - 两个独立的任务混合与其他循环的结果取决于第一个

5) 循环是否可以完全在预取队列上执行——不需要缓存访问——混合在第二个任务中可能会破坏吞吐量

6）有什么样的缓存命中模式

于 2013-03-04T19:44:31.453 回答