Cyanのソースハックを試みる 2倍速達成

Cyanはせっかく面白いのに、現在の実装が遅すぎてまだ遊びにくいのが残念です。とくに、単純繰り返しにすごく弱い。

#1000個の数字から二乗が1になるものだけ抽出(つまり1だけ)
iota(1000).filter^(x){ x * x == 1 }

これ、自分のマシンで約8秒もかかりました。スタックマシンじゃないからといっても、Lispの評価機がそんなに遅いはずがない、というわけで、
cyan-1.0.2 - takuto_hの日記
をベースにソースをハックしてみました。

src/Cyan/Evalutor.cs の Evaluor::Run メソッド(仮想マシンの最小単位命令を回すループっぽい)になにやら怪しげな部分を発見。

while (instructions.Count > 0)
{
    insn = instructions[0];
    instructions.RemoveAt(0);
    
    //PrintState(insn);

    GetType().GetMethod(insn.Key).Invoke(this, insn.Value);
}

GetMethodしてInvokeて…、プログラムの最小単位で毎回リフレクションって、そりゃ遅くなるわけだ。enumで全オペコードを定義(enum Opcode...)して、リフレクションで書かれた部分を

switch(insn.Key)
{
    case Opcode.Push:
        Push((CyBase)insn.Values[0]);
        break;
    case Opcode.Pop:
        Pop();
        break;
    // (ry
}

こんな感じになるように作り変えてみる(インストラクションのリストの、命令名を列挙の値になるように変更する)と、なんと、8秒かかってたのが4秒ちょっと切るところまで行きました。だいぶ速くなったけど、まだまだ…。

次に怪しいのは、instructions.RemoveAt(0) あたりでしょうか。C#でList(普通の配列だよね、たしか)の先頭を取り除くというのは、1から末尾までの要素を1つづつずらす必要があるので、インデックスを進めることによって「消したことにする」か、連鎖リストにしておきたいところです。でも、生成コストとのトレードオフを考えないと、と思い、そのデータの出所を調べてみると…。

src/Cyan/Objects/CyContinuation.cs のコンストラクタの

instructions = new List<KeyValuePair<string, object[]>>(insns);

ってのがその主要な発生源でした。Cyanの継続というのは、「実行されたところ以降しか残ってない(未実行の)命令リスト」を、「コピーバックアップ」したものか。なるほどこれはシンプル。継続を使うときは、バックアップから未実行命令のリストを復元するだけ。すぐ隣には、なにやらスタックのコピーを取ってるところもありました。

って、少々重くても頻度が少なけりゃ、と思いきや、なななんと、CyContinuationって、生成回数が尋常じゃないぐらい多いんですよね。2個の整数を加算するだけで3個、3つの整数の加算で6個のCyContinuationが生成されました。つまり、1000回ループで演算子2個だと、軽く見積もって6000回CyContinuationコンストラクタを通ることになります。いや、6000回のnewが問題どころの騒ぎじゃなくて、命令リストとスタックのコピーと復元の量たるや…。

Cyanの構文はCyanのマクロや関数で定義されてて、かつ、Cyanのreturnは継続で実現されている、ということを考えると、やっぱり、継続の生成と命令リストのコピー/復元には、最適化の効果が期待できそうです。

連鎖リストのノードを次のノードに進めるような感じで命令を消化し、バックアップを取るときは現在ノードへのポインタを取るようにすればどうだろう?　スタックもコピーを取らず、どうにかポインタ切り替えにならないだろうか…。あとは、大量にnewしてもリサイクルが期待できるオブジェクトじゃないと。

って、考えたところまでで限界。どうも独自のコレクションクラスが要りそうだし、続きはそうとう暇なときに考えよう。ただ、これで確かになったのは、現バージョンのCyanの実装は、まだ出せる性能を出し切っていないってことです。ああ面白い。

うーん、末尾再帰(というか、命令リスト空状態での継続発生、か)の最適化もできそうだ。なんとなく。