2007-04-08 15:26:27 +0900 (1072d); rev 5
プログラムが速ければ速いほどいいのは世の必定である。 Ruby でプログラムを書くときは速度を気にしないで済むことが多いが、 それでもものには限度・節度ってもんがある。 使いすてプログラムならまあ、 どんなに遅くてもちゃんと目的が果たせればいいだろう。 しかし、繰りかえし使われるライブラリなどはそれでは困る。 ライブラリは使う期間も長いし、何度もいろいろな場面で使うので、 遅いとちょっと気になる。
そうすると、いわゆる最適化ってやつをすることになる。 よく言われるとおり、 最も有効な最適化はアルゴリズムの最適化 (やり方を変える) である。 だがこれは C だろうとなんだろうと同じなので 「Ruby で」っていうのと関係ないし、 この分野はそれこそ死にもの狂いで専門のひとたちが研究してるわけだから いまさら素人が口を出すこともあるまい。なので、ここでは筆者が知っている 「Ruby の姑息な最適化技法」をこまごまと紹介してみたい。
と、その前に、少しだけ Ruby プログラムのボトルネックについて話しておく。
実を言うと、多くの Ruby プログラムではアルゴリズムは あまり速度に関係していなかったりする。 もちろん、以下に述べるような姑息な最適化なんてもう全然関係ない。 だいたいの場合、プログラムの速度は GC (?GarbageCollection) だけで決まっている。
従って、GC に負担をかけない、あるいは GC と相性のいいプログラムは速い。 Ruby 1.8.1 時点では、以下のようなプログラムは GC と相性がいい。
なぜなら、こういうパターンだと Ruby のガーベージコレクタは さっさと GC をあきらめて、しばらくメモリ増量に専念してくれるからである。 そうすると GC 回数が減って、速くなる。という理屈だ。
パフォーマンスとかをあまり考えず豪勢にメモリを使うと だいたいこういう性質が現れるので、 スクリプト言語であるところの Ruby としてはよい傾向かもしれない。
最初は有名なやつから。 下に行くほど難易度が上昇する。
破壊的メソッド (「!」が付くメソッド) はそうでないのに比べ概して高速。 しかし最近は非破壊的メソッドも高速化されてきているので以前ほど 違わなくなってきているのは確かだ。 たとえば gsub と gsub! だと作業自体は gsub のほうが高速だったりする。 計測してみると非破壊的メソッドが遅いことが多いのは、 無駄なオブジェクトが増えて GC が起きているからである。
これも上と同じだけど特にあげる。 String および Array の + を連発すると遅い。 破壊的に行っていいものはできるだけ concat にするのがよい。 姑息な最適化では、とにかく malloc が減るようにするのがコツだ。
ちなみに、文字列リテラルで生成されたオブジェクトは、 変更しようとした時点でオリジナルがコピーされてから 変更を加えるようになっている。 そのため、例外的に 'str' << 'str' よりも 'str' + 'str' のほうが速い。
またいくら concat を使っても文字列が巨大になってくると realloc が一気に遅くなってくるのでちょっとキツい。 このあたりは 1.8 で改善されている。
Fixnum は C レベルの整数なので非常に軽い。 特に生成は他のオブジェクトに比べると断然速い。 また GC の対象にもならない。
Symbol オブジェクトもやはり C の整数なので軽い。 Ruby 本体でもやっているように、名前など、 多用する文字列を Symbol に変えると速度とメモリ容量の両面を改善できる。
ただし、文字列を Symbol に変えて速くなるのは、 あくまでも特定の文字列が何度も繰り返し登場する場合である。 同じ内容の文字列がまったく存在しない場合には Symbol を使うとむしろ遅くなる。
Ruby のオブジェクト自体の生成はリンクリストから持ってくるだけなので軽い。 しかし、Array や Hash のようなコンテナオブジェクトは同時に オブジェクト格納用の領域を割り当てるので malloc が発生する。 特に Hash はその構造上それなりの領域を使うので、使い捨てるのはおしい。 再利用できるものは片端から再利用しよう。
例えば Hash をバッファのように使うときは、 最初に一度だけ生成して clear してからまた使う。 Array の場合は Hash よりは効果が小さいが、 それでも生成するよりはやっぱり速い。 Hash は clear して使いまわすほうがかなり速い。
ちなみに Ruby の内部構造については RubyHackingGuide や Ruby 本の 8 章「Inside Ruby」を見てほしい。 それと当然ながら Ruby のソースコードも見逃せない一次情報である。
イテレータを while にしたら速くなるかなーと思ったらなんと遅くなった (Array#each の場合)。Ruby レベルのループまわしは遅いみたいだ。 なんと、(1..limit).each と Array#[] を使うよりも遅い！ 一般に、明示的な while ループよりイテレータのほうが高速である。 C レベルで書いた操作が多いほど (== Ruby レベルで書いたコードが少ないほど) 速いようだ。
ちなみにイテレータを自分で作る場合は「&」引数で受けて 「&」引数で丸投げするのが一番速い (もちろん、それで済む場合だけに限られる)。 block.call(i) と yield(i) では yield がかなり速い。
ブロックの引数は多いほど遅い。 多重代入が効いているようだ。__send__ する場合と比べると、 引数が一つかゼロだとイテレータの方が速いが二つ以上だと __send__ の方が速い。
重複しない集合を得たいとき。Array に入れておいて uniq! するよりも Hash のキーとして登録していくほうが圧倒的に速い。 hash メソッドの値をうまく設定するのもコツ。
Array#index より Hash のほうが速い。どのくらい速いかというと、 Array のインデックス 0 でヒットしても Hash のほうが速い (ことが多い)。 なぜだぁ。
大量にオブジェクトが生成されていて、そのほとんどは使われているのが わかっているときは GC を止めてしまう。仕事が終わったら明示的に開始する。 効くときは秒単位で効く。
このへんは世代別 GC が導入されれば随分変わるはず…… と言われていたのだが、どうもこのまま導入されない気配が濃厚である。 ただし、Ruby 1.8 でメモリ割り当てと GC 発生のアルゴリズムが改善された結果、 以前よりも GC の問題は起きにくくなっている。
時間のかかるところを全部 C で書いてしまう。 モノによっては 10 倍以上速くなるがデバッグの手間も 10 倍近くなる。 だがスピードが重要で本当に役立つものならば書きなおす価値はある。 Ruby では拡張ライブラリが非常に簡単に作れるので意外に検討の価値はある。
→ RubyExtensionProgrammingGuide
しかしその逆に、拡張ライブラリを作るのがあまりに簡単なため 小さい拡張ライブラリをどんどん作ってしまい、 メンテナンス性が異様に悪くなるという罠も存在する。
以下は測定の結果無駄とわかったもの。書いてある秒数は 10 万回あたり。 計測した環境は Celeron 333(A)MHz + 128MB + Linux 2.0.36、全てスワップなし。 ただし Ruby の場合誤差がかなり入るのでここの数値を信用してはいけない。 やはり実際に測りたいもので計測するのが一番だ。
メソッドを手で展開する。Ruby ではありとあらゆる操作がメソッドゆえ、 一つ二つ減ったところでなかなか効果は出ない。 メソッドひとつで 0.21sec (キャッシュヒット時)。
「"」より「'」のほうが微妙に速い…はずだった。だが無駄 (0.08sec)
"....#{exp}" と '...' + exp とどっちが速いか。考えるだけ無駄 (0.06sec)
というか、これは両方ともコンパイル時にしか差が出ないのだから、 こんなの考えるまでもなく無駄である。
ブロック変数は遅いので、ブロックの外で宣言しておいて ローカル変数にするとちょっと速くなる。でも無駄 (0.10sec)。
Related Pages: RubyPages
system revision 1.162