75

是否有可能有一个执行时间为零的循环？我认为即使是一个空循环也应该有一个执行时间，因为它会产生开销。

4

4 回答 4

121

是的，在as-if 规则下，编译器只有义务模拟代码的可观察行为，所以如果你有一个没有任何可观察行为的循环，那么它可以被完全优化掉，因此实际上执行时间为零.

例子

例如下面的代码：

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

gcc 4.9使用标志编译-O3基本上最终减少到以下（现场查看）：

main:
  xorl  %eax, %eax  #
  ret

几乎所有允许的优化都属于as-if 规则，我知道的唯一例外是复制 elison，它允许影响可观察的行为。

其他一些示例包括死代码消除，它可以删除编译器可以证明永远不会执行的代码。例如，即使下面的循环确实包含一个副作用，它也可以被优化出来，因为我们可以证明它永远不会被执行（现场查看）：

#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 ) ;

可以优化为（现场查看）：

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

我们可以看到没有涉及循环。

标准中涵盖的“好像规则”在哪里

as-if 规则包含在草案 C99 标准部分5.1.2.3 程序执行中，它说：

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

as-if 规则也适用于 C++，在 C++ 模式下gcc也会产生相同的结果。C++ 标准草案在1.9 程序执行部分对此进行了介绍：

本国际标准中的语义描述定义了一个参数化的非确定性抽象机。本国际标准对一致性实现的结构没有要求。特别是，它们不需要复制或模仿抽象机器的结构。相反，需要符合要求的实现来模拟（仅）抽象机的可观察行为，如下所述。 5

于 2014-11-06T14:46:16.997 回答
52

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

于 2014-11-06T04:25:41.627 回答
12

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

于 2014-11-08T08:02:22.897 回答
3

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

Harbison and Steele, C：参考手册

于 2014-11-12T07:28:53.290 回答