SECDV Schemeの実装 - 意外に遅い問題と小手先の最適化

nmosh

というわけでGCヒープも一通り実装が完了し、そろそろ他の言語への移植を考えるフェーズに移ってきた。大体ネイティブ実行、つまり普通のSchemeインタプリタで実行した速度の100倍程度の遅さ(= インタプリタの実行速度ギャップ20倍 x PCと実機のIPC比5倍)なら実ゲームを載せて検証できるのでそれくらいの性能を目標にしている。
(コアになるゲームロジック -- いわゆる当たり判定等フレーム単位の処理が必要なもの -- はSchemeではなく専用のVMを使う予定で、Schemeで書かれるのはシーンのロード処理やイベント用のスクリプトのみ。このような分割を行なわないと特に携帯機では処理量的に厳しい。)
...で、いわゆるマイクロベンチマークでは比較的余裕でこれを達成していたのだけど、ちょっと複雑なSchemeコードを実行するとなんと0.4秒で終わる処理がSECDV VMだと2分(それもGC等を行わない状態で)という300倍もの速度差が付いてしまったのでちょっと最適化を考えることにした。

プロファイルの採取

yuniの重要な特徴は複数のScheme処理系で同じコードが走ることなので、とりあえず今回はGaucheとChez Schemeのプロファイリング機能を使う。つまり、

  • Gaucheのプロファイラで大量に呼ばれている手続きを特定する - Gaucheのプロファイラは手続き単位の呼び出し回数を直ぐに見ることができる
  • Chezのプロファイラでホットスポットを特定する - Chezのプロファイラはカバレッジツールのように基本ブロック単位での実行回数を追跡することができる

Chezのプロファイラはコードから呼び出して使う必要があるが、単にloadすれば良いだけなので簡単。

(import (chezscheme))

(parameterize ((compile-profile 'source)
               (command-line (list "-PROG" "vmbench.sps")))
              (load "_launcher.sps"))

(profile-dump-html)

loadするコードのcommand-lineはparameterizeで変更できる。

観察と最適化

今回のベンチマークは、"Schemeで書かれたS式リーダを使って実プログラムを3回readする"というもの。当然一瞬で終わることを期待している(し、実際ネイティブでは1秒未満で終わる)。
まず、最初に目を引くのは、VM命令の実行数よりもヒープ操作が多いという点。

Name                                                calls  call(ms) samples
---------------------------------------------------+------+-------+-----------
object?                                            132888717  0.0000     0(  0%)
object-tag                                         106132674  0.0000     0(  0%)
(vmcore-new cycle)                                 87540015  0.0000     0(  0%)
object-datum                                       64302819 0.0000 0( 0%)
- snip -
real    1m55.139s
user    2m5.890s
sys     0m1.936s

VM命令の実行数はcycle手続きの実行数に対応する。この場合は87540015命令の実行に2分掛かっていることになる。先に結論すると、既に0.7MIPS(約8700万命令/2分 = 0.725M命令/sec)出ていることになるので、VMの性能という意味では既に十分なパフォーマンスが出ていて、VMコンパイラで最適化をサポートするか、ランタイムライブラリを最適化することが必要と言える。ただ、開発のイテレーション的にはVM自体の最適化も無意味ではないので、最適化をしてみる。
object-tagはヒープオブジェクトの種別の取得、object-datumはヒープオブジェクトのホストSchemeへの変換を行う手続きで、これらの処理はMOV命令等大半の命令では不要であることを考えると命令ミックス的におかしいと言える。
というわけでChezのプロファイラ出力を眺めてみると、

ホストSchemeの文字オブジェクトをターゲットに戻す処理が突出して多いことがわかる(紫色)。適当にbreakを入れて確認したところ、この処理は定数ロードに使用しているLDI命令の実装に由来することがわかったので、LDI命令のたびにターゲット→ホスト変換をしていたのを、実行前にまとめて行うように変更してみた。

更に、分岐命令BRVでターゲット→ホスト変換を毎回行っていたのを、ターゲットのFalseかどうかを直接判定するだけにした。

ここまでの最適化で実行時間は1m40.161sになった(87%)。10%の改善はまぁまぁの効果と言える。
... が、CALL/RET命令のそれぞれの実装でクロージャを確保していたのを修正したら1m9.489s(60%)になった。

このまま1分は切れるくらいまでは最適化できるのではないだろうか。まぁ先に書いた通りこれ以上高速化しても仕方ないのでやらないけど。

方針の再検討

とりあえず、現状の方針ではVMコンパイラ/ランタイム実装が頭悪すぎと結論して良さそうなので、もう少し真面目に実行負荷見積りを出す必要があるのではないかといえる。
方針は2通り考えられて:

  • ラインタイムを既存のScheme上で(SECDV VMを使わずに)直接動作させて、プロファイルを取る
  • SECDV VMに真面目なプロファイラを実装する

後者かな。。もっとドラスティックな案としては、VM構成を単純に捨ててコンパイラ前提の方針に修正することか。。
現状では、85359803命令の実行(cycle)に対して25162773フレームが生成されており、約3命令に1度フレームが生成されている(= letやlambda等変数のbindが発生している)ことになる。

インライン化や定数畳み込み等を真面目に実装してVM負荷を減らすことがかなり重要そうなのはわかる。ただこれらを真面目に実装するのは避けたいので、どうにかホスト言語にこの負担を押し付ける方法は無いものか。。
例えば、必ずleaf関数になることが保証されているプリミティブを呼び出すときは、そのパラメタを格納するためのフレームを新規に確保する必要は無い(= 使いまわしができる)。このような小手先の最適化の効果を予測するために、コードの性質を良く計測する必要がある。