toy VM 続き

scheme

gauche toy VM はまだ遠いので、SECD machine の続き。
LispMe の VM は SECD Machine をちょっと拡張したものになっている。特に理解しておきたいのが、シンプルに書けるという continuation(6.7,7.5) と、tail call(6.6, 7.4)。
まず末尾呼び出しの最適化。TAPC という命令と、コンパイラが必要。そのまえに、LispMe ではクロージャの表現を拡張している(6.5)。これはエラーチェックのためのようなので、当面は無視する。

  • LispMe: An Implementation of Scheme for the Palm Pilot 個人的には 3imp よりずっと分かりやすい気がする。

テスト中。

gosh> (time (secd 's 'e '(DUM NIL
                              LDF
                              (LDC 0 LD (1 . 1) =
                                   SELR
                                   (LD (1 . 2) RTN)
                                   (NIL LD (1 . 2) LD (1 . 1) * CONS LDC 1 LD (1 . 1) - CONS LD (2 . 1) TAPC))
                              CONS LDF (NIL LDC 1 CONS LDC 20 CONS LD (1 . 1) TAPC) RAP) 'd))
;(time (secd 's 'e '(DUM NIL LDF (LDC 0 LD (1 . 1) = SELR (LD (1 . 2) RT ...
; real   0.009
; user   0.010
; sys    0.000
((2432902008176640000 . s) e () d)
stop

プロファイルを取ろう

gauche はまだ実験的とあるが組み込みプロファイラを持っている。プロファイラAPIを使うと対話環境でプロファイルを取得できる。
とりあえずこんなマクロを定義して、

(define-macro (with-profiler . body)
  (let1 result (gensym)
    `(begin
       (profiler-reset)
       (profiler-start)
       (let1 ,result ,@body
         (profiler-show)
         (print ,result)))))

プロファイルを取ってみた。まずは gauche の普通の fib 。

gosh> (with-profiler
       (letrec ((fib (lambda (n)
                             (if (< n 2)
                                 n
                                 (+ (fib (- n 1)) (fib (- n 2)))))))
               (fib 20)))
Profiler statistics (total 1 samples, 0.01 seconds)
                                                    num    time/    total
Name                                                calls  call(ms) samples
---------------------------------------------------+------+-------+-----------
fib                                                  21891  0.0005     1(100%)
undefined?                                               3  0.0000     0(  0%)
profiler-show                                            1  0.0000     0(  0%)
profiler-raw-result                                      1  0.0000     0(  0%)
profiler-get-result                                      1  0.0000     0(  0%)
6765
#<undef>

そして secd machine 版。

gosh> (with-profiler
       (run '(letrec ((fib (lambda (n)
                             (if (< n 2)
                                 n
                                 (+ (fib (- n 1)) (fib (- n 2)))))))
               (fib 20))))
Profiler statistics (total 358 samples, 3.58 seconds)
                                                    num    time/    total
Name                                                calls  call(ms) samples
---------------------------------------------------+------+-------+-----------
secd                                                306480  0.0095   291( 81%)
equal?                                             2046961  0.0003    54( 15%)
(secd G719)                                          21891  0.0032     7(  2%)
list-ref                                            153236  0.0003     4(  1%)
locate                                               76618  0.0003     2(  1%)
number?                                                 27  0.0000     0(  0%)
compile                                                 21  0.0000     0(  0%)
省略

気付いたこと。

  • あくまで secd 関数が呼ばれた回数しか分からない。LDF (load function) の呼ばれた回数を数えてもよい。（その先はプロファイラ付き vm だろうか。）
  • equal? は match のマクロ展開後に出てくるもの。util.match はシンボルとの比較でも、必ず (if (equal? (caaddr G636) 'CAR) ...) というような形で equal? を使うようだ。eq? で比較するようにすれば少し効率的になるかもしれない。
  • TAPC を用いると少し secd の呼び出し回数が減る。
  • 遅い。中間層一つで１０倍遅くなる（と誰かが書いていたと思うのだが出典がみつからず。）としても、遅すぎる気がする。せめて１００倍遅いくらいにしたい。
  • 今思いついたが最適化オプションをオフにしたら差が縮むかもしれない。