MTよりSFMTの方が速いという幻想？

実際、MTの配布元がMTよりSFMTの方が2倍速いと標榜しているのだが、MTの方は、今時の乱数ライブラリインライン呼び出しに対応していないとか、配列への一括生成モードに対応してないとか、生成ルーチンそのものでないオーバーヘッドが大きいこともあるので、「だったら対応させれば速いんじゃないの？」ということである。

なお、この記事はApple M1の性能検証を兼ねているのでこの記事なんかも目を通していただけると幸いである。

64ビット版MTはSIMDでも有効

SIMD化は少ないビット数の演算を複数並列で行うのでビット数が少ないほど恩恵が大きいと言われるが、結論からいうとMT19937-64はSIMDに向いている。
64ビットだから１回で使わないといけないこともないし、16ビットとして4つに分割して使ってもいい。そもそもそういうデータ均質性があるからこそのC++標準ライブラリ入りなのである。

もちろんSIMDで64ビット×2のパックド演算が頻出するが、AltiVecでは64ビット×２のSIMDをサポートしてないとかおそらくそういうことであれば、x86のSSE2以降とかARMのNEONではその範囲内でできるので、その点は問題にならない。

むしろAVX2の256ビットまで素直にスケールするポテンシャルを秘めている。
AVX-512もアラインメント不整合をどうにか我慢すればいける。
というかむしろ速い。

64ビット版なら配列アクセスにかかる定数が偶数（＝アラインメントが揃う）

というのも、なんのことはない、定数定義が偶数であるため、mt[i+MM] とかを並列にアクセスする際にアラインメント補正が不要なのである。mt[i+1]の部分はどう足掻いても奇数になるのでここは仕方がないが。

#define NN 312
#define MM 156

もしここが奇数だとミスアラインとなるため、NEON(ASIMD)ではVEXT*操作、SSEだとpalignrなどが必要になってきて、その分性能のロスになるのである（Intel AVX以降はロードユニットのサイクルが大きくなるがずれていてもロードはできる）。その点、156は4でも割り切れるので、256ビットSIMDまではアラインメント揃ったデータとしてロードできる。

データの依存性が低い

SFMTと比べて直近のデータとの依存がない点も考慮したい。
SFMTは1つ前と2つ前の各128ビット値を参照してXORを取る。したがって、256ビットとか512とかに容易に並列化できない。
（SFMTの256ビット並列版は、特定のパラメータの時だけ限定して演算をショートカットして2並列動作させることができるインチキをしているが2つ前までは無理だった）

とりあえずはコードだ

そんなわけでApple M1向けに書いてみたのがこのコードである。
https://github.com/magurosan/PRNG-Apple/blob/main/mt19937-64-neon.c

なぜそこでインラインアセンブラ？

我ながら不思議なことをやっているので、まずこれの説明をしよう。

#if defined(__apple_build_version__) 
#define INSERT_IF_TRUE(a,b,mask)  __asm__ ("bit.16b %1,%2,%3" :"=w"(a) : "w"(a), "w"(b), "w"(mask))
#else 
#define INSERT_IF_TRUE(a,b,mask)  a = vbslq_u64(mask, b, a)
#endif

新命令はともかく既存命令であるが、明示的にインラインアセンブラで命令指定しているのは、vbslq_u64と書いたのをコンパイラがわざわざ A and UPPER_MASK | B and LOWER_MASK の3命令(AND+AND+OR)に勝手に展開するというあまりに "FUBAR" なコードを生成してくれたせい。clang君、今回ばかりは無能な働き者にも程がある。
グローバルな最適化を阻害するのであんまり使いたくないのだけどせっかくのハンドオプティマイズを台無しにされては怒り心頭なので今回は致し方ないとする。

Apple版clangだけがこうであるとは限らないがとりあえずこうしておく。

MT19937-64でもSHA3命令はもちろん有効

SFMTと同じく新命令のBCAXとEOR3がいい仕事をしてくれている。
やはり新たに書き起こしたSIMDを用いた配列への一括生成でのスコアが良く、SFMTと同じ50,000,000回分の生成に換算すると34.6msとなり、先の性能改善版SFMTとほぼ同等の生成速度となる。

% clang -O3 mt19937-64-neon.c -o neon_test 
% ./neon_test bench      
100000000 random numbers generation time                                                                                 
Original:       178.26 ms
NEON:           145.24 ms
NEON x2:         95.45 ms
NEON ARRAY:      84.76 ms

% clang -O3 -march=armv8.4-a+simd+sha3 -DHAVE_SHA3 mt19937-64-neon.c -o m1test 
% ./m1test bench 
100000000 random numbers generation time                                               
Original:            173.37 ms
NEON+SHA3:           111.67 ms
NEON+SHA3 x2:         86.29 ms
NEON+SHA3 ARRAY:      69.13 ms

Cortex-A77機で追試してみたらやっぱりMTは遅くでSFMTの方が安定して性能上がっていたので、性能向上はCPUの実装依存なのかもしれない。