変数lookupの高速化 - Scheme VM のお勉強

いま勉強しているヒープベースの VM は、他の命令に比べて refer が重い。
実行時の変数 lookup が inner most の rib から外側に変数を線形に探索していくのが実行時間の大半を占めるからである。
僕の処理系でもこの問題を抱えている。
スタックベースの VM だとこの問題は劇的に改善されるらしいのだけど、論文ではヒープベースでもう一工夫している。

発想はとても簡単。
Scheme の変数は静的なスコープを持つので、実はコードコンパイル時にどの変数が参照されるべきかを決定できる。
なので実行時の env の中のどの value を参照すればよいのか分かるのだ。

例えば以下の内側の lambda の中の a がどちらの a を参照するかはコンパイル時点に分かる。
実行時には一番内側の value rib の1つ目の value を参照すればよい。

(lambda (a b c)
  (lambda (a)
    a))

内側から参照すべき value rib の index を x とし、value rib 内の変数の index を y とすると、実行時の environment における、(x . y) の値を参照することになる。
上記の例であれば、内側の a は (0 . 0)である。
このようにコンパイル時に全ての変数の位置を (x . y) のように指定してやれば、実行時の変数 lookup は軽くなる。

この高速化を施して以下のコードで実行時間を比べてみた。

(define code (compile '(((((lambda (a)
                             (lambda (b)
                               (lambda (c)
                                 (lambda (d)
                                   a))))
                           1)
                          2)
                         3)
                        3)
                      '()
                      '(halt)))
(time
 (let loop ((i 0))
   (if (>= i 1000000)
       i
       (begin
         (VM '() code '() '() '())
         (loop (+ i 1))))))

10% ほど速くなった。

最適化なし	最適化あり
real 17.105	real 15.423
user 17.050	user 15.400
sys 0.000	sys 0.020