自分がプログラムを最適化する時に、気を付けていることをまとめてみました。
最適化したつもりなのに、イマイチ速くならない…と悩んでる人向けです。

言語特有の処理が絡む部分はActionScript3.0を前提にしていますが、
大部分は他の言語でも役立つはずです。

 

最適化の前に

最適化する前に、必ずやることがあります。
それは、どこのコードにどれだけ実行時間がかかっているかを調べることです。

処理時間のうち、全体の5%しか使っていない部分を80%最適化するより、
全体の70%を使っている部分を10%最適化するほうが効果が見込めます。

時間を計測するコードを各所に挟んでもいいですし、
(AS3にはgetTimerという便利なメソッドがありますよ)
何かプロファイリングツールを使ってもいいので、
とにかくどこの処理にどれだけの時間がかかっているかをまず把握しましょう。

これをすっ飛ばすと後で大変なことになります。

 

ターゲットを定める

どこにどれだけの時間がかかっているかが把握できたら、
集中的に最適化する場所を定めます。

前述の通り、ほとんど時間がかかっていない所で
様々なテクニックを使って最適化を施したところで全くの無駄です。

実行時間の大半を占める固まったコードがあるはずなので、
そこを何とかしていきます。

取るに足らない部分のコードは最適化対象から外しましょう。

 

そもそもなぜ時間がかかるのか

最適化すべき部分が分かった所で、もう一度コードを分析します。
コードが遅い原因には大きく分けて2通りのパターンがあります。

・計算量的には特に問題はないが、コードの書き方に無駄がある
・そもそもコンピューターに要求する計算量が多すぎる

このうち大抵は前者ですが、ゲーム内等でオブジェクトを増やした際に
極端な速度低下が見られる場合は、後者である可能性があります。

まずはコードの書き方に無駄がないか見直してみましょう。

 

無駄のないコードを書く

さて、ここからの解決法は言語に依存してきます。
ActionScript3.0の場合、特に時間のかかる処理は次のようなものです。

・new によるインスタンス生成
・配列へのアクセス
・Mathクラスのメソッド
・メソッドの呼び出しによるオーバーヘッド

この他にも多々ありますが、上記を何とかすれば大抵の問題は解決してくれます。

 

new が多すぎる

遅いコードで、不要なインスタンスを生成しまくっている例をよく見かけます。

ActionScript3.0やJavaなどの言語では、new でインスタンスを生成する処理というのは
相当に時間がかかるものです。

これらの言語はC/C++などと違い、使われなくなったインスタンスのメモリは
すぐには開放されず、後にGC※のお世話になることとなります。
※Garbage Collection, 孤立したオブジェクトのメモリを開放するシステム
このGCが作動する際にプログラムの動作が一瞬停止するため、
更に体感速度を下げる原因となります。

まずは使い捨てになっているインスタンスがないかチェックしてみてください。
メソッドの引数に渡すためだけに生成するオブジェクトなどがその好例です。

特に構造体(Vector3DやMatrix3Dなど)については、臨時用にグローバル変数を
あらかじめ用意し、使う直前に中身をセットして渡すのが理想的です。
ただし、同一インスタンスを使い回すので参照が共有されないように注意してください。
過剰な使い回しはバグの原因にもなりかねません。

それと、意外と気付きにくいのが、「知らない内にインスタンスを生成していた」
という事例です。

返り値が構造体になっているメソッドは、
大抵はその中で一つ以上のインスタンスが生成されます。
getterについても同様に、別の参照を持たせるために内部でインスタンスを
生成することが多いです。

このあたりにも注意してみてください。

 

呼び出し・アクセスのコスト

どの言語にもメソッド呼び出しにかかるコストは少なからずあるものですが、
その中でもActionScript3.0はメソッド呼び出しのコストが大きい言語です。

1フレームに数十、数百回程度の呼び出しでは大した問題にはなりませんが、
数万、数十万回ともなってくると、意外と時間を取られます。

一見フィールドのようにアクセスできるgetterやsetterも中身はメソッドです。
マウス座標など、フレーム内で変化しないものであれば
あらかじめ値を保存しておき、なるべく呼び出しをループの外に追いやっておきます。
これは非常に気付きにくく、以前に大変苦労した覚えがあります…

メソッドが頻繁に呼び出されるようであれば、
インライン展開※することである程度の高速化が期待できます。
※メソッドの中身を呼び出している部分に展開すること
多重ループになっている場合、内側のループほど重点を置いて展開してみてください。

逆にループの外側ではほとんど効果が得られず、可読性を下げるだけなので
展開しないようにしておきます。

最新のAS3コンパイラーでは、条件を満たせば、タグを付けておくことでコンパイル時に
自動でインライン展開をしてくれるようなので、それを使ってみるのもいいかもしれません。

また、配列へのアクセスが非常に遅いのもAS3の特徴です。

配列にArrayや可変長Vectorを使った場合、固定長Vectorに比べ数倍の時間がかかります。
恐らくはアクセスする度にサイズチェックや拡張チェックをするためだと思われます。

固定長のVectorを使っても普通のフィールドに比べ時間はかかりますが、
Arrayや可変長Vectorよりは遥かにマシです。
頻繁にアクセスする配列にはできるだけ固定長Vectorを使うようにしましょう。

 

計算量のオーダーに気を付ける

ここからは言語に依存しない話になります。
これは先述のパターンのうち、

・そもそもコンピューターに要求する計算量が多すぎる

パターンに対して有効です。

いくら最適化しても速くなってくれない場合、
プログラムの組み方に問題があることが多いです。

根本的なアルゴリズムを見直すことも最適化のひとつです。

計算量のオーダーというものがあります。
O(n) や O(n²) といった表記をみたことはありませんか？
これはnを増やしていった時に、計算量がどのように増加するかを表したものです。

例えば、当たり判定の例で見てみましょう。
動き回るキャラクターに対してそれぞれ当たり判定を行います。

次のような流れでプログラムを組んだとします。

・すべてのキャラクターに対してループ
　　・すべてのキャラクターに対してループ
　　　　・ループで取り出した2体を判定する
　　・ループ終了
・ループ終了

チェックの回数を見てみましょう。
キャラクターが5体のとき、5回のループの中で更に5回ループするので、
5×5で25回の判定が行われます。

10体のときはどうでしょうか。
今度は10回のループの中で更に10回ループするので、
10×10で100回の判定が行われます。

同じように100体のときは10000回、1000体の時はなんと1000000回の判定が行われます！

キャラクターの体数をn体としたときに、判定の回数は n²回となり、
このアルゴリズムのオーダーは O(n²) となります。

実はこのような判定や並べ替えのロジックは、
何も考えずに書くと O(n²) となることがほとんどです。

一般に O(n²) 以上のオーダーは、
nの増加に伴って計算量が急増するので好ましくありません。

先ほどの当たり判定のプログラムは、例えば次のように書き直すことによって
計算量のオーダーを抑えることができます。

・フィールドをマス目に分解し、配列として持っておく
・すべてのキャラクターに対してループ
　　・取り出したキャラクターを、存在しているマス目の配列に格納する
・ループ終了
・すべてのキャラクターに対してループ
　　・取り出したキャラクターの周囲のマス目を取り出す
　　・マス目の中のキャラクターに対してループ
　　　　・ループで取り出した2体を判定する
　　・ループ終了
・ループ終了

これは空間分割と呼ばれる手法で、計算量のオーダーを O(n) まで抑えることができます。

しかし、これもどんな状況にも対応できるわけではありません。
ひとつのマス目に全てのキャラクターが入っているという最悪の情況を想定した場合、
このアルゴリズムのオーダーは O(n²) となってしまいます。
そのような状況が頻繁に発生しうる場合は、別のアルゴリズムを考え直す必要があります。

このように、状況に応じて使用するアルゴリズムを適切に選ぶことが最適化には欠かせません。

幸い、アルゴリズムに関しては様々なサイトを参考にすることができます。
今のような当たり判定以外の処理でも、
怪しく思ったらいいアルゴリズムがないか調べてみましょう。
必ずあなたの役に立つはずです。

 

おわりに

さて、いろいろな最適化の方法を紹介してきましたが、重要なことは
焦らずに、しっかりと分析をして最適化を行うことです。

一つずつ、着実に手順を踏めば、きっと今よりも速いコードを書くことができます。

This entry was posted on 2013年1月28日 月曜日 at 6:29 PM and is filed under ゲーム, プログラミング. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.