Hatena::ブログ(Diary)

このブログは証明できない。

2010-10-30

[]ループをたくさん回す処理を高速化する初歩の初歩。

テキスト処理を中心にやっていましたが、画像処理に興味が出てきて、さっそくアプリを作りました。もともと下の記事のあたりでユーザーとして画像処理に興味を持って、当然の流れながら、自分でもつくってみようと。


で、何かを間違えて、普通の画像処理ではなく、カメラの映像をリアルタイムに加工しはじめました。そうすると、パフォーマンスがかなりシビアなんですね。


ピクセルを操作しなければなりませんから、ループをたくさん回す必要があります。なんとか高速化できないかと考えてみたところ、あっさり高速化に成功しました。私が気づくぐらいですから、初歩の初歩なんだと思います。


追記:Cの経験はないです。すみません。

追記:コメント欄も参考に。

追記:めずらしく、狙ってないのにはてブがたくさんついてます。この記事の内容は当てにならないですよー。とくに最初の「ループの中で変数を宣言しない」とか迷信っぽいです。むしろ、つっこみどころ満載らしいですよ。。。

追記:ホントにドシロウトが書いたので、鵜呑みにしないでー。

追記:体感速度が上がったなら、ベンチマークいらなくね?今回のケースであれば。いや、どれが有効だったか確認しといたほうがいいけど。




ループの中で変数を宣言しない

例えば、こんなコードであれば。

for (int i = 0; i < length; i++) {
    int value = func();
}

こう書き換えます。

int i, value;

for (i = 0; i < length; i++) {
    value = func();
}



構造体のメンバにアクセスしない

もちろん、OOPとか使ってる余裕はありません。それだけでなく、構造体のメンバにもアクセスしないほうがいいです。

int i, value;

for (i = 0; i < length; i++) {
    value = func(point.x, point.y);
}

ループの外で、変数に代入しておきます。

int i, value;
int x = point.x;
int y = point.y;

for (i = 0; i < length; i++) {
    value = func(x, y);
}



ループの中で演算を行わない

例えば、こんなコード。

int i;

for (i = 0; i < length; i++) {
    if (min + margin < value) {
        // 処理
    }
}

演算は、ループの外で。

int i;
int l = min + margin;

for (i = 0; i < length; i++) {
    if (l < value) {
        // 処理
    }
}



switchを使う

int i;

for (i = 0; i < length; i++) {
    if (flg == 0) {
        // 処理
    } else if (flg == 1) {
        // 処理
    } else {
        // 処理
    }
}

ifの場合は上から順に見ていきますが、switchはいきなりジャンプします。

int i;

for (i = 0; i < length; i++) {
    switch (flg) {
        case 0:
            // 処理
            break;
        case 1:
            // 処理
            break;
        default:
            // 処理
            break;
    }
}



ifの条件の順序を工夫する

極端な例を出すと。下のコードだと全ての条件が評価されます。

int i;

for (i = 0; i < length; i++) {
    if (!((value1 == 0) && (value2 == 0))) {
        // 処理
    }
}

下のように書き換えれば、value1が0でない時点で、次の条件は評価されません。

int i;

for (i = 0; i < length; i++) {
    if ((value1 != 0) || (value2 != 0)) {
        // 処理
    }
}

また、value2が0でないケースのほうが多い場合は、それを先に書くと効率的です。

int i;

for (i = 0; i < length; i++) {
    if ((value2 != 0) || (value1 != 0)) {
        // 処理
    }
}



インライン関数を使う

関数にinlineをつけると、関数呼び出しではなく、呼び出した箇所に処理が展開されます。

inline int func(int a, int b) {
    return a + b;
}

ただし、インライン展開されるかどうかは、コンパイラに依存します。




とうことをやってみると、かなり高速化できました。ほとんど我流なので、しかも今日思いついたことばかりなので、間違ったことを書いてたらスミマセン。。。

sta_blockheadsta_blockhead 2010/10/30 21:25 こんばんは、こんにちは。
--if ((value1 != 0) || (value2 != 0)) {
++if ((value1 != 0) && (value2 != 0)) {
では?

uzakadeuuzakadeu 2010/10/30 21:53 sta blockheadさんの指摘はドモルガンの定理ですよね。!(A and B) == !A or !B。

最適化レベル指定を上げてもこれらのテクニックが必要なら、あまり優秀なコンパイラ(gcc? LLVM?)じゃないな、という感想です。

sta_blockheadsta_blockhead 2010/10/30 22:04 うお、スイマセン、勘違いしてました。上記コメントは間違いです。

uzakadeuuzakadeu 2010/10/30 22:04 コメントを訂正です。
 誤:これらのテクニックが必要なら
 正:これらのテクニックが全部有効なら

sta_blockheadsta_blockhead 2010/10/30 22:46 コメント修正:
--上記コメントは間違いです。
++オレの上記コメントは間違いです。

nminorunminoru 2010/10/31 01:37 「ループの中で変数を宣言しない」
value は定義(値の代入)をされるものの参照が行なわれません。そのためかなり貧弱なコンパイラでない限り value への定義するコードを削除してしまうので、ループ変形の前後で高速化効果はないと思います。

「ループの中で演算を行わない」
min と margin が自動変数の場合、min + margin の計算はループの外にだせるということは、かなり初歩的なコンパイラでも解析できるので、コンパイラが自前でやってしまう可能性が高いです。

「構造体のメンバにアクセスしない」
これは point が自動変数の場合とそうでない場合に分かれます。
point が自動変数の場合は「ループの中で演算を行わない」と同じなのですが、グローバル変数の場合はループの前後で「メモリからの読み込み」が省略されたことになります。マルチスレッドプログラムの場合、point の内容を他のスレッドが書き換える可能性があるのでループ中に ponit の内容が一定かどうかはコンパイラは判断できません。
ただし gcc3 以上のコンパイラは最適化オプションをつけると、point は不変であると仮定をおいて強引に変形後のループのように最適化します。

「switchを使う」
これは有効な高速化で、連続する if 文をテーブルジャンプにするのはなかなかコンパイラ最適化ではできないと思います。コンパイラが十分に賢ければ、逆にソースコードに switch 文を書いておけば、ジャンプ命令のコストよりも分岐命令の連続の方が速いと判断すると、if 文の連続と同じコードを出すように判断してくれます(例えば1サイクルに条件分岐命令を3つまで処理できるIA-64のICCとか)。

「ifの条件の順序を工夫する」
他の方も指摘されていますが、1番目と2番目は同じです。
3番目は条件によっては有効だと思います。
ただ最近の CPU は分岐予測と out-of-order 実行を備えているのが主流です。この場合、条件式の中の value1、value2 が自動変数(非メモリアクセスで関数呼び出しでもない) 場合には、if の条件式全体を計算した後に 1 回だけ分岐するようなコードを出してくる可能性もあります。この場合、条件式をいろいろ変えても高速化できません。
条件式の中にメモリアクセスや関数呼び出しが入ってくる場合は、|| や && を評価しないのでいまでも有効だと思います。

あと分岐が分かれている場合、aの節とbの節をどちらを先に持ってくるかは性能に大きな影響があります。

 if (a) {
 } else (b) {
 }

ただ a と b をひっくり返すとソースが汚くなる場合も多いです。コンパイラの中には分岐命令の条件を指示することができるものがあります。GCC の場合、これを使って以下のようなマクロを定義し、

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

 if (unlikely(a)) { // これは成立しない可能性が高いと教える。
 } else (b) {
 }

あと最適化コンパイラの中には Profiled Guided Optimization(PGO) を備えたものもありますが、PGO コンパイラをされるとコンパイラが一気に最適化されたコードを出してくるので、上記のようなプログラム手法は無化されます。

shunsukshunsuk 2010/10/31 08:21 ありがとうございます。
なるほど、知識として持っていないといけませんね。

ここに書いたものをいろいろ試したので、どれが一番効いているかわかりません。
効果のなかったものもあると思います。
構造体のメンバにアクセスしない、min + marginを外に出す、は体感速度が確実に上がりました。

今回はiPhoneアプリなので、そのコンパイラの性質を調べてみます。

かもめかもめ 2010/10/31 22:36 これくらいコンパイラが最適化するでしょう。
コードを汚すくらいなら、適切なコンパイルオプションを覚えた方が有用なのでは?

かもめかもめ 2010/10/31 22:36 これくらいコンパイラが最適化するでしょう。
コードを汚すくらいなら、適切なコンパイルオプションを覚えた方が有用なのでは?

shunsukshunsuk 2010/10/31 22:44 私もそう思います。。

PSVPSV 2010/11/01 01:54 たぶん、この方法でもXcodeのデバッグモードでコンパイルしたなら、高速化されるですよ。
調べてみたら、デバッグ構成では、Xcodeのgccのオプションは、 -O0 だから最適化無しでござる。
http://twitter.com/psv_cast/status/29286128696
デバッグモードでしか確認してないのなら、「かなり高速化できました」は嘘ではないと思うよ。
リリースモードだと、 -Os の最適化がされるみたいなので、リリースモードでコンパイル
してみましょう!
http://developer.apple.com/jp/tools/xcode/xcodebuildsettings.html

shunsukshunsuk 2010/11/01 14:01 比較したのはリリースモードなんです。
体感速度なんて当てにならないと言われればそれまでですが。。
ちなみに、iOS SDKに含まれるXcodeの場合、デバッグでも-Osになってました。

PSVPSV 2010/11/01 20:58 ちゃんと、-Osオプションを付けて比較したのなら、たぶん inline最適化の効果が高い
ソースコードのだったのかもしれません。
実際にコードを見てないので、確認しようがありませんが・・・。
理由は、これ↓。
http://gcc.gnu.org/onlinedocs/gcc-3.4.6/gcc/Optimize-Options.html
=====
-O2
Optimize even more. GCC performs nearly all supported optimizations that do not involve a space-speed tradeoff. The compiler does not perform loop unrolling or function inlining when you specify -O2. As compared to -O, this option increases both compilation time and the performance of the generated code.
-O2 turns on all optimization flags specified by -O. It also turns on the following optimization flags:

-fforce-mem
-foptimize-sibling-calls
-fstrength-reduce
-fcse-follow-jumps -fcse-skip-blocks
-frerun-cse-after-loop -frerun-loop-opt
-fgcse -fgcse-lm -fgcse-sm -fgcse-las
-fdelete-null-pointer-checks
-fexpensive-optimizations
-fregmove
-fschedule-insns -fschedule-insns2
-fsched-interblock -fsched-spec
-fcaller-saves
-fpeephole2
-freorder-blocks -freorder-functions
-fstrict-aliasing
-funit-at-a-time
-falign-functions -falign-jumps
-falign-loops -falign-labels
-fcrossjumping

Please note the warning under -fgcse about invoking -O2 on programs that use computed gotos.

-O3
Optimize yet more. -O3 turns on all optimizations specified by -O2 and also turns on the -finline-functions, -fweb, -frename-registers and -funswitch-loops options.

-O0
Do not optimize. This is the default.

-Os
Optimize for size. -Os enables all -O2 optimizations that do not typically increase code size. It also performs further optimizations designed to reduce code size.
-Os disables the following optimization flags:

-falign-functions -falign-jumps -falign-loops
-falign-labels -freorder-blocks -fprefetch-loop-arrays
=====

-O3でないと自動でしてくれないinline展開の最適化を手動でしたわけですね。
比較するなら、-O3の最適化オプションを付けて試してみると面白いと思います。

ブランドコピーブランドコピー 2010/11/03 08:37 ブランドコピー
(GUCCI)、エルメス(HERMES)、コーチ(COACH)
◆ スタイルが多い、品質がよい、価格が低い!
◆ 送料無料(日本全国) ご注文を期待しています!
◆ 信用第一、良い品質、低価格は 私達の勝ち残りの切り札です。
◆ 当社の商品は絶対の自信が御座います。
◆ S/SS品質 シリアル付きも有り 付属品完備

fj68fj68 2013/06/15 21:16 こんにちは、はじめまして。

私がループの高速化で初めて習ったのは、降順にすることでした。
for (int i = length; i <= 0; i--) {
int value = func();
}
これぐらいならコンパイラが最適化してくれていそうなんですが、LLとかでも有効な時があるので。

babydaemonsbabydaemons 2013/11/02 21:38 iPhone実機だとARMですねー。
x86ならアセンブラ吐かせてみて雰囲気つかむのもありかも。

cfw4cfw4 2014/08/10 09:57 遅レスすいません。
コンパイラの最適化に関して議論呼んでますが、言語に限定されていないブログなので、価値ある内容だと思いますよ。特に、最適オプションが安定して働いてくれる言語なんて限られてますし、可読性にしてもコードの処理の律速になる部分にピンポイントで適応させれば問題はないんじゃないでしょうか?また、コードの公益性を考えても利用者がどんなコンパイラを使うのかわからない前提にたてばこういった最低限の高速化のための丁寧なコードは必要でしょう。

長生きのC言語にしたってbsdで標準化されそうなclangみたいな処理系も出てきてコンパイラは多様化していますし、コンパイラの挙動に左右されないコードはまた長生きします。個人的には(色々事情がある現場では難しいと思いますが、)コードの可読性は変数の宣言や演算の順序に左右されずに担保されるべきであると思います。また、最適化がオプションになっていることはデバッグ以外にも最適化オプションを付けない需要もあるわけです。

つまり言いたいことは、コンパイラに依存しない高速なコードを書くには学習コストが高くなるが、それに見合ったメリットは十二分にあるということです。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証