mini-python 高速化 - 日記を書く [・w・] はやみずさん

現在のmini python VM は、VMのプロトタイプTiviにちなんで、自分の中ではTivi2と呼んでおります。

そんなことはどうでもよい。

VMの速度が思ったほど出ないなー、と思ってプロファイリングをとってみたら、STLのvectorをふんだんに利用しているのが、どうも遅さの一員らしい、ということがわかってきた。そこで、限定的な場面で（といってもかなり沢山呼ばれる）配列を使うように切り替えてみたところ、劇的に高速化することができた。

サンプルプログラムにフィボナッチ数の計算、数値積分などをするsamplesというコード群があるのだけれど、そいつらをまとめて10回繰り返し実行する run_simples.sh というシェルスクリプトを実行して、その実行時間を測ってみたところ、次のような結果になった。計測はtimeコマンドで、5回走らせて平均をとった。画面出力は、どちらも /dev/null にリダイレクトしてある。

本家python(sec)	Tivi2 (sec)
12.84	13.67

ε(　v°ω°)ε(　v°ω°)ε(　v°ω°)ε(　v°ω°)ε(　v°ω°)

しかし、辞書式のアクセスが今のところ線形探索になっているので、sor.py という熱伝導方程式を解くプログラムに3分以上かかってしまうんだよなぁ。本家pythonなら5秒程度で終了するのだけれど。今ハッシュを使って実装しなおしているけど、はたしてそこまで辿りつけるか。

ハッシュ以外に思いつく高速化としては、forループのコンパイルだろうか。sor.py だけでなく、サンプルにあるforループはどれも for var in range(...) という形になっている。この形になっていると最適化をかけれそうなので、それで幾分か早くなるんじゃないかと思っている。

今のforの実装だと、カレントフレームのスタック上にシーケンスのインデックスを保持して、それを1回ずつインクリメントして、シーケンスの長さと比較して、シーケンスから値を取り出して、ループの中身を実行して、ということになっている。とりあえず書いた、という状態なので相当おばかな感じ。

  12: VM_LREF_PUSH( 0 )  --- インデックスの値をスタックにプッシュ
  13: VM_IMMVAL_NUM( 1 ) --- 1 をレジスタにロード
  14: VM_ADD2_NUM()      --- インデックスとレジスタの値を加算
  15: VM_LSET( 0 )       --- インデックス更新
  16: VM_LREF_PUSH( 0 )  --- インデックスの値をスタックにプッシュ
  17: VM_LREF( 1 )       --- シーケンスの長さをジレスタにロード
  18: VM_NUMLT2()        --- インデックスとシーケンスの長さを比較
  19: VM_GOTOIFNOT( 28 ) --- 終了条件ならば、ループを抜ける
  20: VM_LREF_PUSH( 2 )  --- シーケンスをスタックにプッシュ
  21: VM_LREF( 0 )       --- インデックスをレジスタにロード
  22: VM_GETITEM()       --- レジスタの値をインデックスとして、スタックにあるシーケンスから値を取り出してレジスタにロード
  23: VM_GSET( i )       --- ループ変数にレジスタの値を代入
 ... ループの中身 ...