以零执行时间循环
是否有可能有一个零执行时间的循环? 我认为,即使是一个空循环应该有一个执行时间,因为有一个相关的开销。
是的,在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 。
其他一些例子包括死代码消除 ,可以删除编译器可以certificate永远不会执行的代码。 例如,即使下面的循环确实包含一个副作用,它也可以被优化,因为我们可以certificate它永远不会被执行( 见它现场 ):
#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
节程序执行中包含如下规则:
在抽象机器中,所有expression式都按照语义指定的方式进行评估。 如果一个实际的实现可以推断出它的值没有被使用,并且没有产生所需的副作用(包括由调用一个函数或者访问一个volatile对象引起的任何副作用),那么它就不需要评估一个expression式的一部分。
as-if规则也适用于C ++, gcc
也会在C ++模式下产生相同的结果。 C ++草案标准包含在1.9
节中:
本标准中的语义描述定义了一个参数化的非确定性抽象机器。 本国际标准对合规实施的结构没有要求。 特别是,他们不需要复制或模拟抽象机器的结构。 相反,需要符合的实现来模拟(仅)抽象机器的可观察行为,如下所述
是的 – 如果编译器确定循环是死代码(永远不会执行),那么它将不会生成代码。 该循环将有0个执行时间,尽pipe严格来说它不存在于机器代码级别。
除了编译器优化之外,一些CPU架构,特别是DSP,具有零开销循环 ,由此具有固定迭代次数的循环被硬件有效地优化,参见例如http://www.dsprelated.com/showmessage/20681 /1.php
编译器没有义务评估expression式,或expression式的一部分,它没有副作用,其结果被丢弃。
Harbison和Steele, C:参考手册