私は、いくつかの「問題のある」プロパティを持つ関数型言語を実行するために、中間言語と仮想マシンに取り組んでいます。
- レキシカル名前空間 (クロージャ)
- 動的に増加するコール スタック
- 遅い整数型 (bignums)
中間言語はスタック ベースで、現在の名前空間の単純なハッシュ テーブルを使用します。どのように見えるかを理解するために、McCarthy91関数を次に示します。
# McCarthy 91: M(n) = n - 10 if n > 100 else M(M(n + 11))
.sub M
args
sto n
rcl n
float 100
gt
.if
.sub
rcl n
float 10
sub
.end
.sub
rcl n
float 11
add
list 1
rcl M
call-fast
list 1
rcl M
tail
.end
call-fast
.end
「大きなループ」は簡単です。
- 命令をフェッチする
- 命令ポインタ（またはプログラムカウンタ）をインクリメントします
- 命令を評価する
に加えてsto、rcl関数呼び出しには 3 つの命令があります。
call名前空間をコピー (ディープ コピー) し、命令ポインタをコール スタックにプッシュします。call-fastは同じですが、浅いコピーのみを作成しますtail基本的には「goto」です
実装は実に簡単です。より良いアイデアを提供するために、「大きなループ」の途中からのランダムなスニペットを次に示します (更新、以下を参照)。
} else if inst == 2 /* STO */ {
local[data] = stack[len(stack) - 1]
if code[ip + 1][0] != 3 {
stack = stack[:len(stack) - 1]
} else {
ip++
}
} else if inst == 3 /* RCL */ {
stack = append(stack, local[data])
} else if inst == 12 /* .END */ {
outer = outer[:len(outer) - 1]
ip = calls[len(calls) - 1]
calls = calls[:len(calls) - 1]
} else if inst == 20 /* CALL */ {
calls = append(calls, ip)
cp := make(Local, len(local))
copy(cp, local)
outer = append(outer, &cp)
x := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
ip = x.(int)
} else if inst == 21 /* TAIL */ {
x := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
ip = x.(int)
問題は次のとおりです。McCarthy91 を -10000 の値で 16 回呼び出すと、ほとんど違いはありませんが、3 秒かかります (ディープコピーを最適化した後、1 秒近く追加されます)。
私の質問は、この種の言語の解釈を最適化するための一般的な手法は何ですか? ぶら下がっている果物はありますか？
リストにスライス (引数、さまざまなスタック、名前空間のマップのスライスなど) を使用したので、この種のことをあらゆる場所で行いますcall_stack[:len(call_stack) - 1]。今のところ、どのコードがこのプログラムを遅くしているのか、まったくわかりません。私は主に一般的な最適化戦略を探していますが、ヒントをいただければ幸いです。
余談:
呼び出し規則を回避することで、実行時間をかなり短縮できます。命令はスタックのlist <n>n 個の引数をフェッチし、それらのリストをスタックにプッシュし、args命令はそのリストからポップして、各項目をスタックにプッシュします。これは、第一に、関数が正しい数の引数で呼び出されていることを確認し、第二に、可変引数リスト (つまり ) で関数を呼び出せるようにするため(defun f x:xs)です。それを削除し、sto* <x>を置き換える命令を追加するとsto <x>; rcl <x>、2 秒に短縮できます。まだ華麗ではありません、とにかくこれlist/argsビジネスを持たなければなりません. :)
もう1つ（これは私が知っている長い質問です、申し訳ありません）：
pprof を使用してプログラムをプロファイリングしても、ほとんどわかりませんでした (明らかでない場合に備えて、私は Go を初めて使用します) :-)。これらは、pprof によって報告された上位 3 項目です。
16 6.1% 6.1% 16 6.1% sweep pkg/runtime/mgc0.c:745
9 3.4% 9.5% 9 3.4% fmt.(*fmt).fmt_qc pkg/fmt/format.go:323
4 1.5% 13.0% 4 1.5% fmt.(*fmt).integer pkg/fmt/format.go:248
これまでに行った変更は次のとおりです。
- ハッシュテーブルを削除しました。代わりに、配列へのポインターだけを渡すようになり、必要な場合にのみローカル スコープを効率的にコピーします。
- 命令名を整数のオペコードに置き換えました。以前は、文字列の比較にかなりの時間を費やしていました。
- 命令はなくなりました
call-fast(他の変更の後、スピードアップはもはや測定できませんでした) - 「int」、「float」、および「str」命令を使用する代わりに、1 つだけ使用
evalし、コンパイル時に定数を評価します (つまり、バイトコードのコンパイル)。次にeval、それらへの参照をプッシュします。 - のセマンティクスを変更した後
.if、これらの疑似関数を取り除くことができました。と同様の暗黙の gotos とブロック セマンティクスを使用して、今.ifでは 、.elseandです。(いくつかのサンプルコード).endif.sub
レクサー、パーサー、およびバイトコード コンパイラを実装した後、速度は少し低下しましたが、それほどではありませんでした。MC(-10000) を 16 回計算すると、1.2 秒で 420 万のバイトコード命令が評価されます。生成されるコードのサンプルを次に示します(このから)。