top pageへ.

Programming Room.

Programming Techniques.

処理速度の向上.

 ちょっとしたコードの書き方の違いや工夫で、処理速度が変ることがあります。その差はわずかなものから、予想外の大きな差が出るものまで。どのような書き方で差が出るのか、なぜ差が出るのかを説明します。
 ここで説明するのは、コンパイラ言語に限定です。インタプリタ言語はそもそも処理速度が遅いので、私はインタプリタ言語の処理速度改善に関して興味がありません。


おしながき


register記憶クラス指定子.

C/C++言語 保守性 処理速度 メモリ効率 難易度

 C/C++言語では記憶クラス指定子を用いない限り、ローカル変数の値の記憶領域はスタック上に確保されます。しかし、ローカル変数の宣言をregister記憶クラス指定子で修飾すると、そのローカル変数はできる限りプロセッサのレジスタに確保されるようになります。変数のアクセスのためにメモリをアクセスする必要がなくなるので、変数へのアクセスが高速化されます。
 下記の例では、3行目で宣言した変数だけがレジスタに記憶されます。

    int     stacked_var1;               // スタックに記憶
    auto        int     stacked_var2;   // スタックに記憶
    register    int     registered_var; // レジスタに変数

 register記憶クラス指定子を使用する場合には以下の注意が必要です。


カウントダウンのループ.

C/C++言語 保守性 処理速度 メモリ効率 難易度

課題.

 ループ内部の処理ではなく、ループそのものを高速化出来る場合があります。
 次によくあるループと、そのアセンブルコードを示します。ループ回数が10回固定のループです。

C言語ソース アセンブルコード
    for (i = 0; i < 10; i++) {
        (処理)
    }
        mov     [i], 0          ; i = 0
for_loop
        (処理)
        inc     [i]             ; i++
        cmp     [i],10          ; i < 10
        jl      for_loop

改善案.

 上記の処理を高速化したのが次に示すソースと、そのアセンブルコードです。
 何のことはない、ループ変数iをカウントダウンするように変更しただけです。

C言語ソース アセンブルコード
    for (i = 10 - 1; i >= 0; i--) {
        (処理)
    }
        mov     [i], 9          ; i = 10 - 1
for_loop
        (処理)
        dec     [i]             ; i--
        jge     for_loop

理由.

 なぜこれだけで高速化されるのかは、コンパイル結果であるアセンブルコードを、高速化しないものと比較すればわかります。高速化した方は、ループの終了判断の比較命令がなくなっています。
 ループ変数iのデクリメントの結果、フラグ変化が起こります。このフラグ変化の結果はループ変数iを0と比較した結果ですから、ループの終了判断の比較命令は必要ないとコンパイラが判断して、このように比較命令が削除されました。実行される命令が減ったぶん、処理時間が短縮され、同時にメモリ使用量も減ります。
 ただし減るのは比較命令1つだけですから、効果はわずかです。そのため処理速度を少しでも稼ぎたいところ、保守性に影響しなさそうなところぐらいに使うだけで十分でしょう。

 アセンブリ言語でループを組む場合は、もはや定石ですね。


注意.

 注意しなければならないのは、何でもカウントダウンに変更すれば効果が出るわけではないことです。例えばループカウンタを表示のために参照していたりすると、表示が逆順になってしまいます。これを回避するためにループカウンタに演算を加えたりすると、その分処理が増えますので、効果がなくなったり、場合によっては逆に遅くなってしまったりします。またループの終了判断の比較命令は必要ないことを判断するのはコンパイラですから、コンパイラがこのように判断してくれるものでないと意味がありません。コンパイラによってはコンパイルオプションによって、ここで期待したとおりにコンパイルするものもあると思います。
 このテクニックにより高速化できる条件をまとめると、以下のとおりです。すべて満たす必要があります。


ループの展開.

言語依存なし 保守性 処理速度 メモリ効率 難易度

課題.

 ループ内部の処理ではなく、ループの処理そのものを高速化します。


改善案(?).

 ループ内部で行う処理を、ループしたい回数分だけベタで書きます。ループの制御に必要な処理がなくなる分、処理速度が速くなる場合があります。

通常のループ ループを展開したもの
    /* ループ回数8回 */
    for (i = 0; i < 8; i++) {
        (処理)
    }
    /* ループ回数分並べる */
    (処理)
    (処理)
    (処理)
    (処理)
    (処理)
    (処理)
    (処理)
    (処理)

応用.

 ループ回数が可変の場合、ループ回数相当のアドレスに分岐することで、ループ回数の制御が可能です。ただしループに入る前に、ループ回数が決定できる場合にしか使えません。


注意.

 すぐに分かるように、ループの制御がなくなるだけなので、ループ回数がある程度以上多くないと効果が期待できません。しかしループ回数が多いとコード領域の消費が多く、特にループ内の処理が複雑であればメモリ効率が非常に悪くなります。

 インストラクションキャッシュを持つプロセッサの場合、展開した処理が消費するコード領域がキャッシュのページサイズを超えると、キャッシュの再充填のためのペナルティが発生して、かえって処理速度が低下する可能性もあります。キャッシュを持つプロセッサでは、処理をコンパクトにしてページサイズに納まるようにした方が、処理速度・メモリ効率の両面で良好です。キャッシュを持つプロセッサが増えたこと、メモリ効率の悪化が激しいことから、近年ではこのテクニックが使われることはありません。プロセッサの性能が貧弱であった過去のテクニックであって、知識として「こんなテクニックもあった」と知っていれば十分です。

 アイデアとしては面白いですし、更なるアイデアを生み出す種になる可能性もあるので、説明してみました。


関数コール.

言語依存なし 保守性 処理速度 メモリ効率 難易度

課題.

 関数呼び出しを性能という側面から見ると、処理速度やメモリ効率などの、性能を低下させているという面があります。


理由.

 関数呼び出しが性能低下の要因になる理由は、関数呼び出しのコンパイル結果であるアセンブルコードを考えてみれば理解できます。
 1回の関数呼び出しの処理内容は、コンパイラによって差はありますが、基本的にはこんなものではないでしょうか。

  1. 引数に構造体がある場合、引数のコピーを生成する。
  2. すべての引数を順にスタックに積む。構造体の引数は1で生成したコピーへのポインタを積む。
  3. 必要なら戻り値を格納する領域をスタック上に確保する。
  4. リターンアドレスをスタックに積んで、関数へ分岐。
  5. 呼び出された関数が破壊するレジスタの値をスタックに待避する。
  6. ローカル変数用の領域をスタックに確保する。

 これに対応して、呼び出された関数から戻るときの処理内容は、次のようになります。

  1. 必要なら戻り値を、確保された領域へ格納する。
  2. ローカル変数用の領域を破棄する。
  3. 待避されたレジスタの値を復帰する。
  4. リターンアドレスをスタックから取り出し、そこへ分岐する。
  5. 必要なら格納された戻り値を読み出す。
  6. スタックに積んだ引数の分だけ、スタックポインタを戻す。
  7. 引数に構造体がある場合は、生成したコピーを破棄する。

 C言語のソースコードではたった1行の関数呼び出しも、アセンブルコードではこんなにも長い処理にコンパイルされます。当然実行時間も、この命令を格納するコード領域も、実行時に消費されるスタックも、それなりに必要になります。


改善案.

 必要以上に小さい関数に分けすぎると、性能が低下する原因になることを理解する必要があります。たった1回や2回の関数呼び出しなら無視できる程度でしょうが、ループで何度も呼び出される関数であったり、関数呼び出しのネストが深くなれば、「塵も積もれば…」ということになりかねません。
 ある程度まとまった処理は関数として分けることで、生産性・保守性・可読性が良くなることは事実です。それだけにとどまらず、要求されるものに応じて、性能とのバランスを取ることを考える必要もあることでしょう。

 コンパイラが関数呼び出しのコードを最適化するのは、現在では常識と化しています。そのため特定の処理系における実際の関数呼び出しのコードは、必ずしも上記に説明したとおりとは限りません。しかし多くの場合、ここで述べた「関数呼び出しの削減が性能の向上につながる場合がある」ことを覆すほどは最適化されません。


▲page top.
Copyright 2005-2016, yosshie.