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 ルールに該当します。私が認識している唯一の例外は、監視可能な動作に影響を与えることが許可されているコピー エリソンです。

他のいくつかの例には、コンパイラが決して実行されないことを証明できるコードを削除できるデッド コードの削除が含まれます。たとえば、次のループには実際に副作用が含まれていますが、実行されないことを証明できるため、最適化することができます (ライブを参照してください)。

#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 ルールはどこにありますか

as-if ルールは、ドラフト C99 標準セクション5.1.2.3 プログラムの実行で説明されています。

抽象マシンでは、すべての式がセマンティクスで指定されたとおりに評価されます。実際の実装では、式の値が使用されておらず、必要な副作用 (関数の呼び出しまたは揮発性オブジェクトへのアクセスによるものを含む) が生成されていないと推測できる場合、式の一部を評価する必要はありません。

as-if ルールはC++ にも適用されgcc、C++ モードでも同じ結果が生成されます。C++ ドラフト標準では、セクション1.9 プログラムの実行でこれをカバーしています。

この国際標準のセマンティック記述は、パラメータ化された非決定論的抽象マシンを定義します。この国際規格は、適合する実装の構造に要件を課していません。特に、抽象マシンの構造をコピーまたはエミュレートする必要はありません。むしろ、適合する実装は、以下で説明するように、抽象マシンの観察可能な動作をエミュレート (のみ) する必要があります.5

于 2014-11-06T14:46:16.997 に答える
12

コンパイラの最適化と同様に、一部の CPU アーキテクチャ、特に DSP にはゼロ オーバーヘッド ループがあり、固定回数の反復を伴うループがハードウェアによって効果的に最適化されます。たとえばhttp://www.dsprelated.com/showmessage/20681を参照/1.php

于 2014-11-08T08:02:22.897 に答える