プロパティへのアクセス速度の比較
id:nishiohirokazuさんの少し前のエントリー「PointとArrayで速度比較」の、
ActionScriptの配列はC的な配列じゃないからかも。逆にクラスのメンバ変数はすでに配列として確保されていそう。xとかも整数にマップされてそう。
という推測が正しいのかを調べてみました。
まずは私もプロパティへ定数を代入する式の実行速度を比較してみました。
以下は、評価対象の式の一覧になります。各式を10,000,000回ループで実行した時の実行時間を//の後ろに記載しておきます。
また、pがPoint型、aがArray型、oがObject型となります。
p.x = 1; //216ms (1) p["x"] =1; //1631ms (2) a[0] = 1; //567ms (3) a["0"] = 1; //2681ms (4) o.x = 1; //2028ms (5) o["x"] = 1; //2201ms (6) o[0] =1; //1105ms (7)
メンバ変数へのアクセスが最速でした(1)。しかし、添字を使ってアクセスするとかなり遅くなります(2)。
２番目に速かったのが数値の添字でArrayにアクセスした場合でした(3)。しかし、文字列の添字でアクセスすると遅くなりました(4)。
一番遅かったのが文字列の添字でObjectのプロパティにアクセスした場合です(6)。これに対しObject型へのアクセスでもuint型の添字でアクセスすると速くなりました(7)。
何故このような結果になったのかを理解するために、avm2overview.pdfとtamarinのソースコードを読んでみました。以下では、まずどうしてこのような結果になったのかという疑問に対する私の回答を述べます。その後、その根拠となるコードをtamarinから一部抜粋して説明します。
メンバ変数へのアクセスが速いのはなぜか？
逆に遅いのはなぜかを考えると話は簡単になります。遅いのは、すべてのアクセスはハッシュテーブルを基本として設計されているからです。
幸いなことにメンバ変数のアクセスでは、ハッシュテーブルのインターフェースを使わないで直接変数にアクセスする方法を使えるので高速になります。この仕組みは「slot」と呼ばれます。
このslotを通してメンバ変数へアクセスされるのは、添字を使わなかった場合のみです。
p.x =1;
はslotを使われますが、
p["x"] =1;
という式では、使われません。何故かというとこの式は、
var propName:String = "x"; p[propName] =1;
と書き直す余地があり、構文上propNameには任意の文字列を設定出来ます。したがって、添字を使ったプロパティへのアクセスは実行時に変更される可能性があるわけです。
それに対し、
p.x =1;
という式は、実行時にxの部分を書き換える「構文が存在しません」。そのため、コンパイルされたコードは必ずメンバ変数xを参照することが保証されます。
以上の仕組みから、同じメンバ変数であっても添字でアクセスすると実行時に変更される可能性があるとみなされslotで処理されなくなります。
この話は、AVM2のマルチネーム(Multiname)という仕様に密接に関わっており少し複雑な話なのであとで別エントリーにまとめようと思います。
クラスで定義されていないプロパティへのアクセスは辞書へのアクセスとして扱われる
これはどういうことかというと、(5)のような
o.x =1;
というクラス定義に存在しないプロパティにアクセスした場合、Objectが標準で持つハッシュテーブルへのアクセスとして処理されます。つまり、
o["x"] = 1;
と書いたとしても、本質的には変わらないということです（通過するコードに若干違いがあります）。
今回の調査したtamarinのソースコード
今回調査したコードは、主にプロパティへの代入に関わる「setproperty」オペレータの実装部分です。
プロパティへの代入が発生すると、コンパイラは
p.x =1;
というコード（pがローカル変数として存在していることを仮定）であれば、
getlocal1 pushbyte 1 setproperty :x
というバイトコードが出力されます。:xはプロパティの名前のようなもの（正確にはname indexといいます）です。
また、添字でアクセスした場合は、
p["x"] = 1;
getlocal1 pushstring "x" pushbyte 1 setproperty private,,,Main,Main,flash.display:Sprite,flash.display:DisplayObjectContainer ,flash.display:InteractiveObject,flash.display:DisplayObject,flash.events:EventDispatcher,Object,flash.display:IBitmapDrawabl e,flash.events:IEventDispatcher:null
というように値がプッシュされる前に添字がプッシュされています。setpropertyの引数がエラいことになってますが、これの詳細は不明です。
コンパイル時にプロパティ名が確定していない場合に現われるようです。
tamarinの実際のコード(core/Interpreter.cpp、907行目付近)※説明のために注釈が入っています
case OP_setproperty: { Multiname multiname; pool->parseMultiname(multiname, readU30(pc)); //(a) Atom value = *(sp--); //(b) if (!multiname.isRuntime()) //(c) { Atom obj = *(sp--); toplevel->setproperty(obj, &multiname, value, toplevel->toVTable(obj)); //(d) } else { if(multiname.isRtns() || !core->isDictionaryLookup(*sp, *(sp-1))) { //(e) sp = initMultiname(env, multiname, sp); Atom obj = *(sp--); toplevel->setproperty(obj, &multiname, value, toplevel->toVTable(obj)); } else { Atom key = *(sp--); Atom obj = *(sp--); AvmCore::atomToScriptObject(obj)->setAtomProperty(key, value); //(f) } } continue; }
(a) setpropertyに渡されたname indexに対応するMultinameオブジェクトを生成しています
(b) スタックからプロパティに代入するvalueを取得しています
(c) isRuntime()が偽になるとき、コンパイル時に定義されているプロパティへのアクセスとみなされます
(d) Toplevelのsetproperty()メソッドをコールします。
(e) 添字によるアクセスの場合、isDictionaryLookup()が真になり(f)が実行されます。
(f) Objectが標準でもつハッシュテーブにアクセスします
core/Toplevel.cpp、1059行目付近
void Toplevel::setproperty(Atom obj, Multiname* multiname, Atom value, VTable* vtable) const { Binding b = getBinding(vtable->traits, multiname); //(g) setproperty_b(obj,multiname,value,vtable,b); } void Toplevel::setproperty_b(Atom obj, Multiname* multiname, Atom value, VTable* vtable, Binding b) const { switch (b&7) { (途中省略） case BIND_VAR: //(h) { #ifdef DEBUG_EARLY_BINDING core()->console << "setproperty slot " << vtable->traits << " " << multiname->getName() << "\n"; #endif int slot = AvmCore::bindingToSlotId(b); AvmCore::atomToScriptObject(obj)->setSlotAtom(slot, coerce(value, vtable->traits->getSlotTraits(slot))); return; } （途中省略） case BIND_NONE: //(i) { #ifdef DEBUG_EARLY_BINDING core()->console << "setproperty dynamic " << vtable->traits << " " << multiname->getName() << "\n"; #endif if (AvmCore::isObject(obj)) { AvmCore::atomToScriptObject(obj)->setMultinameProperty(multiname, value); } else { // obj represents a primitive Number, Boolean, int, or String, and primitives // are sealed and final. Cannot add dynamic vars to them. // property could not be found and created. throwReferenceError(kWriteSealedError, multiname, vtable->traits); } return; }
(g) Multinameオブジェクトとvtableからbindingを取得します。bindingがプロパティの種類を決定しています。
(h) bindingが変数の場合、slotを通してvalueがセットされています。
(i) bindingが無い場合、辞書へのアクセスとして処理されます。(e)で辞書以外と判定された場合はここを通過しているようです。
※tamarinのコード内で出てくるpropertyは、AS3のプロパティとは異なります。tamarin内では、メンバ変数、メソッドなどをひっくるめてプロパティと呼んでいるみたいです（詳細不明）。
まとめ
id:nishiohirokazuさんの推測はずばり当たっていました。
ActionScriptの配列はC的な配列じゃないからかも。
添字を使ったアクセスはすべてディクショナリとして扱われています。
逆にクラスのメンバ変数はすでに配列として確保されていそう。xとかも整数にマップされてそう。
メンバ変数はインスタンス生成時にその領域を確保されており、slotという機構でアクセスが高速化されています（アルゴリズム的にはO(1))。
参照
- avm2overview.pdf
- http://wiki.libspark.org/wiki/AVM2/Overview - Sparkプロジェクトのここの日本語訳が結構参考になりました。２章のあたりを一部翻訳したので今度アップしようと思います。
