軽量 let 問題 - Scheme VM を書く
何が問題か？
- 最適化が行き詰まっている
- どこが？
- inline 展開する手続きに副作用がある場合を考えるとうまくいかなそう
- より具体的には、let1 を使って展開しないとまずそう
- しかしその場合、自分の処理系では let1 は手続き呼び出しに変換されるので最適化の意味がなくなってしまう。
- (例) (a 1) => (let1 x 1 aのbody) => ((lambda (x) aのbody) 1)
- lookupの手間は省けるが、その分 closure 作成のコストがかかってしまう
そもそも inline 展開で期待されるメリットは？
以下のコストを減らすことが出来る
- クロージャ作成
- Frame作成/削除
- 手続きの lookup
どのコストも何万回と手続きが呼ばれる場合は大きなコストになる。
おそらく上に並べた順でコストが高い。さらにクロージャ作成に至ってはヒープにクロージャを作成するのでメモリやGC的にもうれしくない。
思っていることを自動書記
- 軽量 let と lambda 呼び出しを区別しよう
- free variable を持たない let はとても軽量に実現できるはずだ
- 他の処理系の let の実装を見てみるのはどうか？
- クロージャをスタックに作ることが可能な場合もあるだろう
- コードを書くのを止めて論文をあさるのはどうだろうか。
Gauche の場合
gosh> (disasm (lambda () (let1 a 3 (let1 b 4 (+ a b))))) main_code (name=#f, code=0x81ee9a0, size=3, const=0, stack=0): args: #f 0 CONSTI(4) 1 NUMADDI(3) ; (+ a b) 2 RET #<undef>
当たり前だが良いコードを吐く。
free variable がある場合は
gosh> (disasm (lambda () (let1 a y (let1 b 4 (+ a b))))) main_code (name=#f, code=0x80d7048, size=6, const=1, stack=4): args: #f 0 GREF-PUSH #<identifier user#y>; y 2 LOCAL-ENV(1) ; (let ((a y)) (let1 b 4 (+ a b))) 3 LREF0 ; a 4 NUMADDI(4) ; (+ a b) 5 RET #<undef>
Gaucheの LOCAL-ENV を見てみよう。
static-link を up して探索していく例のパターン。
コンパイル時に、何個 static-link を up してベースから何番目かも分かっているということ。
gosh> (disasm (lambda () (let ([a y] [b z]) (set! a 3) a))) main_code (name=#f, code=0x80f89d8, size=9, const=2, stack=4): args: #f 0 GREF-PUSH #<identifier user#y>; y 2 LOCAL-ENV(1) ; (let ((a y) (b z)) (set! a 3) a) 3 GREF #<identifier user#z>; z 5 CONSTI(3) 6 LSET(0,0) ; a 7 LREF0 ; a 8 RET #<undef>
あまり関係ないけど Gauche に負けた気がしたこの結果。
gosh> (disasm (lambda ()(let1 a 3 (let1 b 3 (let1 c 3 (let1 d 3 (let1 e 3 (let1 f 3 (let1 g 3 (let1 h 3 (let1 i 3 (let1 j 3 (let1 k 3 (let1 l 3 (let1 m 3 (let1 n 3 (+ a b c d e f g h i j k l m n))))))))))))))))) main_code (name=#f, code=0x8143e00, size=15, const=0, stack=0): args: #f 0 CONSTI(3) 1 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 2 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 3 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 4 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 5 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 6 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 7 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 8 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 9 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 10 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 11 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 12 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 13 NUMADDI(3) ; (+ a b c d e f g h i j k l m n) 14 RET #<undef>
さて？
3imp では static link を使う手法を止めて display closure を導入したのだった。
display closure を使えば static-link をたどるコストを抑えることが出来る。また static-chain をスタックにおくことも必要なくなる。
ということで static-link の手法にそのまま戻るのはあまりうれしくない気がする。
3imp の 4.7.2 Direct Function Invocations を読み返そう。
Rather than
forcing the creation of a closure and call frame, the compiler can generate code to
place these local variables into stack locations within the call frame. The compiler
does this either by saving space in the call frame or by extending the call frame
as needed.
In Algol 60 or C this saves the allocation of a call frame on the stack. In
Scheme, this saves collecting the values of the free variables of the directly-applied
lambda expression and the allocation required to create the closure object.
いわゆるC言語のローカル変数がスタック上に配置されるのと同じだよと。とてもよく分かるが display closure との関係が分からないのでノートに描いてみよう。
2枚ほど絵を描いたら分かった。let はその場にあるかのようにコンパイルされるので、free variable への参照はすでに解決済みなのだ。
(begin 3 (let1 a 3 (+ a x)) 2)
この begin は外側の display closure の body の一部であるから free variable である x は refer_free 0 でアクセス出来る。って自分にしか分からない説明だな。
まずは簡単な let1 から。コンパイルと参照に必要な構造を列挙していこう。
- local env レジスタ
- コンパイル時に locals 引数
- compile-refer で対応
- ENTER
- local env を作る
- LET_REFER_LOCAL(n, m)
- n 個 local env を up し、m番目の引数参照する
- LEAVE
- local env レジスタを一つ上のものに更新する。
さて stack-vm35.scm を作るか。（大規模な変更が35回あったということ）。
