$Id: optimize.rd,v 1.4 2003/06/18 23:28:28 aamine Exp $
プログラムが速ければ速いほどいいのは世の必定である。Ruby はインタ プリタであるゆえそんなに速度に気をつかってもしょーがないのは確かだ し、そういうのって楽しくない。これは Ruby の第一教条に反する。
しかしいくらスピードを気にしないと言っても、ものには限度・節度って もんがある。使いすてプログラムならまあ、どんなに遅くてもちゃんと目 的が果たせてりゃいい。しかし、繰りかえし使われるライブラリなどはど うだろうか？ 筆者などはアプリケーションを作っている途中にライブラ リを増殖させるくせがあるもので、ライブラリが結構たくさんある。そう すると、使う期間も長いし、何度もいろいろな場面で使うので、遅いとちょっ と気になる。それにスクリプトだろうとなんだろうとやっぱり遅いよりは 速いほうがいい。
そうすると、いわゆる最適化ってやつをすることになる。よく言われるとおり、 最も有効な最適化はアルゴリズムの最適化 (やり方を変える) である。だがこ れは C だろうとなんだろうと同じなので「Ruby で」っていうのと関係ないし、 この分野はそれこそ死にもの狂いで専門のひとたちが研究してるわけだからい まさら素人が口を出すこともあるまい。なので、ここでは筆者が知っている 「Ruby の姑息な最適化技法」をこまごまと紹介してみたい。
最初は有名なやつから。 下に行くほど難易度(と鬼度)が上昇する。
破壊的メソッド (！が付くメソッド) はそうでないのに比べて概して高速。
しかし最近は非破壊的メソッドも高速化されてきているので以前ほど違わ
なくなってきているのは確かだ。たとえば gsub と gsub! だと作業自体
は gsub のほうが高速だったりする。非破壊的メソッドが遅いのは主に捨
てオブジェクトが増えて、その結果 GC が起こるのが原因だ。
1.8 で世代別 GC が実装されるとまた結果が変わってくるはず。
これも上と同じだけど特にあげる。String および Array の + は遅い。
破壊的に行っていいものはすべて concat にするのがよい。姑息な最適化
では、とにかく malloc が減るようにするのがコツだ。
ちなみに、スクリプト埋めこみの文字列は変更しようとした時点でオリジ
ナルがコピーされてから変更を加えるようになっている。そのため、例外
的に 'str' << 'str' より 'str' + 'str' のほうが速い。
またいくら concat を使っても文字列が巨大になってくると realloc が一気に
遅くなってくるのでちょっとキツい。このあたりは 1.7 で改善されている。
Fixnum は C レベルの整数なので非常に軽い。特に生成は他のオブジェク
トに比べると断然速い。また GC の対象にもならない。1.5 から導入され
た Symbolクラスもやはり C の整数なので同。Ruby 本体でもやっている
ように、文字列のかわりに Symbol を使うようにするとかなり CPU とメ
モリの両面を節約できる。
ただし例外として、Symbol をたくさん作りまくって一回使うとおしまい、
という場合には Symbol を使うと遅くなる。文字列を Symbol に変換する
コストのほうがデカくなるからだ。と言っても相当作らないと速度は変わらない。
たとえば 10 万個とか。
Ruby のオブジェクト自体の生成はリンクリストから持ってくるだけなので
軽い。しかし、Array や Hash のようなコンテナオブジェクトは同時にオ
ブジェクト格納用の領域を割り当てるので malloc が発生する。特に
Hash はその構造上それなりの領域を使うので、使い捨てるのはおしい。
再利用できるものは片端から再利用しよう。
例えば Hash をバッファのように使うときは、最初に一度だけ生成して
clear してからまた使う。Array の場合は Hash よりは効果が小さいが、
それでも生成するよりはやっぱり速い。Hash は clear して使いまわすほ
うがかなり速い。
ちなみに Ruby の内部構造については拙著 Ruby Hacking Guide や Ruby 本の 8 章「Inside Ruby」を見てほしい。 それと当然ながらソースコードも見逃せない一次情報である。
イテレータを while にしたら速くなるかなーと思ったらなんと遅くなった
(Array#each の場合)。Ruby レベルのループまわしは遅いみたいだ。
なんと、(1..$limit).each を使うよりも遅い！
イテレータのほうが C に封入されてる操作が多いから速いようである。
ちなみにイテレータを自分で作る場合は＆引数で受けて＆引数で丸投げする
のが一番速い (もちろん、それで済む場合だけに限られる)。block.call(i)
と yield(i) では yield がかなり速い。
ブロックの引数は多いほど遅い。多重代入がきいているようだ。__send__ す
る場合と比べると、引数が一つかゼロだとイテレータの方が速いが二つ以上だ
と __send__ の方が速い。
重複しない集合を得たいとき。Array に入れておいて uniq! するより
Hash のキーとして登録していくほうが圧倒的に速い。#hash をうまく
設定するのもコツ。
Array#index より Hash のほうが速い。どのくらい速いかというと、
Array のインデックス 0 でヒットしても Hash のほうが速い(ことが多い)。
なぜだぁ。
大量にオブジェクトが生成されていて、そのほとんどは使われているのが わかっているときは GC を止めてしまう。仕事が終わったら明示的に開始する。 効くときは秒単位で効く。
このへんは世代別 GC が導入されれば随分変わるはずだ。
時間のかかるところを全部 C で書いてしまう。モノによっては 10 倍以上 速くなるがデバッグの手間も 10 倍近くなる。だがスピードが重要で本当に 役立つものならば書きなおす価値はあるだろう。Ruby では拡張モジュール が非常に簡単に作れるので意外に検討の価値はある。
測定の結果無駄とわかったもの。書いてある秒数は 10 万回あたり。 計測した環境は Celeron 333(A)MHz + 128MB + Linux 2.0.36、全てスワップなし。 ただし Ruby の場合誤差がかなり入るのでここの数値を信用してはいけない。 やはり実際に測りたいもので計測するのが一番だ。
メソッドを手で展開する。Ruby ではありとあらゆる操作がメソッドゆえ、
一つ二つ減ったところでなかなか効果は出ない。メソッドひとつで 0.21sec
(キャッシュヒット時)。
「"」より「'」のほうが微妙に速い…はずだった。だが無駄 (0.08sec)
"....#{exp}" と '...' + exp とどっちが速いか。考えるだけ無駄 (0.06sec)
ブロック変数は遅いので、ブロックの外で宣言しておいて
ローカル変数にするとちょっと速くなる。でも無駄 (0.10sec)。