SICP 読み (179) 4.1.7 構文解析を実行から分離する

問題 4.24

とりあえず、以下の手続きをでっち上げて time なソレを測定。

(let f ((i 0))
  (if ((lambda (x) (> x 100000)) i)
      '()
      (f (+ i 1))))

で、わし製評価器に吸わせてみたらびっくり仰天。

$ time gosh 4.1.4/4.1.4.scm <test/2/test.scm >/dev/null

real    0m16.565s
user    0m8.609s
sys     0m0.012s
$ time gosh 4.1.7/4.1.7.scm <test/2/test.scm >/dev/null

real    0m10.469s
user    0m5.164s
sys     0m0.024s
$ time gosh test/2/test.scm >/dev/null

real    0m0.529s
user    0m0.040s
sys     0m0.004s
$ time gosh test/2/test.scm >/dev/null

real    0m0.038s
user    0m0.032s
sys     0m0.008s
$ time gosh test/2/test.scm >/dev/null

real    0m0.042s
user    0m0.036s
sys     0m0.004s
$

16 秒って ... (絶句
最後の三つは gosh に同じ手続きを吸わせてみたものなんですが、最初の 0.5 秒と以降の 0.04 秒くらいのソレは何かヒミツがあるのだろうか。
ってそりゃ良いとして analyze 版は 2/3 近くのナニで速度改善されているのは分かるな。
とりあえず、上記の手続きをそれぞれの評価器がどのように処理しているかを確認。

analyze 版

let 式は let->combination で変換された後に analyze される。名前付き let なので以下の式に変換。

(begin
  (define f
    (lambda (i)
      (if ((lambda (x) (> x 100000)) i)
	  '()
	  (f (+ i 1)))))
  (f 0))

上記の式は analyze によって cdr が analyze-sequence に渡されて手続きが戻る。analyze-sequence ではリストの要素が一つづつ analyze されてから一つの手続きにまとめられるんですが、それぞれどのように解析されるのか。
まず最初の define 式。analyze-definition においては、lambda 式が analyze される。analyze-lambda において lambda 式の手続き部分 (上記で言えば if で始まる式) が analyze される、と。
analyze-if においては cadr、caddr、cadddr なそれぞれの式が事前に全部 analyze される。まず条件式 (cadr 部) は手続き認定されるので、analyze-application において手続き部分と引数部分がそれぞれ analyze された上で手続きが戻る形になる。
この先は略しますが、全てを掘り下げて analyze されて、環境を渡せば変数の束縛を解決してしなければならない仕事をするだけ、な状態になる。
構文の解析を全部ヤッツケてしまうので、それなりのコストはかかりますが、実行時にはテキストにある通り、同じ手続きを解析する手間が省けるので無駄が無い。もしかすると上記の手続き的に言えば、繰り返しの回数が少ない場合には time なソレが逆転する事もあり得るかもしれない。このあたりが実験なソレでしょうか。

もう一つのソレの前に

と、いう事で繰り返し回数が少いソレで試験してみた。まず 100 回繰り返し。

$ time gosh 4.1.4/4.1.4.scm <test/2/test.scm >/dev/null

real    0m0.587s
user    0m0.048s
sys     0m0.016s
$ time gosh 4.1.7/4.1.7.scm <test/2/test.scm >/dev/null

real    0m0.088s
user    0m0.056s
sys     0m0.004s
$

あら。それでも相当違いがあるな。次は 10 回。

$ time gosh 4.1.4/4.1.4.scm <test/2/test.scm >/dev/null

real    0m0.055s
user    0m0.044s
sys     0m0.012s
$ time gosh 4.1.7/4.1.7.scm <test/2/test.scm >/dev/null

real    0m0.056s
user    0m0.040s
sys     0m0.016s
$

さすがにここまで値が小さいと、です。1000 回でも試してみるか。

$ time gosh 4.1.4/4.1.4.scm <test/2/test.scm >/dev/null

real    0m0.132s
user    0m0.124s
sys     0m0.004s
$ time gosh 4.1.7/4.1.7.scm <test/2/test.scm >/dev/null

real    0m0.104s
user    0m0.088s
sys     0m0.012s
$

あらら。それほど変化は無いな。もっかい 100 回繰り返し。

$ time gosh 4.1.4/4.1.4.scm <test/2/test.scm >/dev/null

real    0m0.065s
user    0m0.052s
sys     0m0.008s
$ time gosh 4.1.7/4.1.7.scm <test/2/test.scm >/dev/null

real    0m0.060s
user    0m0.052s
sys     0m0.008s
$

げ。やっぱ gosh は何かの形で手続きをキャッシュしてるのかなぁ。このまま 10000 回繰り返しにしてみると以下。

$ time gosh 4.1.4/4.1.4.scm <test/2/test.scm >/dev/null

real    0m0.800s
user    0m0.788s
sys     0m0.008s
$ time gosh 4.1.7/4.1.7.scm <test/2/test.scm >/dev/null

real    0m0.498s
user    0m0.476s
sys     0m0.020s
$

次は 100000 です。

$ time gosh 4.1.4/4.1.4.scm <test/2/test.scm >/dev/null

real    0m7.514s
user    0m7.456s
sys     0m0.044s
$ time gosh 4.1.7/4.1.7.scm <test/2/test.scm >/dev/null

real    0m4.499s
user    0m4.432s
sys     0m0.036s
$

先に構文解析しようがいっしょくただろうが、やる事は同じなので件数が少なければ処理時間がさほど変わりはないだろうな、というのは分かる。あとは最初の版でどの程度ムダな事をしているか、を確認しないと上記の差をナニするのは無理だな。

このまま解析は継続しますが、途中でぶっ倒れる可能性が高いんでとりあえずエントリ投入。

4.1.4 な版の確認

ある意味こっちの方が大変かも。analyze なナニは途中で止めましたが、こっちはそうはいかない予感。評価する手続きを再度以下に。

(let f ((i 0))
  (if ((lambda (x) (> x 100000)) i)
      '()
      (f (+ i 1))))

あ、これが begin で始まる式に変換されるまでは同じなのか。(とほほ
変換された式の cdr 部は eval-sequence に渡されて一つづつ eval される、と。ワケワカになりそうなんで eval-sequence に渡される式を以下に。

((define f
   (lambda (i)
     (if ((lambda (x) (> x 100000)) i)
	 '()
	 (f (+ i 1)))))
 (f 0))

まず最初の式は define-variable! が呼び出される。lambda 式はどこまで解析されるのか、というと以下だはず。

'(procedure (i) ((if ((lambda (x) (> x 100000)) i) '() (f (+ i 1)))))

ここから先は apply で解析、という事か。逆に言えば、f が実行される度に if 以下が eval されてしまう、という事ですか。実際には (f 0) が apply される時に eval-sequence で if な式が eval されるはず。
て事は、eval-if で上記の if 式が 100000 回評価 (ってか解析含む) される事になるとゆー事ですか。else なブロックの (f (+ i 1)) は analyze 版とさほどの違いは無いように感じる。先入観でモノ言っちゃだめかなぁ。やっぱ条件式の解析と評価を一緒に、とゆーのは大変そげ。

条件式を eval
手続き認定
lambda を eval して、引数も eval して、apply に渡す
lambda を eval したら procedure が戻るんですが、渡された apply でその中身が解析される
apply に渡す前に eval したら > は primitive な手続き
x は i に束縛。i は f の引数の値で束縛。

わ。だんだん解析が雑になってるな。別途きちんとヤリます。(を