パフォーマンスチューニングについて悩むこと


ここ数日時間をかけているわりにはインタプリタのパフォーマンスチューニングが進まない。
しかもうまく進む気がしないもやもやする。これは良くない兆候だ。
Mさんに言わせればこれは知識や経験やどこまでやりこんだことがあるかといったものが足りないことに起因するようだ。
すぐそこに速くなるはずのものがあるのにもどかしい。


なので自分が知っていることやったこと悩んでいることを書いてみようと思う。

パフォーマンスチューニングとは?

パフォーマンスチューニングは以下の要素と手順からなると思う。

  • 目標
    • チューニングのための動機。
    • 要求される速度が出ていないとか。
    • 1秒以内にレスポンスを返すようにとか。
  • 調査
  • チューニング
    • 問題となるコードに手を加えて速くする。
  • 再計測
    • 目標を達成しているか?
  • 上記をくり返す。


これをベースに考えよう。

目標

大きな目標は Gauche 以上の速度を出すこと。
その前段階と実用的な(Perl 並の)速度を出すこと。
もう少し細かく言えば特定のスクリプトを実行して 100ms 以内に結果が返ること。

調査

調査の基本方針は

  • 大きく→細かく
  • 再現性のある記録をとる
大きく→細かく

インタプリタの処理を大まかに分類する。
例えば、VM初期化、コンパイル、実行 の3つに分類するなど。
そしてそれぞれの処理にかかる時間を計測する。
計測し思ったような速度が出ていない処理を3つの中から特定する。
特定できたら、その処理の中をまた大まかに分類し遅い部分を特定をするというのを繰り返す。
処理を意味のある単位に分けづらいときや、細かくなったときは二分法で適当に範囲を絞る。

再現性のある記録をとる

実行時間の計測は

などの記録をとる。

気をつけるべきは計測時のマシンの負荷とか。(Firefox が重いときに測ったみたいなことのないように)

調査のツール

ここからはインタプリタに特化した話になってしまいます。
通常チューニングと言えばプロファイルをとるためのプロファイラを使うことでしょう。

gprof

C/C++ の関数単位で実行時間が分かるプロファイラ。
gccコンパイル時に -pg をオプションをつけてコンパイルする。
そのあと実行すると gmon.out が吐かれるのでそのディレクトリで

gprof コマンド名

とやるとプロファイル結果が出力される。

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 58.33      0.98     0.98       86    11.40    14.55  scheme::VM::run(scheme::Object)
 23.21      1.37     0.39 20002847     0.00     0.00  scheme::VM::call(scheme::Object, scheme::Object)
  8.33      1.51     0.14 20005300     0.00     0.00  scheme::Object::makeRegexp(scheme::ucs4string const&, bool)
qprof

shiro さんに教えていただいた qprof 。
gprof では関数単位でしかプロファイルをとれない。
インタプリタVM ループの中で switch/case or goto/label で分岐している場合など、どこの処理が重いかが分からない。


qprof を使えばどのアドレスで遅くなっているかが分かる。

qprof -ginstruction -i 1 -o qprof.log ./hogehoge

これと例えば label のアドレスを比べればどの分岐先で(どの VM のインストラクションで)遅いかが分かる。

チューニング

実際にコードを速くするフェーズではどんな選択肢があるだろう?
以下に並べたものは上が粒度が大きく、下が粒度が細かい感じで。

  • 構造の大きな変更
    • 例えばスタックベースの VM じゃなくてレジスタベースの VM にするとか。
  • アルゴリズムの変更
    • 変数のルックアップをリニアサーチからハッシュを利用したものにするとか。
  • 実装言語の変更
  • コンパイラの最適化が聞きやすい構造に変更
    • const つけましょうとかインライン展開を期待するとか
  • 無駄なループや変数の削除など細かい改善

とまあいろいろな粒度の方法がある。


コード変更時に気をつけるべきことは一度に2つ以上の変更をしないこと。
1つの変更をしたら計測をし効果を見て、その変更が有効であるかを必ず確認する。
2つ以上の変更をしてしまうと現れた効果が何によるものかが見えにくくなる。


プロファイラがないときは?

チューニングで気をつけなければいけないことは何だろう?
1度に多くの変更をしないこと、記録をとること。

もやもやその 1

今作っているインタプリタコンパイラを内蔵しているのだけどそれは、Scheme で書かれており他の Scheme のコードと同様に VM 上で実行される。
このコンパイラが遅いときは

  • VM のプロファイルをとり性能を上げればいいのだろうか?
  • Scheme のコードとしてプロファイラをとり Scheme のコードの性能を上げればいいのだろうか。
  • それとも両方だろうか
  • そしてその具体的な手順は?

もやもやその 2

Scheme で書かれたコンパイラのプロファイルはどうやってとろうか?
プロファイラっぽいものを自作するのが良いんだろうな。
今は原始的に手続きの開始時と終了時に get-timeofday を出力してあとで集計する的なツールを自作していますがこれは後述の問題がある。

もやもやその 3

上で書いた、ツールだと細かい部分は分からない。
さらに Scheme でありがちな再帰のコードでは遅い所が分かりづらくストレスがたまる。

もやもやその 4

ついつい勘に頼っていいかげんな対応をして失敗するというのを繰りかえしてしまう。
自分がやっていることに自信がないからだろう。

次の一手は?

もやもやを書いてみたら多少冷静になれてすっきりした。
さらに頼りになる Gaku さんがいろいろとアドバイスをくれて付き合ってくれるようになったので次の方針も決まってきた。

以下の計測をすることに

さてがんばろう。