新 VM が遅くなった原因が分かった - Scheme VM を書く

scheme

昨日の続き。今日は大きな進展があったよ。

仮説1: VMループが遅くなった

実際にコンパイルとVMの時間を計測してみた。どうやら仮説は当たっているようだ。
約3倍遅くなっている。

項目 旧VM 新VM
コンパイルに要した時間 80806 89363
VMの実行に要した時間 998848 290239

次の一手

簡単なコードでの速度比較をしてみたらそこまで変わらなかった。遅い命令でもあるのかな。

仮説2: 特定命令が遅い

命令毎の実行時間をとろう。汚くても良いから。
プロファイルすることで実行時間に大きな影響を与えてしまい失敗気味。（参照：steps to phantasien プロファイラのしくみ）
特定の命令が遅いのではなさそうだ。どうも平均して一命令毎に1-2マイクロ秒遅くなっているみたい。

次の一手

さてどうするか。命令のフェッチが遅いのではないか？
旧VMでは命令に次の命令が含まれていたのですぐに到達できていたが、新VMでは pc をインクリメントして vector-ref。いやそんなに違わないな。むしろ case に落とし込めている分、新VMの方が速いはずだ。


あと考えられるのは、internal define が遅いってことぐらいだな。いまいち証拠がないが検証してみよう。

仮説3: internal define が遅い

internal define が遅いのであれば、手動で inline 展開したものと比べれば良い。検証は簡単だ。
やってみたところ当たりだった。inline展開したら4倍も速くなった。


Gauche で特定の条件で internal define を使うと、inline展開されないってことっぽい。
短い手続きだから展開されることを期待していたのだけど。
以下の next, skip, apply-native-1arg などを手動で inline 展開したら速くなった。

(define (VM codes len pc a fp c stack sp)
  (define (next n)
    (vector-ref codes (+ n pc)))
  (define (skip n)
    (+ pc n 1))
  (define (apply-native-1arg proc)
    (VM codes len (skip 0) (proc a) fp c stack sp))

深追い

自分が期待するようには inline 展開されていないのだろうと予測。
Gauche の disasm で該当部分を見てみる。

skip と next を使った場合。

それぞれの手続きが呼ばれて call/ret/push されている。

[(CONSTANT)
  (VM codes len (skip 1) (next 1) fp c stack sp)]

=>
   923 BNEQC CONSTANT, 955      ; ((CONSTANT) (VM codes len (skip 1) (next ...
   926 LREF-PUSH(2,7)           ; codes
   927 LREF-PUSH(2,6)           ; len
   928 PRE-CALL(1) 937
   930 CONSTI-PUSH(1) 
   931 LOCAL-ENV(1)             ; (lambda (n) (+ pc n 1))
   932 LREF-PUSH(3,5)           ; pc
   933 LREF0                    ; n
   934 NUMADD2                  ; (+ pc n 1)
   935 NUMADDI(1)               ; (+ pc n 1)
   936 RET 
   937 PUSH-PRE-CALL(1) 947
   939 CONSTI-PUSH(1) 
   940 LOCAL-ENV(1)             ; (lambda (n) (vector-ref codes (+ n pc)))
   941 LREF-PUSH(3,7)           ; codes
   942 LREF0-PUSH               ; n
   943 LREF(3,5)                ; pc
   944 NUMADD2                  ; (+ n pc)
   945 VEC-REF                  ; (vector-ref codes (+ n pc))
手動で inline 展開した場合

その場で計算して push。

[(CONSTANT)
  (VM codes len (+ pc 1 1) (vector-ref codes (+ 1 pc)) fp c stack sp)]

=>
   751 BNEQC CONSTANT, 772      ; ((CONSTANT) (VM codes len (+ pc 1 1) (ve ...
   754 LREF-PUSH(1,7)           ; codes
   755 LREF-PUSH(1,6)           ; len
   756 LREF(1,5)                ; pc
   757 NUMADDI(1)               ; (+ pc 1 1)
   758 NUMADDI(1)               ; (+ pc 1 1)
   759 PUSH 
   760 LREF-PUSH(1,7)           ; codes
   761 LREF(1,5)                ; pc
   762 NUMADDI(1)               ; (+ 1 pc)
   763 VEC-REF                  ; (vector-ref codes (+ 1 pc))


やはり吐かれているコードが違い、inline展開してくれないようだ。
でも、もうすこし単純な例だと期待通りに展開される。以下の2つのコードは disasm するとまったく同じコードになる。

(define (test i)
  (if (>= i 10000000)
      (print 'done)
      (test (+ i 1))))

(define (test i)
  (define (inc-and-test inc)
    (test (+ i inc)))
  (if (>= i 10000000)
      (print 'done)
      (inc-and-test 1)))

インライン展開閾値の、SMALL_LAMBDA_SIZEあたりに引っかかったかな？
結論として internal define が必ずしも inline 展開されるわけではないので、シビアなところでは使わない方が良いかもという感じかな。

追記

Gauche はドキュメントが豊富で「Gauche ユーザリファレンス: 3.6 プロファイリングとチューニング」に気をつけるべきポイントが書かれています。
一読しておいたほうが良いでしょう。

追記2

shiroさんから丁寧な解説コメントを頂きました。ありがとうごいます<(_ _)>。

『あー、それはインライン展開されてるんです。PRE-CALLというのは関数コールではなく、実際は継続フレームをpushするというインストラクションです。本来はPRE-CALLの後引数を積んで最後にCALLするんですが、ここでは引数を積んでから直接手続き本体のコードが置かれています。RETは前のPRE-CALLでつまれた継続をポップするだけです。

これを手でインライン展開した形にするのは、もうちょっと手間がかかります。ここは興味深いと思うので詳しく説明します。

applynative-1argがコンパイルされたコードの流れは、(1)codesを評価してpush (2)lenを評価してpush (3) (skip 0)を評価してpush (4) (proc a)を評価してpush (5) fpを評価してpush (6) cを評価してpush (7) stackを評価してpush (8) spを評価してpush (9) VMをTAIL-CALL、となります。

ここで、(skip 0)の実行中に継続が補足された場合、Gaucheは継続フレームのチェインをヒープに移すんですが、スタックに既につまれているcodesとlenの結果はまだ環境の一部になっていないため、これらもヒープに避難しておく必要があります。これを「作りかけの引数フレーム」と呼びます。

(skip 0)をインライン展開しない場合、codesとlenの上にskipを呼ぶための継続フレームがpushされるので、どこからどこまでが作りかけの引数フレームかはすぐにわかるのですが、ナイーブにインライン展開してしうと、作りかけの引数フレームの情報を保存しておく手段がありません。少なくとも今のGaucheでは、ダミーの継続フレームをpushしないと作りかけの引数フレームを確実に保護できないんです。(インライン展開される式が末尾式だったり、最初の引数である場合は作りかけの引数フレームは存在しないので、素直なインライン展開になります。最後のtestのインライン展開が綺麗にゆくのはそのためです)。

(skip 0)の中まで解析して、絶対に継続が補足されないことが確認できれば、ダミーの引数フレームを省くことができます。このくらいの式なら解析できますが、一般的な場合に継続が補足されないことを確認するのはわりと面倒 (少なくとも、pass2を一度終わらせないとわからない) のです。

けれどこういったところで速度が出ないのは悔しいので、そのうち見てみます。

ちなみにこういう場合の常套手段は、internal defineのかわりにlet-syntaxでローカルマクロにしちゃうことです。そしたら多分手で展開したのとほとんど同じにできるはず。

なるほど。継続捕捉のことは全く頭にありませんでした。
うーむ。奥が深い。ちなみに作りかけ引数フレームやら継続フレームの話はどのあたりから学ばれたのでしょうか。もし良い資料があればぜひ教えてください<(_ _)>

ローカルマクロでやってみます。ありがとうございました。

追記

letrec-syntax でやってみました。確かに速いです。ありがとうございます。（letrec-syntax なのはお互いに依存しているからです）

(define (VM codes len pc a fp c stack sp bp)
  (letrec-syntax ([skip (syntax-rules ()
                          ((_ n)
                           (+ pc n 1)))]