ループ展開
ループ展開（ループてんかい、英語: Loop Unwinding）は、プログラムのサイズを犠牲に実行速度を最適化する、ループ変換と呼ばれる手法の1つである。ループアンローリング（英語: Loop Unrolling）とも呼ぶ。
ループ展開の目的は、毎回の繰り返しごとに発生する「ループの終了」条件のテストを減少させる（もしくはなくす）事によって、実行速度を向上させることである。ループは、ループ自体を制御するためのオーバーヘッドがなくなるように、独立した命令ブロックの連続に書き換えることができる。もし（ループ終了テストの除去によって）スピードがサイズの増大によるパフォーマンス低下を相殺するほど上がれば、大きな効果が得られる。さらにもし命令がループ同士で独立なら、すなわち前の周回の実行結果が後続の処理に影響しないなら、それらの命令ブロックは並列実行させる事も可能になる。
目次 |
[編集] 副作用
ループ展開には大きな副作用として以下のものがある。
- 一時的な値を保存するために、一回の繰り返しあたりのレジスタ使用頻度が増加し（最適化に依存するが）、パフォーマンスを低下させる。
- ループ展開後はコードサイズが大きくなる。これは組み込みアプリケーションにとって望ましくなく、またコードの可読性を低下させてしまう。大きなコードはまた、キャッシュミスを増加させパフォーマンスに悪影響を与える。
[編集] 簡単な例
あるプログラムの手続きで、データの集合体から100個の要素を削除(delete)する必要があるとする。このため、for ループ内で関数 delete(要素の番号) を呼び出す:
for (int x = 0; x < 100; x++)
{
delete(x);
}
この部分を最適化する場合、ループに必要なオーバヘッドがリソースを多大に消費しているなら、ループ展開で性能が向上する。ループ展開したコードは例えば以下のようになる:
for (int x = 0; x < 100; x += 5)
{
delete(x);
delete(x+1);
delete(x+2);
delete(x+3);
delete(x+4);
}
この修正の結果、新たなプログラムのループ回数は 100 回から 20 回に削減される。ジャンプ命令と条件付分岐命令の実行回数は5分の1となり、ループそのものの処理にかかる時間は大幅に削減される。
一方、ループ展開によってコードサイズは 3 行から 7 行に増え、コンパイラは展開された部分で必要となる変数を格納するレジスタをさらに必要とすることになる。加えて、展開前と展開後で処理結果が同じになるように、ループ変数のループ内での操作は注意深く行わなければならない。例えば、上の例で 6 回ぶんのループを展開した場合、100 は 6 で割り切れないため、展開前と同じ結果を得るには細工が必要となる。また、ループの終了条件が変数だった場合にはさらに問題は複雑化する。Duff's device を参照されたい。
[編集] 複雑性
単純なループでは、ループ制御は単なる管理オーバヘッドである。ループ自体は必要な結果に直接貢献することはなく、単にプログラマが同じコードをいくつもコーディングする手間を省くだけである。それだけであれば、コードの複製はプリプロセッサやエディタの機能を使っても実現できる。同様に if 文などの他の制御構文もコードの複製で置き換えることもできるが、結果として滅茶苦茶なコードが出来上がってしまう。プログラムは組み合わせに絶えず注意することができるが、人間はそれに我慢できず、間違いを犯す。例えば次の例を見てみよう:
for i:=1:8 do if i mod 2 = 0 then do_evenstuff(i) else do_oddstuff(i); next i;
これをループ展開すると if 文の条件部は定数になるので、次のようになる:
do_oddstuff(1); do_evenstuff(2); do_oddstuff(3); do_evenstuff(4); do_oddstuff(5); do_evenstuff(6); do_oddstuff(7); do_evenstuff(8);
しかし、もちろん展開される中身は手続き呼び出しである必要はない。
x(1) = 1; For i:=2:9 do x(i):=x(i - 1)*i; print i,x(i); Next i;
これは次のように展開される:
x(1):=1; x(2):=x(1)*2; print 2,x(2); x(3):=x(2)*3; print 3,x(3); ...etc.
コンパイラのループ展開によって大量のコードが生成されるとしても、更なる最適化が可能である。コンパイラが Factorial(n) を認識したとしたら驚きだが、階乗のテーブルへの他からの参照がなかった場合、コンパイラは配列を単なる変数に置換するかもしれない。
一般にループの中身は大きく、複雑な配列のインデックス付けに関連している。最も内側のループを展開することで様々な最適化が可能となるかもしれないが、効果は限定的である。
[編集] 参考文献
Kennedy, Ken; & Allen, Randy. (2001年). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0.
