Nendoパフォーマンスチューニングメモ(1)
[Nendo]処理系のパフォーマンスチューニングを実施した際のメモを晒しておく。(こういう記録はブログとかWikiに書いとくのが一番だと思う)
Nendoの特性について
まず、何と比較するかという問題であるが、[Nendo]は1つのS式ごとにrubyプログラムを自動生成し、rubyでevalしながら走るので、手書きのrubyプログラムと速度比較するのがわかりやすだろう。 ただ、そうはいっても[Nendo]を極限まで最適化しても、手書きのプログラムに勝ることは不可能であることは明白なため、[Nendo]の生成コードとして最大限狙える限界のコードと比較してみることにした。(参考までに手書きのコードも同時に示す) [Nendo]が手書きコードに勝てない理由を書いておくと、動的にエラーチェックをする必要があることと、四則演算なども関数なので’+’や’-‘を記述しただけでも関数呼び出しになる(Schemeのサブセットとして考えるとそうしないといけない)ので、同じアルゴリズムを記述した場合でも、[Nendo]のほうが多くの処理をする必要がある。
計測方法
計測ツールにはruby-profを使った。 マイクロベンチマークプログラムには、階乗計算と竹内関数(別名:たらいまわし関数)を使う。 その他のベンチマークプログラムは、この次考えることにしよう。
計測に使ったコード
tak(竹内関数)への引数は全て tak(10, 5, 0) とした。 ruby-tak 人間がrubyでプログラミングした一般的なコード
def tak( x, y, z )
if y >= x
y
else
tak( tak( x-1, y, z ),
tak( y-1, z, x ),
tak( z-1, x, y ))
end
end
ruby-tak3 Nendoが目指すべき生成コード
def tak3( x, y, z )
@inner_minus = Proc.new { |_a,_b|
_a - _b
}
@inner_ge = Proc.new { |_a,_b|
_a >= _b
}
@inner_tak = Proc.new { |_x,_y,_z|
if ( @inner_ge.call( _y, _x ))
_y
else
@inner_tak.call(
@inner_tak.call( @inner_minus.call(_x,1), _y, _z ),
@inner_tak.call( @inner_minus.call(_y,1), _z, _x ),
@inner_tak.call( @inner_minus.call(_z,1), _x, _y ))
end
}
@inner_tak.call( x, y, z )
end
nendo-tak 人間がNendoでプログラミングした一般的なコード
(define (tak x y z)
(if (>= y x)
y
(tak (tak (- x 1) y z)
(tak (- y 1) z x)
(tak (- z 1) x y))))
計測結果
マシン環境 Hardware: MacBook Pro 13inch OS: MacOS X Snow Leopard version 10.6.4 CPU: 2.4GHz Intel Core 2 Duo Memory: 4GB 1067MHz DDR3 ruby: ruby 1.9.3dev (2010-10-14 trunk 29498) x86_64-darwin10.4.0
* 最適化前
Nendo 0.3.4リリース版の結果である。
tak (ruby version)
user system total real
0.040000 0.000000 0.040000 ( 0.039284)
tak3 (ruby version)
user system total real
0.220000 0.000000 0.220000 ( 0.214475)
tak (nendo version)
user system total real
34.130000 0.730000 34.860000 ( 34.848524)
ruby-tak3 : nendo-tak = 1.0 : 155.13 (約155倍遅い)
* 引数リストを Listではなく、Arrayで渡すようにした。
ruby-profで計測した結果、引数リストをList型で渡しているところが重いことがわかった。 現状: callProcedure( ‘func’, @_func, * a, b, c .to_list ) 形式は (cons a (cons b (cons c ‘()))) のようなList形で引数を渡している。 最適化後: 固定長引数の場合は、@_func.call( **a, b, c ) というlistを使わない呼びだし形式にした。 当然、ArrayのほうがRubyの組み込みクラスなので処理が軽い。 最適化の結果は以下のようになった。
tak (ruby version)
user system total real
0.030000 0.000000 0.030000 ( 0.032908)
tak3 (ruby version)
user system total real
0.210000 0.000000 0.210000 ( 0.215441)
tak (nendo version)
user system total real
22.200000 0.720000 22.920000 ( 22.908085)
ruby-tak3 : nendo-tak = 1.0 : 105.71 (約106倍遅い)
* シンボル変換処理をコンパイル時に持っていった。
まだ重い部分があったので調べてみると、tak関数が呼ばれる度に、Nendoの関数名をrubyの名前空間でのメソッド名に変換する処理が走っていることに気がついた。 Nendoの関数名はSchemeの識別子と同様に、’-‘ や ‘’ などのように rubyの識別子に使える範囲外の文字が使えるため、それらを変換してやる必要がある。 (例: aa-bb を aa_MIMARK_ASMARKbb_METHOD に変換する処理) 最適化の結果は以下のようになった。
tak (ruby version)
user system total real
0.030000 0.000000 0.030000 ( 0.033190)
tak3 (ruby version)
user system total real
0.210000 0.000000 0.210000 ( 0.217253)
tak (nendo version)
user system total real
10.020000 0.120000 10.140000 ( 10.130185)
ruby-tak3 : nendo-tak = 1.0 : 47.71 (約48倍遅い)
まとめ
引数リストの受け渡しにオーバーヘッドの大きいList型を使っていた問題と、シンボル変換をコンパイル時ではなくランタイム時に行っていた問題を改善することによって、takの計算時間を約1/3に改善することができた。
今後の高速化アイデア
今回の計測で、Nendoのビルトインの四則演算関数は可変長引数を受けるバージョンしかないため、可変長引数を扱うオーバーヘッドが依然大きいことがわかっている。 (+ 2 2) などのようにソースコード上で引数の数はわかっているわけなので、四則演算の２引数固定バージョンなどを用意して、コンパイル時に選択すればtakなどのマイクロベンチマークではかなり高速化できそうである。 ただ、メンテナンスの面からあまり良い方法とはいえないので、もっと良い方法が何か検討する。
ほかにも、mapやfilterなどはNendoで実装するのではなくRubyのネイティブのmapやselectをうまく利用してRubyの速度に近づけるアイデアもある。 但し、rubyのmapが使えるのは mapに1個のリストが与えられた場合のみであるが、それでもほとんどのNendoプログラムではmapやfilter関数に複数のリストを与えることは稀であることから十分有効なアイデアだと考える。
ちなみに、今回の改善は 0.3.5に入る予定です。