ループ展開の必要性はありますか？
解決最近ループ展開という記述方法を知りましたが、これは効果的なのでしょうか？
組込み等では効果的だよ、とか
そんなのは今時コンパイラがやってくれるよ、とか
その処理部分がボトルネックになってるかまず調べろよ、とかの回答を期待しております。
大味な質問で申し訳ありません・・・
case by case じゃないっすかねぇ。
小さなループならループ丸ごとCPUキャッシュに納まるでしょうし、
そうなりゃ展開しようがしまいが大差ないようにも思われます。
単純にループ展開 (unroll loop) というと、たとえば
for (i=0; i<N; ++i) func(i); のような呼び出しを
func(0); func(1); func(2); ... func(N-1); に置換するということ。
メリット：比較１個Ｎ回がいらない
デメリット：コードがでかくなる
通常は unroll だけしてもあまりおいしくないことが多く、
この例では unroll ＋ func をインライン展開できてはじめて高い効果が得られる。
(関数呼び出し１回のコストに対し、比較１回のコストなど無視できるほど小さい)
効果のほど/実用状況は、どうなんだろう・・・
少なくとも組み込み系ではまず使わない（メモリ量の節約のほうが大事）
Pentium 以後の「内蔵高速キャッシュがヒットしないと性能が出ない」 CPU では
・比較回数が減る効果
・コードがでかくなってキャッシュヒット率が下がる効果
のどっちが顕著に出るか、実測して何ぼな部分があるわけだ。
gcc などでは -funroll-loops や -funroll-all-loops など手指定ができるようになっている。
ってことはやはり効果を実測して使い分けるべき、ってことだと思うぞ。
回答ありがとうございます。
επιστημηさん
>小さなループならループ丸ごとCPUキャッシュに納まるでしょうし、
効果の有無はCPUキャッシュ依存となるわけですね。
tetrapodさん
>(関数呼び出し１回のコストに対し、比較１回のコストなど無視できるほど小さい)
関数呼び出しのコストは結構大きいんですね・・・知りませんでした。
>・比較回数が減る効果
>・コードがでかくなってキャッシュヒット率が下がる効果
なるほど。ここを考えるべきなのですね。
>gcc などでは -funroll-loops や -funroll-all-loops など手指定ができるようになっている。
こんなのがあるんですか！ちょっと調べてみます。
>ってことはやはり効果を実測して使い分けるべき、ってことだと思うぞ。
そういうことですね。
非常に詳しく有益な情報ありがとうございました。
とっかかりが分かりましたのでもう少し勉強してみます。
解決後に蛇足
最近の Pentium 互換 CPU は内部挙動が難しすぎて机上評価できない。
ウチで使っている組み込み系 CPU であるところの SH2/3/4 なら見積もったことがあって
(パイプラインが乱れない場合に限り、１命令の実行時間が１クロックとしてよい）
関数呼び出しにかかるコスト＝
呼び出し側命令コスト (引数を用意し返却値を受け取る） ５−１０命令
呼び出され側命令コスト (レジスタ退避復帰など) ２−２０命令
パイプラインが乱れるコスト 最悪４０クロック程度
見えないコスト（呼び出し側での最適化が制約されるコスト：見積もり不能）
の合計だったりするので、最小でも７クロック、最大だと６０クロック程度が必要。
# レジスタ復帰・退避の際にパイプラインが乱れるコストが意外に大きく無視できない
比較にかかるコスト＝
比較する数値を持ってくるコスト ２−３命令
比較しジャンプするコスト ２−３命令
パイプラインが乱れるコスト 最小０クロック、最悪でも数クロック
ということで、最小なら４クロック程度、最大でも１０クロックいかない程度。
昔々その昔の話をするなら、MZ-80 の画面消去するのに
・LD+DJNZ でループ組むと、画面消してる様子が見える
・スタックを一時的に VRAM 上に移して PUSH を unroll すると超高速
なんて話があったわけで、有効に unroll できれば効果絶大だったりする。
・だ・け・ど・
この手の小手先チューンに時間を割く暇があったらアルゴリズムの改善を検討するべき。
バブルソートを unroll しても、クイックソートやヒープソートには勝てない。
改善効果の桁が違う。
tetrapodさん
補足の説明ありがとうございます。
最後に本気出されて置いてかれまくった感があります（´；ω；）
CPU周りの勉強不足ですね・・・
>この手の小手先チューンに時間を割く暇があったらアルゴリズムの改善を検討するべき。
これはまったくその通りですね。肝に銘じておきます。
重ね重ね、ありがとうございました。
| ツイート |  |