ループ展開
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ループ展開（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.
[編集] 関連項目
- ループ分割
- ループ融合
- Duff's device
