PSLの遅さの理由とか速度改善案とかJITの使い道とか

投稿日: 2012年6月14日 作成者: Silica

ちょっと考えの整理．頭の中では出来上がってるんですが、文字に残しておこう．

PSLの何が遅いかっていうと理由は色々あるんですが、
例えばバイトコード．

PSLのバイトコードとVMの話

バイトコードだバーチャルマシンだと名乗ってはいますが、
その実体は事実上単なる(直列化した)構文木でしかなくて、
実際の数値に対する処理からするとかなり抽象的なコードです．
言葉の上だけで説明するのは私には難しいので、
具体例(コードとか)を交えながら説明していきましょう．

ベンチマークはO(n^2)なフィボナッチ数列で取るのがメジャーみたいなので、

fib(n)
{
	if (n < 2)
		return n;
	else
		return fib(n-1) + fib(n-2);
}
print(fib(30));

こんなコード(PSLのスクリプト)を考えます．
nを返すか1を返すかは意見が分かれるところですが、まあ．
こいつのバイトコードは、PSL_DEBUGコンパイルオプションをONにして、
debug(fib)とやれば見れますが、

VARIABLE n
ARGUMENT
VARIABLE n
PUSH 2
LT
JRF 4
POP
VARIABLE n
RETURN
JR 13
POP
VARIABLE fib
VARIABLE n
PUSH 1
SUB
CALL
VARIABLE fib
VARIABLE n
PUSH 2
SUB
CALL
ADD
RETURN

あ、ついでにPSL_IF_STATEMENT_NOT_SCOPEもONです．今の標準はどっちだったか．
そうしないとifが別のスコープになってややこしくなるので．

面倒なので解説はしないが、
ジャンプ先だけはちゃんと処理しているが(因みにJRはRelative Jump、
数がおかしい様に感じるならそれは命令実行時に自動的に一つ進む為である)
他はスクリプト上の構文とバイトコード命令がほぼ1対1で対応していることが見て取れるかと思う．

まず、途中の計算は数値だろうが何だろうがvariable型を経由して行われる．
n-1は
variable n
push 1
sub
になるが、これはC++で書けば
variable n = env.getVariable(“n”);
variable temp1(1);
variable ans = n – temp1;
みたいな感じである、感じ．あくまで感覚的には．

variable型は数値だろうが文字列だろうがオブジェクトだろうが同等に扱う為に、
中で仮想関数を呼び出している．
nの中身は数値型なので、vInt::subが呼び出される、まあそれは許そう．
vInt::subは右項を数値として扱う為に相手のtoInt(勿論これも仮想関数)を呼び出す．
現実的に変数同士を処理する場合にはまあそうするでしょうよ、
でも今この時、数値から、変数クラスのインスタンスを作って、
それの仮想関数呼び出しをして、中の数値を取り出す．何たる回り道．

数値を数値として扱える様に、もっとバーチャルマシンを低レベルにする．
これは一つの道であると思います．
うまくすれば、nが数値であることも前提にしてもっとうまいこと処理出来るのではないでしょうか．

まあそこまでせずとも、対数値の処理を特殊化することは可能であります．
variableにはoperator-=(const variable &v)しかありませんが、
operator-=(int i)も持つ．各内部型が、対int用の処理を明示的に持つ．
これだけで相手の数値を得る際に仮想関数呼び出しが必要無くなるので明確に速くなります．
for (variable v = 0; v < 65536; v+=1) …;(C++です)
みたいなのを書いて計ってみれば、違いは歴然です．

これをバイトコードに反映出来る様にするだけでも効果はあるのですが、(確認済み)
明らかにオブジェクト指向の敗北なのであんまりやりたくはない．
いや敗北とかはどうでもいいんですが、コードの肥大化著しい．
汎用演算と、対int用演算、対double用演算、対string用演算…
まあ出来ればやりたくはないね．
しかも実用上で考えると定数との計算ってどの程度あるよ？
いや、STG01には結構定数あった気もするが…

スタック操作

その前に、さっきのコード、
variable n = env.getVariable(“n”);
variable temp1(1);
variable ans = n – temp1;
これ、かなり嘘．だって各命令間で値をどう受け渡す？
それはスタックを経由しますから．実際には、
variable n = env.getVariable(“n”);
env.push(n);
variable temp1(1); // まあこれはその場ではなく予め作ってはおくんですが
env.push(temp1);
variable r = env.pop();
variable l = env.pop();
variable a = l – r;
env.push(a);
割とこんなイメージ．

各命令の実行

スタック操作も重くはあるんですが、
問題は、VARIABLE/PUSH/SUB、等の各命令、その実行、
それも仮想関数呼び出しなんですね．
まあそれに関してはswitchで振り分けるパターンにしてみても速度は変わらなかったので、
どうしようもない犠牲ではあるとして、
こうやって比較してみるとどうしても回りくどいですよね．

if (n < 2)の部分を見てみましょう、
VARIABLE n
PUSH 2
LT
JRF 4
という命令ですが
1.envから名前がnの変数を受け取ってスタックにpushする
2.数値2を持つ変数をスタックにpushする
3.スタックから2つ変数をpopして、後でpopした方が先にpopした方より小さいかどうかを求め、
その結果を(0か1の数値で)持つ変数を新たに作ってpushする
4.スタックから変数をpopして、そのbool値がfalseであればジャンプする
これはひどい．

C++コードにするとこんな感じ…まあさっきと同じなのでしなくてもいいですね．
例えばここで、
3.スタックから2つ変数をpopして、後でpopした方が先にpopした方より小さいかどうかを求め、
その結果がfalseであればジャンプする
という命令を新たに作ったらば、
・仮想関数呼び出しが一つ減る．
・余計な変数の作成が一つ減る．
・スタックへの変数の出し入れが1セット減る．
減る減るずくめです．
これも実際にやってみたら明確に効果があります．
更に一歩進んで、
「スタックからpopした変数と、定数(この場合2)を比較して、
変数の方が小さくなければ(falseの時なので)
ジャンプする」
みたいなちょー具体的な命令を作ってやれば、かなりききます．
(勿論定数の値は自由に指定出来るんですよ)
fib用にこの辺を徹底してやれば、cygwinに入ってたperlとは戦える様になりました．

そしてJIT

JITの使い道としては、ガチ低レベルなコードを導き出す、という方法もあるとは思うのですが、
このバイトコードの結合をやらせるだけでもかなりの効果があるのでは、と思われるのです．
仮想関数呼び出しが減るだけでも効果があるし、
(因みに毎回仮想関数を呼び出すだけでなく、その後更に、
返ってきた値によって振り分けがある、大抵の命令は何もしないが、
returnとかcallとかした時に必要)
うまく命令を構成して解析すればstack操作の回数も減らせるであろう．
まあそっちは難しいかもしれないが、
細かい命令を繋げて一つの命令にするだけで効果があるのは間違いない．

別のアプローチ

VMやバイトコードをもっと低レベルにする、という方法はあるとは思うんです．
でも自分で低レベルなVM設計するぐらいならLLVMとかに載せるし、
そうすると…以下前回の繰り返し．

因みに命令が低レベルになってしまっても関数合成(という表現が果たして正しいのか謎だが)
とか同じノリで出来るんだろうか…
と、そう言えば名前解決の話もあったな．

名前解決

バイトコードを見て貰ったら分かる通り、ローカル変数であろうがその場で名前解決してます．
(まあこの場合はローカル変数とは限らないのであるが)
普通ローカル変数ってスタックに割り付けたりするじゃないですか．
命令列の中で、ローカル変数nを…とか言わないワケですよ．
スタックの上から何バイト目を…って感じですよ．
同じ様なことが出来たら名前解決が必要なくなる分速い．
ローカル変数って、
内部的には、スコープが持ってるlocalって連想配列のメンバでしかないんですが、
連想配列メンバじゃなくて、通常配列に入れて番号で扱えば速くね？
という思想の内部命令だけは存在して、
いや、明示的に扱う為の構文も、どこにも公開してないながら存在はするんですが、
先のスクリプトを、

fib(@0)
{
	if (@0 < 2)
		return @0;
	else
		return fib(@0-1) + fib(@0-2);
}

って書き換えてやると幾分高速に動作します．
スコープが変わるとアクセス出来ないので、
PSL_IF_STATEMENT_NOT_SCOPEがないと正しく動作しません．

ローカル変数は自動的に番号振ってこいつで置き換えてやってもいいんですが、
PSLには幾つかそれを阻害しうる変態仕様があります．
それは低レベルなVMを考える上でも問題になるでしょう．
一つは上でも言った関数合成．
PSLの関数合成はそう呼ぶのが正しいのか不明な変な機能です．詳しくはまた今度．
もう一つは外から中のローカル変数にアクセス可能なコルーチンです．
凄いね、これの為に色んなことが出来かねるよ．
yieldしなければならないことを別にしてもコルーチン周りに手を入れるのは難しい．

そうじゃなくても結局、そんなPSLだからこそ、
言語処理系というより本質的には単なるC++クラスに過ぎないPSLだからこそ、
本体とスクリプトのシームレスな連携が可能なのかもしれなくて、
低レベルなVMはどうなんだろう…とは思うワケです．

更に別のアプローチ、トランスレータ

再び先程のPSLのコードです．

fib(n)
{
	if (n < 2)
		return n;
	else
		return fib(n-1) + fib(n-2);
}

次に示すのはC++のコードです．

variable fib(variable &n)
{
	if (n < 2)
		return n;
	else
		return fib(n-1) + fib(n-2);
}

厳密に言えばoperatorオーバーロードが甘いので、ちょっと定義しておいてやる必要はあります．
いつものノリで全体を書いてみると、

#include "PSL/PSL.h"

using namespace PSL;
variable operator-(const variable &l, int r){return l.operator-(r);}
bool operator<(const variable &l, int r){return l.operator<(r);}

variable fib(variable &n)
{
	if (n < 2)
		return n;
	else
		return fib(n-1) + fib(n-2);
}

int main(void)
{
	PSLVM p;
	p.add("fib", fib);
	if (!p.LoadString("print(fib(30));"))
		p.Run();
	return 0;
}

こんな感じになりますが、当たり前にちょう速い．
まあ実際には名前解決とか結構難しいし、
C(++)には無いPSLの構文で再現が難しいものもあります．
コルーチンなんか当然に無理でしょうしね．

因みにですが、ご存知の通り、PSLではfib(int n)と書くことも出来ます．
上のC++コードをvariable fib(int n)として、
p.addFunction(“fib”, fib);とすればもーっと速くなります．
更にint fib(int n)とすれば(ry
まあそれは冗談にしてもね、というか自動的にそれを判別するのは大変にしてもね、
基本的な構文がCとそっくりだし、
スクリプト変数と同じ扱いが出来るvariableクラスが存在するというのは、
取り敢えずスクリプトで書いて必要ならC++で書き直すってことが、
凄くし易いのではないでしょうか．
PSLの遅さが不満ならC++で書き直せばいいんだー！(死

自動的なトランスレータでどこまで出来るか、ってのはどうだろうなあ…
極単純な構文でないと難しい気が…というかめんどくさい．

結局

取り敢えずSTG01が満足に動かない人が出てきたら、
または、今後私がゲームを作る上でPSLを使っていくことになるワケですが、
その際に速度が問題になったら、
または、PSLを使ってなんか凄いの作ってくれた人が、
「もうちょっと速度が出たらなー(チラッチラッ」みたいになったら考えます．

カテゴリー: コンピューターとインターネット パーマリンク

PSLの遅さの理由とか速度改善案とかJITの使い道とか への1件のフィードバック

  1. ピンバック: 別のアプローチによるVM | 生存確認兼近況報告日記

コメントを残す