#はじめに
現在、ChickenClispというSchemeライクなLisp処理系をD言語で実装しています。(これについては今後記事を書こうかなぁと考えています)
そこで、パフォーマンスの悪さがとても深刻な問題だったので高速化を行いたいと考え、まずはじめにどこがボトルネックになっているのかを調べました。
ちなみに、どれぐらいパフォーマンスが悪かったかというと、Gauche(gosh)だと竹内関数(tak)に10 5 0を引数に渡した場合、ChickenClispはその250倍ぐらい遅かったり、8-queenの探索でもそのぐらいでとにかく深刻な遅さでした。
#ボトルネックを探す
ボトルネックを探すのはDMDのビルドオプションでprofileを指定すればtrace.logとかを吐いてくれるのでdubに--build=profileを指定することでprofileをつけてビルドしてくれます。
そうするとtrace.logとtrace.defが出力されます。前者がprofileの詳細で、後者はプロファイルで出てきたシンボルの一覧です。
それで、trace.logの中を見ると、コールされた回数と時間が出てきます(それからコールあたりの処理時間も)。
それで、これが改善前のtak 10 5 0を食わせた時のtrace.log(一部抜粋)です。(見にくいのはごめんなさい)。
それで、evalとかはまぁ、仕方ない(おそらく高速化可能ですが手間がかかるので今回は無視)として
コール回数の割にめっちゃ時間食ってる一番上のorelang.Engine.Engine.__ctor()に目をつけました。
これはmodule orelang.EngineのEngineクラスのコンストラクタの呼び出しを意味します。
それで、ChickenClispではスコープの生成時にこのEngineクラスが環境を保持しているのでその複製を作っています。
そのため、関数が呼ばれたりする度にコンストラクタが呼ばれます。
で、実際何をコンストラクタでやっているのかを抜粋すると
Value[string] variables;
this() {
this.variables["+"] = new Value(cast(IOperator)(new AddOperator));
this.variables["-"] = new Value(cast(IOperator)(new SubOperator));
this.variables["*"] = new Value(cast(IOperator)(new MulOperator));
this.variables["/"] = new Value(cast(IOperator)(new DivOperator));
this.variables["%"] = new Value(cast(IOperator)(new ModOperator));
this.variables["="] = new Value(cast(IOperator)(new EqualOperator));
this.variables["<"] = new Value(cast(IOperator)(new LessOperator));
this.variables[">"] = new Value(cast(IOperator)(new GreatOperator));
this.variables["<="] = new Value(cast(IOperator)(new LEqOperator));
this.variables[">="] = new Value(cast(IOperator)(new GEqOperator));
this.variables["set"] = new Value(cast(IOperator)(new SetOperator));
this.variables["get"] = new Value(cast(IOperator)(new GetOperator));
this.variables["until"] = new Value(cast(IOperator)(new UntilOperator));
this.variables["step"] = new Value(cast(IOperator)(new StepOperator));
this.variables["if"] = new Value(cast(IOperator)(new IfOperator));
this.variables["!"] = new Value(cast(IOperator)(new NotOperator));
this.variables["not"] = this.variables["!"];
this.variables["&&"] = new Value(cast(IOperator)(new AndOperator));
this.variables["and"] = this.variables["&&"];
this.variables["||"] = new Value(cast(IOperator)(new OrOperator));
this.variables["or"] = this.variables["||"];
this.variables["print"] = new Value(cast(IOperator)(new PrintOperator));
this.variables["println"] = new Value(cast(IOperator)(new PrintlnOperator));
this.variables["def"] = new Value(cast(IOperator)(new DeffunOperator));
this.variables["while"] = new Value(cast(IOperator)(new WhileOperator));
this.variables["get-fun"] = new Value(cast(IOperator)(new GetfunOperator));
this.variables["lambda"] = new Value(cast(IOperator)(new LambdaOperator));
this.variables["map"] = new Value(cast(IOperator)(new MapOperator));
this.variables["set-idx"] = new Value(cast(IOperator)(new SetIdxOperator));
this.variables["as-iv"] = new Value(cast(IOperator)(new AsIVOperator));
this.variables["def-var"] = new Value(cast(IOperator)(new DefvarOperator));
this.variables["seq"] = new Value(cast(IOperator)(new SeqOperator));
this.variables["fold"] = new Value(cast(IOperator)(new FoldOperator));
this.variables["length"] = new Value(cast(IOperator)(new LengthOperator));
this.variables["car"] = new Value(cast(IOperator)(new CarOperator));
this.variables["cdr"] = new Value(cast(IOperator)(new CdrOperator));
this.variables["load"] = new Value(cast(IOperator)(new LoadOperator));
this.variables["cond"] = new Value(cast(IOperator)(new CondOperator));
this.variables["alias"] = new Value(cast(IOperator)(new AliasOperator));
this.variables["let"] = new Value(cast(IOperator)(new LetOperator));
this.variables["for-each"] = new Value(cast(IOperator)(new ForeachOperator));
this.variables["remove"] = new Value(cast(IOperator)(new RemoveOperator));
this.variables["cons"] = new Value(cast(IOperator)(new ConsOperator));
this.variables["when"] = new Value(cast(IOperator)(new WhenOperator));
this.variables["list?"] = new Value(cast(IOperator)(new IsListOperator));
this.variables["make-hash"] = new Value(cast(IOperator)(new MakeHashOperator));
this.variables["set-value"] = new Value(cast(IOperator)(new SetValueOperator));
this.variables["get-value"] = new Value(cast(IOperator)(new GetValueOperator));
this.variables["define"] = new Value(cast(IOperator)(new DefineOperator));
this.variables["transpile"] = new Value(cast(IOperator)(new TranspileOperator));
this.variables["eval"] = new Value(cast(IOperator)(new EvalOperator));
this.variables["string-concat"] = new Value(cast(IOperator)(new StringConcatOperator));
this.variables["string-join"] = new Value(cast(IOperator)(new StringJoinOperator));
this.variables["string-split"] = new Value(cast(IOperator)(new StringSplitOperator));
}
こんな感じで、プリミティブな関数を変数として(ChickenClispでは関数は第一級オブジェクトなので変数と区別していません)登録しています。(これ、全く同じ挙動をする関数がスコープ生成のために新たに作られる感じで非常に効率が悪いのでそもそもこの方式をなんとかしたほうがいいですけど、とりあえず今回は無視)
ここで注目したいのは次の2つです
- newによってインスタンスを生成するのはコストがかかる(メモリを確保したり、コンストラクタ内の処理に時間がかかります)
- そうやってコストを払って生成したインスタンスが実際、すべて必要なのか?((ChickenClispのコードで)その関数が呼ばれて、その値が(これはEngineの内部の話)参照されることがなかったらそのインスタンスの生成は無駄になる。)
#実際に解決する
それで、この2つの問題を同時に解決する方法は
- 連想配列の初期化を遅延する
と言うことが考えられます。
具体的にコードで書くと
T[strnig] hashmap;
//連想配列にセットする(新しい鍵について初期化する)
hashmap["abc"] = new T("def");
hashmap["foo"] = new T("bar");
hashmap["hoge"] = new T("fuga");
//中略
//この先に実際に使われたのが"abc"と"hoge"であった場合、"foo"の生成は無駄
とあった場合に、new ValueClass(arg)の呼び出しを遅延させます。
具体的には次のようなクラスを作ることで実現ができます(詳細はコードの後で説明します)。
/**
* Lazed Associative Array
*
* For instance;
* assocArray["key"] = new ValueType
* The above code creates a new instance of ValueType with some costs.
* However it likely to be a bobottleneck if the value will not used.
* Then this class provides lazed associative array, this class will not create an instance until the value become needed.
* In other words, this is sort of lazy evaluation for performance.
*/
class LazedAssocArray(T) {
/**
* Flags, indicates whether the instance of the key is already created
*/
bool[string] called;
/**
* This variable holds the instance as a value of hashmap.
*/
T[string] storage;
/**
* This variable holds the constructor calling delegate to make the instance which will be called when the isntance become needed.
*/
T delegate()[string] constructors;
alias storage this;
/**
* This function works like:
* // laa is an instance of LazedAssocArray
* laa["key"] = new T;
* with following way:
* laa.insert!("key", "new T");
*
* This function uses string-mixin for handling "new T", becase D can't allow make an alias of the expr liek `new T`
*/
void insert(string key, string value)() {
constructors[key] = mixin("delegate T () { return " ~ value ~ ";}");
called[key] = false;
}
/**
* Set the value with the key.
* This function works like:
* laa["key"] = value;
* with
* laa.set("key", value)
*/
void set(string key, T value) {
storage[key] = value;
called[key] = true;
}
/**
* Make an alias of the key
*/
void link(string alternative, string key) {
bool flag = called[key];
called[alternative] = flag;
if (flag) {
storage[alternative] = storage[key];
} else {
constructors[alternative] = constructors[key];
}
}
/**
* An overloaded function of opIndexAssing
* This function hooks: laa["key"] = value; event but this function might be no use
*/
void opIndexAssing(T value, string key) {
storage[key] = value;
called[key] = true;
}
/**
* An overloaded function of opIndex
* This function hooks: laa["key"] event.
*/
T opIndex(string key) {
if (!called[key]) {
T newT = constructors[key]();
storage[key] = newT;
called[key] = true;
return newT;
}
return storage[key];
}
}
メンバ変数は以下の三つです。
bool[string] called;
T[string] storage;
T delegate()[string] constructors;
それぞれが何を意味するかというと
- called - 与えられたkeyに対応する遅延されたインスタンス生成(コンストラクタの呼び出し)が行われたかを保持する連想配列。
- storage - 実際にkeyに対応するインスタンスを生成後(コンストラクタの呼び出し後)に保持する連想配列。
- constructors - 遅延されたインスタンス生成(コンストラクタの呼び出し)を保持する連想配列。
です。
ここで、インスタンスの生成(コンストラクタの呼び出し)を遅延する方法考えます。
結論から言うと、文字列mixin(string-mixin)を行います。
具体的なコードは上から抜粋すると
void insert(string key, string value)() {
constructors[key] = mixin("delegate T () { return " ~ value ~ ";}");
called[key] = false;
}
ここで、valueのところにインスタンスの生成(つまり、"new T"が渡されます)が入ります。
やりたいことは、new Tを遅延することです。そこで、new Tにaliasが張れたらいいんですけど、それは無理なので文字列で渡します。
それで、コンパイル時に
constructors[key] = delegate T () { return new T };
というコードを作ることで、遅延が可能です(実際のインスタンスの生成はconstructors[key]に格納されたdelegateがコールされる時に初めて行われます)。
つまり、delegateを用いてインスタンス生成を遅延させます。
それで、必要になったときは(例えばhashmap["key"]が呼ばれたとき)、以下のオーバーロードされた関数が呼び出されます。
T opIndex(string key) {
if (!called[key]) {
T newT = constructors[key]();
storage[key] = newT;
called[key] = true;
return newT;
}
return storage[key];
}
これは、called[key]によってインスタンスがすでに生成されているかを判断し、生成されてない場合はconstructors[key]に格納されているdelegateを呼び出すことでインスタンスを生成し、生成されている場合はstorageからすでに生成されたインスタンスを返します。
こうすることで、連想配列を遅延することができました。(なお、プリミティブな値が格納される場合、これは意味がないです。これはあくまでも、連想配列の値に独自のクラスを格納する場合にのみ有効です。)
うえのLazedAssocArrayを用いると初めに示したコンストラクタは次のようにすっきりします。
LazedAssocArray!Value variables;
this() {
this.variables = new LazedAssocArray!Value;
this.variables.insert!("+", q{new Value(cast(IOperator)(new AddOperator))});
this.variables.insert!("-", q{new Value(cast(IOperator)(new SubOperator))});
this.variables.insert!("*", q{new Value(cast(IOperator)(new MulOperator))});
this.variables.insert!("/", q{new Value(cast(IOperator)(new DivOperator))});
this.variables.insert!("%", q{new Value(cast(IOperator)(new ModOperator))});
this.variables.insert!("=", q{new Value(cast(IOperator)(new EqualOperator))});
this.variables.insert!("<", q{new Value(cast(IOperator)(new LessOperator))});
this.variables.insert!(">", q{new Value(cast(IOperator)(new GreatOperator))});
this.variables.insert!("<=", q{new Value(cast(IOperator)(new LEqOperator))});
this.variables.insert!(">=", q{new Value(cast(IOperator)(new GEqOperator))});
this.variables.insert!("set", q{new Value(cast(IOperator)(new SetOperator))});
this.variables.insert!("get", q{new Value(cast(IOperator)(new GetOperator))});
this.variables.insert!("until", q{new Value(cast(IOperator)(new UntilOperator))});
this.variables.insert!("step", q{new Value(cast(IOperator)(new StepOperator))});
this.variables.insert!("if", q{new Value(cast(IOperator)(new IfOperator))});
this.variables.insert!("!", q{new Value(cast(IOperator)(new NotOperator))});
this.variables.link("not", "!");
this.variables.insert!("&&", q{new Value(cast(IOperator)(new AndOperator))});
this.variables.link("and", "&&");
this.variables.insert!("||", q{new Value(cast(IOperator)(new OrOperator))});
this.variables.link("or", "||");
this.variables.insert!("print", q{new Value(cast(IOperator)(new PrintOperator))});
this.variables.insert!("println", q{new Value(cast(IOperator)(new PrintlnOperator))});
this.variables.insert!("def", q{new Value(cast(IOperator)(new DeffunOperator))});
this.variables.insert!("while", q{new Value(cast(IOperator)(new WhileOperator))});
this.variables.insert!("get-fun", q{new Value(cast(IOperator)(new GetfunOperator))});
this.variables.insert!("lambda", q{new Value(cast(IOperator)(new LambdaOperator))});
this.variables.insert!("map", q{new Value(cast(IOperator)(new MapOperator))});
this.variables.insert!("set-idx", q{new Value(cast(IOperator)(new SetIdxOperator))});
this.variables.insert!("as-iv", q{new Value(cast(IOperator)(new AsIVOperator))});
this.variables.insert!("def-var", q{new Value(cast(IOperator)(new DefvarOperator))});
this.variables.insert!("seq", q{new Value(cast(IOperator)(new SeqOperator))});
this.variables.insert!("fold", q{new Value(cast(IOperator)(new FoldOperator))});
this.variables.insert!("length", q{new Value(cast(IOperator)(new LengthOperator))});
this.variables.insert!("car", q{new Value(cast(IOperator)(new CarOperator))});
this.variables.insert!("cdr", q{new Value(cast(IOperator)(new CdrOperator))});
this.variables.insert!("load", q{new Value(cast(IOperator)(new LoadOperator))});
this.variables.insert!("cond", q{new Value(cast(IOperator)(new CondOperator))});
this.variables.insert!("alias", q{new Value(cast(IOperator)(new AliasOperator))});
this.variables.insert!("let", q{new Value(cast(IOperator)(new LetOperator))});
this.variables.insert!("for-each", q{new Value(cast(IOperator)(new ForeachOperator))});
this.variables.insert!("remove", q{new Value(cast(IOperator)(new RemoveOperator))});
this.variables.insert!("cons", q{new Value(cast(IOperator)(new ConsOperator))});
this.variables.insert!("when", q{new Value(cast(IOperator)(new WhenOperator))});
this.variables.insert!("list?", q{new Value(cast(IOperator)(new IsListOperator))});
this.variables.insert!("make-hash", q{new Value(cast(IOperator)(new MakeHashOperator))});
this.variables.insert!("set-value", q{new Value(cast(IOperator)(new SetValueOperator))});
this.variables.insert!("get-value", q{new Value(cast(IOperator)(new GetValueOperator))});
this.variables.insert!("define", q{new Value(cast(IOperator)(new DefineOperator))});
this.variables.insert!("transpile", q{new Value(cast(IOperator)(new TranspileOperator))});
this.variables.insert!("eval", q{new Value(cast(IOperator)(new EvalOperator))});
this.variables.insert!("string-concat", q{new Value(cast(IOperator)(new StringConcatOperator))});
this.variables.insert!("string-join", q{new Value(cast(IOperator)(new StringJoinOperator))});
this.variables.insert!("string-split", q{new Value(cast(IOperator)(new StringSplitOperator))});
}
#高速化の結果
で、結果どれらい早くなったのかですが, 改善前の1.4倍~2倍ほど高速化に成功しました(とはいえ、依然としてGaucheに比べるとtak 10 5 0で168倍ぐらい遅いんですけど...)。
で、今後はとりあえずこの時点でのtrace.logを参考にして(いかに貼ります)さらなる高速化を考えたいです...
