BeInteractive! [BeInteractive!@Blog::ループの最適化]

2004年10月15日

ループの最適化

今日は久々にマジメなActionScriptのオハナシです。
ActionScriptというのは基本的に計算が遅い部類に入ります。この計算の遅さというのはなかなかネックなものです。
なので、ループひとつとっても少しでも処理を早く終わらせることができるなら是非最適化しておきたいものです。
「そんなちょっとの時間なんて大した問題じゃないだろ。それよりもっと大事な事が(ry」
という人もいるかもしれませんが、リアルタイム性を求められるゲームなんかにおいては、毎フレームの処理に1nsecも無駄に時間を食わせたくないわけです。
(まあ、確かにプログラムの作りが悪いとかそれ以前の問題な場合もあるわけですが．．．)
そこで、今回はFlashのループ処理についてちょっと突っ込んで考えて見ましょう。

尚、今回の記事の元ネタはDGCAなどで有名なSYNさんのサイトの中の、

ループの最適化 [とってもごはん]

です。
あ、まだ読んだことが無い人は先に読まないでおいてください。
上のページはC++で書かれていますので、AS2.0に置き換えて考えて見ます。

まずは、何も最適化されていない(というか酷い)プログラムを示します。
太字の部分、3つの問題点が分かりますか？

\Sample1\CalcClass.as

class Sample1.CalcClass
{
	private var _a_Array:Array;
	private var _nCounter:Number;
	private var _nLength:Number = 1000;
	
	function CalcClass ()
	{
		_a_Array = new Array(_nLength);
	}
	
	function SetValue (nNum:Number) : Void
	{
	
		for(_nCounter=0; _nCounter<_nLength; _nCounter++)
		{
			_a_Array[_nCounter] = nNum;
		}
	
	}
}

Main.as (速度計測用)

import Sample1.*

var myCalcClass:CalcClass = new CalcClass();

var nTime:Number = getTimer();
for(var i:Number=0; i<100; i++)
{
	myCalcClass.SetValue(i);
}
trace('処理時間：'+(getTimer()-nTime)+'msec');

空の .fla ファイルを作り、

#include "Main.as"

を1フレーム目に記述して実行します。
尚、CalcClass::SetValue(Number) メソッドは、Numberで指定された値で配列全体を初期化するものです。

問題点1
多くの方は既に気づいていると思いまが、まずは for ループのカウンタです。
こんな所にメンバ変数なんて使うのは言語道断です。

問題点2
次に注目すべきは、 for ループの継続条件式です。
_nLengthというメンバ変数が使われていますが、これもローカル変数にすべきです。

これが上記ふたつの問題点を修正して最適化したものです。
しかし、実はまだあとひとつ問題点を残しています。分かりますか？
\Sample2\CalcClass.as (Main.asのimportを変更すればこちらが実行できます)

class Sample2.CalcClass
{
	private var _a_Array:Array;
	private var _nLength:Number = 1000;
	
	function CalcClass ()
	{
		_a_Array = new Array(_nLength);
	}
	
	function SetValue (nNum:Number) : Void
	{
		var nLength:Number = _nLength;
		for(var i:Number=0; i<nLength; i++)
		{
			_a_Array[i] = nNum;
		}
	}
}

問題点3
さて、気付きましたか？注目すべきは _a_Array です。
実は、これもローカル変数に置き換えた方がより早く実行できます。
ASでは、配列を代入する場合、自動で参照が代入されるので、次のように最適化できます。

\Sample3\CalcClass.as

class Sample3.CalcClass
{
	private var _a_Array:Array;
	private var _nLength:Number = 1000;
	
	function CalcClass ()
	{
		_a_Array = new Array(_nLength);
	}
	
	function SetValue (nNum:Number) : Void
	{
		var nLength:Number = _nLength;
		var a_Array:Array = _a_Array;
		for(var i:Number=0; i<nLength; i++)
		{
			a_Array[i] = nNum;
		}
	}
}

では、この最適化によってどれほどの効果があるのでしょうか。
実際に計4回試した結果を以下に示します。
(FlashMX2004Pro/WinXPProSP2/Pen4/Mem1G)

Sample1 : 395msec / 391msec / 390msec / 390msec
Sample2 : 178msec / 182msec / 178msec / 181msec
Sample3 : 145msec / 145msec / 150msec / 155msec

違いは歴然です。
Sample1とSample3では2倍以上差が出ています。
これは決して野放しにしておける問題ではないですね。

では、何故 Sample1 はこれほどまでに遅いのでしょうか(また、最適化がかかってSample3のようにならないのでしょうか)。
答えは簡単です。メンバ変数がループ内の処理で書き換えられて、条件が変わる可能性があるからです。Flashのコンパイラはこの辺りをちゃんと考慮していたわけです。
実際に生成されるバイトコードを見比べてみると、違いは一目瞭然です。
Sample1、SetValueのバイトコード (某Decompilerで生成)

	// register2に引数nNumの値が入っています
	_push register1 "_nCounter" 0
	_setMember
#43	_push register1 "_nCounter"
	_getMember
	_push register1 "_nLength"
	_getMember
	_less2
	_not
	_if true goto #61
	_push register1 "_a_Array"
	_getMember
	_push register1 "_nCounter"
	_getMember
	_push register2
	_setMember
	_push register1 "_nCounter" register1 "_nCounter"
	_getMember
	_increment
	_setMember
	_jump to #43
#61	_setMember

Sample3、SetValueのバイトコード

	// register5に引数nNumの値が入っています
	_push register1 "_nLength"
	_getMember
	_storeRegister 3
	_pop
	_push register1 "_a_Array"
	_getMember
	_storeRegister 4
	_pop
	_push 0
	_storeRegister 2
	_pop
#52	_push register2 register3
	_less2
	_not
	_if true goto #63
	_push register4 register2 register5
	_setMember
	_push register2
	_increment
	_storeRegister 2
	_pop
	_jump to #52
#63	_setMember

Sample1では無駄にGetMember、SetMemberを呼んでいる分オーバーヘッドが大きく、また、実際にループする部分のステップも多いことが分かると思います。
Sample3ではそのような無駄が全部なくなっています。

さて、ループの最適化についてご理解いただけたでしょうか。是非プログラム製作に役立ててください。
ただ、忘れてはならないのは冒頭で紹介したページの筆者SYNさんが考察で述べている通り、大切なのはこれらの問題を自分で見つけられるようになることだということです。
Flashはswfの詳細な仕様書も公開されていますし、一度はこの辺についてじっくり考えてみるといいかもしれませんね。

Posted by be_interactive at 20:56 | Comments(1) | TrackBack(0)

この記事へのトラックバックURL

http://app.blog.livedoor.jp/be_interactive/tb.cgi/8113659

この記事へのライトバック

COMMENT

あーそういえばこういうのやったけどスピードテストしなきゃわからないんだよねー。
rioの文字置換と比べたときは目測でもわかったけど。

flashだとAS以外で時間食うからねー
愛子16歳の時くらいか＜気にしたの

あとね変数名短くしてi++を++iにするとnsec単位で速くなるはずｗ

cascade 2004年10月17日 05:43

このブログについて / Description

Flashとプログラムと音ゲーと。