Edited at

Ruby でベンチマークを取る方法

初心者向けの良い記事がなかったので書いてみる。私も深くは理解していない。


動機

たとえば,配列 array に収められた数値の総和(合計)を求めるのに

sum = array.inject(&:+)

sum = 0

array.each{|x| sum += x}

のどっちが速いんだろう?ということが知りたい。

inject 版の簡潔さは魅力だけど,巨大な数表が与えられて計算しまくらないといけない場合,やっぱり速いやり方を知っておきたい。


まずいやり方

ベンチマークテストのやり方を知らなかったら,こんな方法を思いつくかもしれない。

start_time = Time.now

# (計測したい処理)
puts Time.now - start_time

これが無意味ということはないけれど,問題がある。

いまの CPU は忙しいので,「計測したい処理」をやりつつ他の仕事もやってるかもしれない。上のスクリプトだとそういう時間も含まれてしまう。

また,「計測したい処理」がディスクアクセス,ネットワークアクセスを含むようなものだと,ディスクやネットワークの反応を待ってて CPU が何もしていない時間 まで含まれてしまう。それらの反応はそのときどきでたぶん違うから結果が安定しないし,そもそも目下の関心は Ruby スクリプトが費やした時間なのだ。


benchmark ライブラリー

Ruby にはその名もずばり benchmark というライブラリーが標準で付いているので,これを使おう。

http://docs.ruby-lang.org/ja/2.2.0/library/benchmark.html


最も簡単なやり方

まず以下の形を覚えよう。このくらい単純なら,何回か書けば覚えられるよね。

require 'benchmark'

Benchmark.bm 10 do |r|
r.report "Nantoka" do
# (計測したい処理その1)
end
r.report "Kantoka" do
# (計測したい処理その2)
end
end

このスクリプトを実行すると,結果が

                 user     system      total        real

Nantoka 1.217000 0.000000 1.217000 ( 1.210070)
Kantoka 0.858000 0.000000 0.858000 ( 0.856049)

のように表示される。

bm メソッドの引数 10 は,「Nantoka」「Kantoka」というラベル部分に確保すべき桁数(文字数)だ。一番長いラベルの文字数にするか,ちょっと多めの値にしておけばいい。


結果の見方

数値の単位は秒だ。小数点以下 6 桁もあるが,有効数字はそんなにない。その件はあとでまた触れる。

でも user, system, total, real と四つもあって,一体どれを見たらいいの?

冒頭で「初心者向けの良い記事がない」と書いたのはこのこと。これらの数値の意味を書かなければしょうがないよね。

まず real からいこう。これは処理の開始から終了までの時間。経過時間とも言う。だから,CPU がぼーっとしていたり,他の仕事をやっている時間も含まれる。これは見なくていい。

なぜ real と呼ぶかというと,たぶん我々が暮らしているこの世界における現実の時間だからだろう。これに対し,user, system, total はいずれも CPU にとっての時間,つまり CPU が実際に動いている時間であって,「CPU 時間(CPU time)」と呼ばれる。

total は単純に user と system の和。

system は「システム CPU 時間」のこと。OS はファイルの読み書きなどの基本的な機能を「システムコール」という形で提供しているが,プログラムがそれを呼び出したときに,その実行に費やした CPU 時間をこう呼ぶらしい。

user は「ユーザー CPU 時間」のことで,ユーザープログラムの実行に費やした CPU 時間。いまの場合,Ruby スクリプトを実行すべく Ruby 処理系が働いたぶんの CPU 時間のことだ。

この記事の冒頭に掲げた総和の例のように,OS の機能を呼び出さないプログラムなら system はゼロなので,user と total は一致する。

一般の場合,user と total のどちらを見ればよいかは,目的によるのだろう。


real より total が大きいことも

複数の CPU を並列に動作させるのでない限り,total ≦ real となるはずだ。

しかし実際にやってみると,total のほうが real より若干大きな値になることがある。

計測の誤差ではないかと思うけど,よく分からない。


では,総和の計算で試してみよう。

require 'benchmark'

array = 1000.times.map{ rand }

num_iteration = 10000

Benchmark.bm 10 do |r|
r.report "inject" do
num_iteration.times do
sum = array.inject(&:+)
end
end

r.report "each" do
num_iteration.times do
sum = 0
array.each{|x| sum += x}
end
end
end

num_iteration.times doend ってなんじゃらほい? 実は千個の数値の総和なんて 1 ミリ秒もかからないので,それを一万回やらせた時間を測ることにしたのだ。

結果はこうなった。

                 user     system      total        real

inject 1.186000 0.000000 1.186000 ( 1.189068)
each 0.874000 0.000000 0.874000 ( 0.871050)

かっこいい inject よりマジメに += するほうがだいぶ速いではないか。

理由は分らないけど,inject の場合,ブロックパラメーターが二つある Proc オブジェクトを call するのがしんどいのかもしれない。

もう一度実行してみると,こうなった。

                 user     system      total        real

inject 1.170000 0.000000 1.170000 ( 1.173068)
each 0.858000 0.000000 0.858000 ( 0.855048)

微妙に変わった。何度もやってみると,少なくとも 2% くらいのばらつきはあるようだ。


誤差について

さきほどの例で,繰り返し回数(num_iteration)を 100 に減らしてみよう。CPU 時間は 1/100 になるはず?

                 user     system      total        real

inject 0.015000 0.000000 0.015000 ( 0.012001)
each 0.016000 0.000000 0.016000 ( 0.008000)

ん? ほとんど変わらなくなった。もう一度やってみる。

                 user     system      total        real

inject 0.016000 0.000000 0.016000 ( 0.013000)
each 0.016000 0.000000 0.016000 ( 0.010001)

ん? 同じになった。もう一度。

                 user     system      total        real

inject 0.015000 0.000000 0.015000 ( 0.013001)
each 0.000000 0.000000 0.000000 ( 0.009000)

今度は each 版がゼロに???

                 user     system      total        real

inject 0.000000 0.000000 0.000000 ( 0.013000)
each 0.015000 0.000000 0.015000 ( 0.009001)

今度は inject 版がゼロ??? うーむ。

繰り返し回数をいろいろ変えてやってみると,0.015 秒の(ほぼ)整数倍になることが分った。

別の環境(ハードウエア,OS,Ruby 処理系が違う)でやってみると,0.01 秒の整数倍になった。

その程度の精度しかないんである。

つまり,だ。CPU 時間が 0.01 秒とかになるようなベンチマークテストをやっても,有効数字ゼロ桁の結果 しか得られないというわけだ。

意味のある比較をするためには,目安として CPU 時間が 1 秒程度はほしい。

といって,あまり長いとたるい。

そこで,繰り返し回数を初回はちょっと少なめにしておいて,結果を見つつ桁を増やしてちょうどいいくらいになるようにすればいい。


データの規模と CPU 時間の関係

速度面でどのアルゴリズムが優れているかを判断するとき,データの規模との関係に気をつけなければならない。

たとえば,長さ 100 の配列を何かするのに,ベンチマークテストの結果,アルゴリズム A が B の倍くらい速いことが分ったとする。

でもこれだけで A を選択するのは早計。

長さ 10000 の配列だと B のほうが断然速い,ということがありうるのだ。

A は配列の長さ $n$ に対して,おおむね $n^2$ に比例した時間がかかるが,B だとおおむね $n \log n$ に比例した時間がかかる,なんてことが実際よくある。するとどこかの $n$ で勝ち負けが逆転したりすることになる。

だから,いろいろなデータの規模でベンチマークを取ったり,現実の処理でどのようなデータの規模になるのかを見極めたり,といったことが必要になるだろう。


データの偏り

さて,こんな問題を考える。

整数の配列 array の総和が奇数かどうかを判定するのに,どうするのが速いか。

単純に実装すればこうなる。

def sum_is_odd?(numbers)

numbers.inject(&:+).odd?
end

これより速くできないかな。

ええと,偶数を足しても偶奇性は変わらないから,足さなくていいんじゃないの? 奇数だけの総和で判定すれば速くなるかも。select で奇数だけ選び出して総和を求めればいいね。

では比べてみよう。array が長さ一万の整数配列だとして,下記を実行。

def sum_is_odd1(numbers)

numbers.inject(&:+).odd?
end

def sum_is_odd2(numbers)
numbers.select(&:odd?).inject(&:+).odd?
end

n = 1000

Benchmark.bm do |r|
r.report "sum_is_odd1" do
n.times{ sum_is_odd1(array) }
end

r.report "sum_is_odd2" do
n.times{ sum_is_odd2(array) }
end
end

結果はこう。

       user     system      total        real

sum_is_odd1 0.936000 0.000000 0.936000 ( 0.935053)
sum_is_odd2 0.578000 0.000000 0.578000 ( 0.583033)

おお! やはり効果があった。倍速とは言わないけど,格段に速くなった。

というのはウソ。実は上記の結果を出した array には著しい偏りがあって,一万個の整数のうち,奇数は一つしか無かったのデス。一度も加算をやらないから速かったんだね。

奇数と偶数が半々のデータでやってみると,

       user     system      total        real

sum_is_odd1 0.936000 0.000000 0.936000 ( 0.943054)
sum_is_odd2 1.170000 0.000000 1.170000 ( 1.187068)

のように,却って遅くなっちゃった。

でもね,さっき「ウソ」って書いたけど,実際のデータが偏っているということはあり得るわけで。もし奇数が圧倒的に少ないデータしか扱わないのであれば,「奇数総和法」(?)はやっぱり有効な方法だと言えるわけ。

処理対象のデータの,規模だけでなく偏りについても注意を払ったほうがいいということだね。

ちなみに,総和の奇数性判定はもう少し速い方法がある。

奇数を奇数個足せば奇数,偶数個足せば偶数なので,奇数の個数を数えればいい。こんな感じ。

def sum_is_odd3(numbers)

numbers.select(&:odd?).length.odd?
end

奇数・偶数が半々のデータでやってみると,こう。

       user     system      total        real

sum_is_odd1 0.952000 0.000000 0.952000 ( 0.945054)
sum_is_odd2 1.201000 0.000000 1.201000 ( 1.213069)
sum_is_odd3 0.671000 0.000000 0.671000 ( 0.680039)


ガーベジコレクション

大きなデータを扱うとき,ベンチマークテストは難しくなる。私もあまり分かっていないし,このテーマは「次のステップ」だと思うので,さわりだけ。

ベンチマークテストの実行中に「ガーベジコレクション」というものが起きると,そのぶんユーザー CPU 時間も増えてしまうので,本来測りたい時間がよく分からなくなってしまう。

ん? そもそもガーベジコレクション,つかガーベジって何さ?


ガーベジ

こんなスクリプトを考える。

a = "foo"

b = a
a = "bar"
b = "baz"
# (つづく)

三つの文字列リテラルがある。こいつらは,Ruby の処理系がスクリプトを解釈し,いざ実行しようとする時点で既に String オブジェクトとしてオブジェクト空間に用意されているらしい。

1 行目で,そのうちの一つ "foo"a に代入される。Ruby では,代入と言っても変数という箱にオブジェクトが入るわけではなく,変数というラベル(名前付きの札)にオブジェクトが紐づけられる,というイメージだ。

2 行目で a が参照しているオブジェクトが b に代入される。この時点で,件の String オブジェクトに ab という二つのラベルが紐づけられた。

3 行目で,a に別の String オブジェクトが代入される。これにより,元々 a が参照していた String オブジェクトに紐づけられたラベルは b だけになった。

4 行目で b にまた別の String オブジェクトが代入され,ついに元々 a が参照していた String オブジェクト "foo" に紐づけられたラベルは無くなってしまった。

"foo" を顧みる者はいなくなった。さみしい。

"foo" はどこからも参照されていないので,もはやこれが何かに使われることは永遠になくなったのだ。

※ええと,実は Ruby ではそういうオブジェクトを再び参照する方法があるんだけど,ここでは無かったことにする。

こういうオブジェクトは,オブジェクト空間に漂うゴミというか屑なので,garbage [ɡɑ́ːrbiʤ] と呼ばれる。少なくともスクリプトが終了するときにはキレイに消されるので,心配は要らない。


ガーベジコレクション

んが,しか〜し! オブジェクトがどんどん作られてオブジェクト空間が手狭になってきたらどうするのか?

このときは,Ruby の処理系が屑を集めて捨ててくれる。これを garbage collection という。GC なんて略すこともある。

あるオブジェクトが屑なのかどうかは,すべての参照を丁寧に追っていかなければ判定することができない。よって,屑拾いはけっこう大変なことであるらしい。大変てことは,いまの我らの関心事で言うと,CPU 時間を食ってしまう ということだ。

しかも屑拾いはどんなタイミングで起こるのか,基本的には分からない。よって,ベンチマークテストにとって大いに問題なんである。


ガーベジコレクションの影響を軽減する

実は Benchmark モジュールには,屑拾いの影響を軽減しつつ測定するメソッド bmbm がある。使い方は bm とだいたい同じ。詳しくはリファレンスマニュアルを見てくれ。

http://docs.ruby-lang.org/ja/2.2.0/class/Benchmark.html#M_BMBM

力尽きたのでこのへんで。


追記(2015年4月17日) inject についての注意

この記事で数値の総和を求めるのに

inject(&:+)

と書いてしまったが,これは適切でなかった。レシーバーが空のとき,これだと 0 を返さないのだ。

[].inject(&:+) #=> nil

空の可能性があるときは初期値を与えて

inject(0, &:+)

としなければならない。これだと

[].inject(0, &:+) #=> 0

となるので,メソッドチェインで .odd? とかできる。

ちなみに,

[1, 2, 3].inject(&:+)

は加算が 2 回行われる。

[1, 2, 3].inject(0, &:+)

だと 3 回行われる。

だから空でないと分っている場合に初期値を与えるのは無駄といえば無駄。ただ,多くの場合,気にするほどでもないだろう。


追記(2016年5月2日) 奇数の個数を数える

データの偏り」で奇数の個数を数えるのに

numbers.select(&:odd?).length

というコードを掲げたけど,条件にあう要素の個数を数えるのは,selectlength を組み合わせるよりも Enumerable#count を使ったほうが良かった。

numbers.count(&:odd?)

簡潔になるだけでなく,速い。

本文のベンチマークでいくと,これで 10~20% 速くなった。