boost::randomの罠

今日は先生が午後から用事があったみたいで、ミーティングが朝の10時からに変更。結局あんま誰もネタがなかったから別に今週なしでもよかったよーな。そうそう中間発表が21日だそうで、パワポの準備とかせなあかんなぁ。発表10分やのに質問20分というありえない時間配分が素敵。隠しスライドいっぱい作っとくか？

で、午後からは相変わらずコーディングの続き。乱数あたりをいじってたのでその考察。

乱数生成は特に理由がない限りメルセンヌツイスタ法を使うのが基本。間違っても標準のrand()なんて使わないよーに。このアルゴリズムは今んとこ精度及び速度の点から最良と言われてる代物。わざわざ自分で作らなくてもboost::randomにboost::mt19937というメルセンヌツイスタ法の実装があるからこれを流用。残念ながらこいつはVC6ではコンパイルが通らないので、VC6とかその他古いコンパイラで使いたい場合はCのソースがこのへんとかにある↓
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/mt.html

まぁせっかく.NETが使えるんやからboost::randomを使ってみる。一様分布を生成するのにサンプルとかではboost::uniform_intを使ってる例が多いけど、boost::uniform_smallintってのがある。リファレンスを読む限り、分布の範囲が狭い場合は限界値による統計的な乱れを無視できるものとして単純に範囲で割るだけみたい。どーゆーことかとゆーと、例えば整数の範囲が32767の時に0〜10の乱数を得るなら10で割って余り返せばいいけど、0〜10000の乱数を得るのに単純に10000で割った余りを返すのは危険だとゆー話。とゆーことは裏を返せば、uniform_intはそのへんの端の乱れを補正してるわけでなかなか優れもの。やけど、今回の用途では特に不要。

で、この補正が実際どんくらいパフォーマンスに影響が出るかを測定してみたところ。速度優先で最適化しても10％ほどの違いが出る模様。てか、最適化かけなかったら50％も違う。なんでこんな違うねんと思ってトレースしてみたところ、どうやらuniform_intで範囲指定がある一定より狭い場合は、内部でuniform_smallintを呼んでるみたい。そらー遅くなって当然。で、そのある一定値ってのがなんぼなんか気になるからチェックしてみたところ、だいたい10の10乗くらい。でかっ。大抵の場合uniform_smallintで間に合うってことやん？

で、最適化かけたら10％の低下でとどまるのはやっぱり関数オブジェクトのinline展開が効いてるんかなぁとか思う(関数オブジェクトってのは関数呼び出しをinlineできるように、関数をoperator()を持ったオブジェクトとして作成すること)。inlineの効果を測定するならCの実装と比較した方がわかりやすいかなぁと、メルセンヌツイスタのCの実装とC++の実装を比較してみた。最適化オプションつけて速度を測ってみたとこ、衝撃の事実が発覚。
Cのメルセンヌツイスタの実装は上の20倍ほど速い。
．．．が、しかし、C++のメルセンヌツイスタboost::mt19937そのものは、さらにCの2倍速い。
これからわかることは、やはりCの通常の関数呼び出しより、C++の関数オブジェクトのinline展開の方が速い。が、しかしuniform_intと組み合わせた瞬間ありえないくらい遅い。つまり、
uniform_intいらねー。
一様分布が欲しいだけならマニュアルどおりboost::variate_generatorで分布関数なんぞとバインドせず、直接mt19937を呼びましょう。指数分布が欲しくなっても決して分布関数とバインドせずに、自分でmt19937をlogに突っ込みましょう。