Loading article…
コンピュータサイエンスにおいて、ループ反転はコンパイラの最適化およびループ変換であり、whileループを do..while ループを含むif ブロックに置き換えるものです。[ 1 ]正しく使用すれば、命令パイプライン化やジャンプ命令の回避による分岐予測の誤りの減少により、パフォーマンスが向上する可能性があります。[ 1 ]
whileループ（無限ループ）では、各反復ごとに条件をテストする必要があります。テストが失敗した場合、ループは終了します。ループ本体の最後にテストを配置することで、ループ反転は最終反復の最後に発生するジャンプを回避します。
void pre_inversion () { while ( /* 条件 */ ) { /* ループ本体 */ } }は以下と同等です。
void post_inversion () { if ( /* 条件 */ ) { do { /* ループ本体 */ } while ( /* 条件 */ ); } }ループの最初と最後の反復では、条件が偽であるためループに入らない場合も含め、パフォーマンスに変化はありません。ただし、ループに入ると、do-while ループがループ条件を評価するために while ループの先頭にジャンプする必要がないため、最後の反復ではジャンプ命令が 2 つ少なくなります。[ 1 ]
int i , a [ 100 ]; i = 0 ; while ( i < 100 ) { a [ i ] = 0 ; i ++ ; }は以下と同等です。
int i , a [ 100 ]; i = 0 ; if ( i < 100 ) { do { a [ i ] = 0 ; i ++ ; } while ( i < 100 ); }2番目の例は一見複雑そうに見えますが、命令パイプラインを使用する最新のCPUでは実際にはより高速に実行される可能性があります。コード内のジャンプは本質的にパイプラインの停止を引き起こし、パフォーマンスを低下させるからです。
さらに、ループ反転により、ループ不変な安全なコード移動が可能になります。
i := 0 L1: i >= 100 の場合、L2 へ進む a[i] := 0 i := i + 1 L1へ移動 L2:
もし私が100で初期化されていたとしたら、実行時に実行される命令は次のようになります。
i >= 100 の場合 L2へ移動 i が100 未満の値で初期化されたと仮定しましょう。次に、ループ内でiが 99 にインクリメントされた直後に実行される命令を見てみましょう。
L1へ移動 i < 100 の場合 a[i] := 0 i := i + 1 L1へ移動 i >= 100 の場合 L2へ移動 <<L2で>> それでは、最適化されたバージョンを見てみましょう。
i := 0 i >= 100 の場合、L2 へジャンプ L1: a[i] := 0 i := i + 1 i < 100 の場合、L1 へ移動 L2:
もう一度、 iが100に初期化された場合に実行される命令を見てみましょう。
i >= 100 の場合 L2へ移動 元のバージョンと比較して、無駄なサイクルは一切ありませんでした。次に、 i がインクリメントされた場合を考えてみましょう。
i < 100 の場合 L1へ移動 a[i] := 0 i := i + 1 i < 100 の場合 <<L2で>> ご覧のとおり、実行時に2つのgoto文（つまり、2つのパイプラインストール）が排除されました。