执行时间为零的循环 [英] Loop with a zero execution time

问题描述

是否可能有一个执行时间为零的循环?我认为即使是空循环也应该有一个执行时间，因为有一个与之相关的开销.

Is it possible to have a loop which has a zero execution time? I would think that even an empty loop should have an execution time since there is an overhead associated with it.

推荐答案

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

Yes, under the as-if rule the compiler is only obligated to emulate the observable behavior of the code, so if you have a loop that does not have any observable behavior then it can be optimized away completely and therefore will effectively have zero execution time.

示例

例如以下代码:

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

使用 -O3 标志使用 gcc 4.9 编译基本上最终会减少到以下内容 (现场观看):

compiled with gcc 4.9 using the -O3 flag basically ends up reducing to the following (see it live):

main:
  xorl  %eax, %eax  #
  ret

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

Pretty much all optimizations allowed fall under the as-if rule, the only exception I am aware of is copy elison which is allowed to effect the observable behavior.

其他一些例子包括 dead代码消除可以删除编译器可以证明永远不会执行的代码.例如，即使下面的循环确实包含副作用，它也可以被优化掉，因为我们可以证明它永远不会被执行(现场观看):

Some other examples would include dead code elimination which can remove code that the compiler can prove will never be executed. For example even though the following loop does indeed contain a side effect it can be optimized out since we can prove it will never be executed (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
", j ) ;
      ++j ;
    }
  }
}

循环将优化掉与上一个示例相同的内容.一个更有趣的例子是，循环中的计算可以推导出一个常数，从而避免循环的需要(不确定这属于什么优化类别)，例如:>

The loop will optimize away the same as the previous example. A more interesting example would be the case where a calculation in a loop can be deduced into a constant thereby avoiding the need for a loop(not sure what optimization category this falls under), for example:

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

可以优化为 (现场观看):

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

我们可以看到没有涉及任何循环.

We can see there is no loop involved.

标准中的 as-if 规则在哪里

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

The as-if rule is covered in the draft C99 standard section 5.1.2.3 Program execution which says:

在抽象机中，所有表达式都按照指定的方式计算语义.实际实现不需要评估部分表达式如果它可以推断出它的值没有被使用并且没有产生了所需的副作用(包括任何由调用函数或访问易失性对象).

In the abstract machine, all expressions are evaluated as specified by the semantics. An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object).

as-if 规则也适用于 C++，gcc 在 C++ 模式下也会产生相同的结果.C++ 草案标准在 1.9 程序执行 部分涵盖了这一点:

The as-if rule also applies to C++, gcc will produce the same result in C++ mode as well. The C++ draft standard covers this in section 1.9 Program execution:

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

The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.5

这篇关于执行时间为零的循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！