循环以零执行时间

是否有可能有一个环，其具有零执行时间？我认为即使是空循环也应该有一个执行时间，因为它有一个相关的开销。循环以零执行时间

来源

2014-11-06 user3678189

+37

循环可能会被展开和/或由编译器完全消除。 – 2014-11-06 04:24:54

优化编译器的主要工作之一是数据流分析。生成不会在任何地方流动的数据的计算被消除，包括循环。确切的行为取决于你的编译器。 – 2014-11-06 04:29:49

这实际上同样适用于C++，我也会将相关的C++引用添加到我的答案中。 – 2014-11-06 14:54:13

是 - 如果编译器确定循环是死代码（永远不会执行），那么它将不会生成代码。该循环将有0个执行时间，但严格来说，它不存在于机器代码级别。

来源

2014-11-06 04:25:41

119

是，根据为，如果规则编译器只是有义务模拟代码的可观察的行为，所以如果你有一个循环，没有任何可观察到的行为，那么它可以完全，因此优化掉将有效地执行零时间。

实例

例如以下代码：

int main() 
{ 
    int j = 0 ; 
    for(int i = 0; i < 10000; ++i) 
    { 
    ++j ; 
    } 
}

使用所述-O3标志gcc 4.9编译基本上最终减少到以下（see it live）：

main: 
    xorl %eax, %eax # 
    ret

几乎所有的优化都被允许在之下，因为如果规则为，我知道的唯一例外是copy elison，它允许影响可观察行为。

其他一些例子包括dead code elimination，它可以删除编译器可以证明永远不会执行的代码。例如，即使下面的循环确实含有副作用，可以优化掉了，因为我们可以证明这一点永远不会被执行（see it live）：

#include <stdio.h> 

int main() 
{ 
    int j = 0 ; 
    if(false) // The loop will never execute 
    { 
    for(int i = 0; i < 10000; ++i) 
    { 
     printf("%d\n", j) ; 
     ++j ; 
    } 
    } 
}

循环将优化掉同前例。一个更有趣的例子就是，在一个循环的计算可以推断为一个常数，从而避免为一个循环需要的情况下（不知道优化类别，这属于下），例如：

int j = 0 ; 
for(int i = 0; i < 10000; ++i) 
{ 
    ++j ; 
} 
printf("%d\n", j) ;

可以被优化掉，以（see it live）：

movl $10000, %esi #, 
movl $.LC0, %edi #, 
xorl %eax, %eax # 
call printf #

我们可以看到有没有参与循环。

凡作为，如果规则覆盖标准

的为，如果规则是覆盖在其中说，草案C99标准节5.1.2.3程序执行：

在抽象机器，所有表达式都按照指定的语义进行评估。一个实际的实现不需要评估表达式的一部分，如果它可以推断出它的值没有被使用，并且没有产生任何需要的副作用（包括由调用函数或访问一个易失性对象引起的任何副作用）。

as-if rule也适用于C++，gcc也会在C++模式下产生相同的结果。 C++标准草案包括在本节1.9程序执行：

在本国际标准的语义描述限定参数化非确定性抽象机。该国际标准没有要求符合实施的结构。尤其是，他们不需要复制或模拟抽象机器的结构。相反，符合实现需要（仅）模拟抽象机的可观察行为所解释below.5

来源

2014-11-06 14:46:16

我敢打赌，即使不是所有的语言规范都有一个_as-if_规则，大部分都是如此。如果不使用并且没有副作用，那么通常没有必要进行计算。它只会浪费时间和精力。 – 2014-11-06 21:57:19

+15

@CraigAnderson：绝大多数时候都是这样，但是有很少的情况你会做无用的计算，比如在你希望所有代码路径花费相同时间的加密操作中防止[定时通道攻击]（http://en.wikipedia.org/wiki/Timing_attack）。 – 2014-11-06 22:14:40

**换句话说**：对于执行实际的，不可避免的，不可作弊的工作的实际循环，答案是：**否**。对于只能做多余的东西的伪循环：**是**。 – 2015-02-01 15:29:54

除了编译器的优化，一些CPU架构，特别的DSP，具有零开销循环由此具有固定迭代次数的循环被硬件有效地优化，参见例如http://www.dsprelated.com/showmessage/20681/1.php

来源

2014-11-08 08:02:22

编译器没有义务评估没有副作用并且结果被丢弃的表达式或表达式的一部分。

哈比森和Steele，C: A Reference Manual

来源

2014-11-12 07:28:53

循环以零执行时间

回答

相关问题