2010-1-26[火] xorshift乱数のメモ

XorShift乱数は、こちらとかのように短い関数で紹介されるけれど、たいていシード固定で書かれていて、シードを外部から与えたい場合はどうしたら、と悩んでしまう. もちろん、ちょっとぐぐったらシード設定できるソース載せてるサイトあるし、 おおもとのpaper に all 0でなければよいようなことかいてあるようだけど、 どの程度適当でよいのか不安にもなる. で、今さらながら2chの擬似乱数2 をみたら76に解説&seed設定付ソースがあった. シードは極端な設定をすると不自然な部分列が出力されるからMTのを参考にしたとある. ありがたく、これ流用させていただくことに... と、よくよくみれば、ここの初期化とほぼ同じ(改良版)のよう.

その他、検索したときのサイトメモ.

mt-lite実行速度に xorshiftを含む各種乱数の速度比較あり.

良い乱数・悪い乱数に XorShiftと他の乱数との速度比較とかSSE2使ったバージョンとかがある. 同サイトの こちらにもいろいろなコンパイラでの測定比較あり.

xorshift.pdf 上記サイトで、"問題があると書かれている" とあったのでみた(翻訳ソフトでわからないなりに). 元のpaperより突っ込んだ性能テストをして、通過しないテストがいくつか(も)あるよう. (XorShiftは3つのシフト数の有効な値の組み合わせがいくつか(も)あるけれど、 組み合わせによって性能にばらつきがあるよう) あと改良版として256ビット版が載ってる. (周期のビット数だけでなく、計算でのシフト数も増やして精度をあげている)

XorShift乱数の速度

擬似乱数2の 42 に 周期 32,64,96,128,160,192 ビット版のソースがあったので、 ちょっと速度比較してみた.

ソースは コレコレコレ. (zip)

96ビット版が要修正だったり64ビット版は出力も64ビットだったり だったので 結局 paper みて修正. あと、xorshift.pdfの256ビット版追加. (シード設定可のクラスにしたりでエンバク不安あり. 64,96,160版はA,B,Cの選択がこれでよいのか自信なし).
で paper の160のソース、>>Aになっているけど <<Aの誤記だと思われる. 他と比べてもだし、別のチェックで結果がメタメタになった.

結果は以下. 環境は基本Phenom2 3GHz (玄箱HGは PowerPC 266MHz).
100000000回実行の平均. 単位:ナノ秒.

 vc9
(32bit)
vc9
(64bit)
mingw
g++3.4.5
mingw
g++ 4.4.0
dmc8.51owc 1.8bcc 5.8.2玄箱HG
g++4.1.2
XorShift 32 3.4112.6623.3292.99710.4803.3555.01023.100
XorShift 64 2.0162.1671.8421.9965.1593.0003.73434.700
XorShift 96 2.3354.3451.6672.0415.7733.0233.51238.500
XorShift 128 2.3313.9632.4191.9955.4443.2303.68546.200
XorShift 160 2.3344.2062.3382.0266.2313.0023.18746.200
XorShift 192 2.5843.8742.8762.3368.1153.1573.56646.200
XorShift 256 7.3976.2646.3276.49117.2246.1847.197134.800
線形合同法の乱数 1.5091.3361.6645.7843.5811.3293.15423.200
clib rand 18.55914.17415.08014.7206.5345.2363.231461.900
MT Rand 5.4525.6797.9965.86931.2999.2898.280127.200

下3つは比較用. MT乱数(mt19937ar-cok.c)と 線形合同法を使った乱数とC標準ライブラリのrand()を使ったもの.

コンパイラごとに癖はあるけれど、大筋は似た傾向.

paperの例では1.8GHzで4~6ナノ秒とあったので、 3GHzの環境(vcやg++)で 2~4ナノ秒は、そんなものかもしれない.
なお、これら(の速い値)はインライン展開されている(はず). 関数呼び出しになっている場合は、(vcにて) 3~6ナノ秒台だった (テストルーチンで乱数をファンクタにせずワンクッション関数を噛ましてたとき)

全体に周期32ビット版は他より遅くなっているのは、たぶん(アウトオブオーダーとかのレベルの)命令の並列化ができないためだろうか.

速度的には、 大筋ビット数が増えれば遅くなるけれど、32-192の範囲では 増える周期(質の改善)に比べ時間の増加はさほどでもないので、 どうせなら128でなく160や192あたりを使うのも手かもしれない.

256ビット版はプログラムが少々複雑になっているせいか 時間増加のよう. 128ビット版にくらべ2~3倍... MTと対して変わらない速度(場合によっては負ける)なので出番はないだろう.

でinline展開で速いのはいいけれど、 ビット数が大きいほど(ささやかとはいえ)コードサイズが膨れやすくなるので、 乱数の質が高くなくていいなら、ビット数少ないのを選ぶのもよいかもしれない.
でも線形合同法でいいなら、(inline展開されたら)そっちのほうが速いか.

サイズきになるならinlineしない形に書いて160,192あたりを... もっとも、このソースの64,96,160(,192)は使ったパラメータがほんとにこれがいいのかわかっていないので 結局 128 を選んでおくのがベターな気はする.


あと、XorShiftの件とはずれるが、vcやg++でのcライブラリの rand()の速度が遅いのは、 マルチスレッド対応のオーバーヘッドのためだろうか. インライン展開された線形合同法の乱数の10倍前後なのは ペナルティが大きいとも、10数ナノ程度ならば大抵たいしたことないとも、どちらとも. 結局使用量/使用箇所しだい、だけれど、どっちにしろ精度のことを思えば、 とっとと XorShiftなりMTなり用意して用途別にインスタンスを管理したほうが、 楽になれると思う.

(参考サイトにある SIMD版のSFMTとかが使える環境なら, そっちのほうがいいだろうな)


追記

乱数の精度の評価についてはさっぱりなんですが (自分が使った処理において出目に不都合があるかどうかくらいなら、ともかく)、 同根のtest2をしたときの結果はあまりよいという感じではなかった.(この場合のテストとして適切かどうかもわかってないけど)

まあ、たいていの場合の乱数の利用頻度や精度を思うと 普通は MT を選んどくのが無難だと思う.

この程度の速度差(時間差)やプログラムサイズ差が ネックになるような利用頻度(仕様)やターゲット環境なんて ゲームでもまずないだろうし.
どちらかというとライブラリ化でのオーバーヘッドのほうが 気になる可能性があるかも. (この程度のサイズのルーチンなんだから、わざわざメーカー提供のライブラリ使わなくてもいいよね、とか)