.NET 6 (Preview) における System.Random の実装変更

はじめに

2021 年 2 月に、 .NET 6 Preview 1 が公開されました。
なんとここで System.Random の仕様に大きめの追加・変更があったようなので、紹介します。

※ 本記事の内容は .NET 6 Preview 2 で確認しています。.NET 6 のリリース版では内容が変更される可能性があります。

`xoshiro256**` 擬似乱数生成器の採用

驚くべきことに、以前の記事で散々文句をつけた (そして変わらないだろうと思っていた) 擬似乱数生成アルゴリズムが変更になりました。

新しく採用されたのは xoshiro256** です。このアルゴリズムは速度面・品質面でかなり優秀です。
ざっくり比較すると次のようになります。

アルゴリズム	周期	サイズ (byte)	均等分布次元	失敗するテスト	`Next` 実行時間 (ns)
.NET 5 (Lagged-Fibonacci)	??? ( $\lt 2 ^ {1705}$ )	280	??? (< 55) @ 32 bit	BCFN, DC6	9.351
.NET 6 (xoshiro256**)	$2 ^ {256} - 1$	72	4 @ 64 bit	-	2.744

`xoshiro256**` とは

xoshiro256** は、 2018 年に Sebastiano Vigna 氏が開発した擬似乱数生成器です。
この方は Chrome などで採用されている xorshift128+ や、高速で有名な xoroshiro128+ を開発された方です。 xoshiro256** はそれらの改良版にあたります。

xoshiro256** の C# での実装例を示します。

// 内部状態 (全 0 以外なら可)
private ulong s0, s1, s2, s3;

// 64 bit 擬似乱数生成
public ulong NextUInt64()
{
    ulong result = BitOperations.RotateLeft(s1 * 5, 7) * 9;
    ulong t = s1 << 17;

    s2 ^= s0;
    s3 ^= s1;
    s1 ^= s2;
    s0 ^= s3;

    s2 ^= t;

    s3 = BitOperations.RotateLeft(s3 , 45);

    return result;
}

xoshiro256** は、 Xorshift や Mersenne Twister と同じ系列の理論を持ちます。
内部状態は 256 bit (64 bit x 4) 、周期は $2 ^ {256} - 1$ 、出力は 64 bit 精度で 4 次元に均等分布します。
出力関数の工夫により、 Xorshift や Mersenne Twister でみられた線形性テストでの失敗を克服しており、 BigCrush や hwd テストに合格します。
加えて生成は非常に高速で、作者のベンチマークによれば 1 秒間に 9.5 GB 程度の乱数を生成することができます。

あえて欠点を述べるとすれば、内部状態復元攻撃が比較的容易に行えること (4 つの連続する 64 bit 出力が観測できれば確実に復元可能) 、特定の (限定された) 状況下ではテストに失敗することなどが挙げられます。

既存の実装例としては Math.NET が挙げられます。標準ライブラリレベルで採用している言語は今のところ見つけられませんでした。

原典の論文はこちらを参照してください。
ちなみに、 xoshiro256++ などの出力関数を変更したバリアントも存在します。

シード指定時の互換性の維持

ところで、安直に System.Random の内部実装を変更してしまった場合、従来の乱数列の再現を期待するプログラムの動作が壊れてしまいます。

.NET 6 では、再現性が不要な new() コンストラクタではでは新しい xoshiro256** を、再現を期待する new(int seed) コンストラクタでは従来のアルゴリズムを用いる、というように切り替えることで対策をとっています。 *1
したがって、 xoshiro256** を使用したい場合はシード値を与えることができません。ちょっと残念ですが致し方ありません。

以降、本記事では new() で初期化した (xoshiro256** を使っている) ほうをベースに検証します。

出力関数

内部の状態遷移だけでなく、出力面でも強化が入っています。

`NextInt64()` シリーズ・ `NextSingle()` の追加

Next() の long を返すバージョンである NextInt64() / NextInt64(long maxValue) / NextInt64(long minValue, long maxValue) が追加されています。

なお、 NextInt64() の値域は $0 \le x \lt 2 ^ {63} - 1$ であり、 long.MaxValue は返さない点に注意が必要です。 *2
Next() の仕様に合わせたものかとは思いますが、それは旧アルゴリズムの設計上 int.MaxValue が出せないことによる措置でした (以前の記事を参照) 。アルゴリズム自体が変更になったことでこの制約に縛られる必要もなくなったはずで、無意味でよろしくない制約では？と思ってしまいます…
(せめて NextUInt64() が露出していれば…)

また、 NextDouble() の float を返すバージョンである NextSingle() も追加されています。

`Next(int maxValue)` の内部実装変更

xoshiro256** が使用される場合、 Next(int maxValue) などの「一定範囲に変換する処理」も効率が良いものに変更されています。
ざっくり抜粋すると以下のようになっています。

// ~= (int)Math.Ceiling(Math.Log(maxValue, 2))
int bits = BitOperations.Log2Ceiling(maxValue);
while(true)
{
    ulong result = NextUInt64() >> (64 - bits);
    if (result < maxValue)
        return maxValue;
}

maxValue 以上の最小の $2 ^ {bits}$ を求めて $0 \le result \lt 2 ^ {bits}$ の範囲で乱数を生成し、 $0 \le result \lt maxValue$ なら採用、そうでなければ再抽選する、というアルゴリズムです。
多少実行時間にブレがありますが、剰余や浮動小数点変換を使用する手法に比べて確率の偏りがなく高速です。
再抽選する確率は最悪の場合 ( $maxValue = 2 ^ {n} + 1$ ; 特に $n$ が大きい場合) でも 1 / 2 より小さくなるので、運が悪かったとしてもそれなりの試行回数で終了します。
(擬似乱数生成器の特性上、無限ループに陥る心配はありません。)

`NextDouble()` の内部実装変更

また、 NextDouble() の実装も変更になっています。

return (NextUInt64() >> 11) * (1.0 / (1ul << 53));

53 bit の乱数を生成して $2 ^ {53}$ で割ることで $0 \le result \lt 1$ を得る、という手法です。
"53" は double 型の仮数部のビット数 (+1) から来ています。

従来のアルゴリズムでは高々 $2 ^ {31} - 1$ パターンしかなかったのが $2 ^ {53}$ パターン出るようになったので、かなり精度が向上しました。

`NextBytes()` の内部実装変更

さらに、 NextBytes() も変更されています。
詳細は省きますが、ざっくり説明すると 1 回の乱数生成で得られる 8 byte 分の乱数を一度に書き込むようになっています。
(C 言語で uint64_t * にキャストしてごりごり書き込んでいくイメージ、といえば伝わりやすいでしょうか…)

従来は 1 回あたり 1 byte ずつちまちま書き込んでいたので、かなりの効率化が見込めます。 (後述しますが、実際非常に高速になっています。)

パフォーマンス

メモリ

.NET 6 では、 System.Random は 1 インスタンスあたり 72 byte を消費します。 *3
内訳は以下のようになっています。 (実装はイメージです)

class Random    // クラスのヘッダ(型情報など) 16 byte
{
    class Impl  // 子クラスのヘッダ 16 byte
    {
        ulong s0, s1, s2, s3;   // 擬似乱数の内部状態 32 byte
    }
    private Impl impl;  // 子クラスへの参照 8 byte
}

クラスが入れ子になっているため若干余分に確保してしまっていますが、以前 (280 byte) に比べると 1/4 近くになっています。

速度

とりあえず実測してみましょう。検証環境は以下の通りです。

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i7-7700HQ CPU 2.80GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores

.NET Core 5.0.4 (CoreCLR 5.0.421.11614, CoreFX 5.0.421.11614), X64 RyuJIT
.NET Core 6.0.0 (CoreCLR 6.0.21.15406, CoreFX 6.0.21.15406), X64 RyuJIT

各メソッドコール 1 回にかかった時間は以下の通りです。± は標準偏差、 Speed x は何倍速くなったかを示します。

Method	.NET 5 [ns]	.NET 6 [ns]	Speed x
`new()`	1989.19 ± 37.66	151.631 ± 4.83	13.119
`Next()`	9.351 ± 0.15	2.744 ± 0.03	3.408
`Next(401)`	12.575 ± 0.14	6.809 ± 0.10	1.847
`Next(168, 401)`	12.227 ± 0.17	5.142 ± 0.11	2.378
`Next(1 << 30)`	12.563 ± 0.19	2.941 ± 0.09	4.272
`Next((1 << 30) + 1)`	12.54 ± 0.15	14.323 ± 0.20	0.876
`NextDouble()`	10.43 ± 0.12	2.989 ± 0.05	3.489
`NextBytes(byte[256])`	2333.249 ± 19.59	41.31 ± 0.53	56.481
`NextInt64()`	#N/A	2.612 ± 0.08	#N/A
`NextInt64(401)`	#N/A	6.693 ± 0.15	#N/A
`NextInt64(168, 401)`	#N/A	4.916 ± 0.12	#N/A
`NextInt64(1L << 62)`	#N/A	3.844 ± 0.12	#N/A
`NextInt64((1L << 62) + 1)`	#N/A	14.55 ± 0.23	#N/A
`NextSingle()`	#N/A	3.168 ± 0.04	#N/A

速度差が特に大きかった new() と NextBytes() の処理時間の比較を以下に示します。

f:id:andantesoft:20210328221840p:plain

それ以外の Next() 系メソッドの処理時間の比較を以下に示します。

f:id:andantesoft:20210328221829p:plain

また、 .NET 6 で追加されたメソッド群と既存の似たメソッドの処理時間を比較したグラフを以下に示します。
(これだけ .NET 6 の中での比較です。)

f:id:andantesoft:20210328221834p:plain

ブレはありますが、全体的に 2 - 3 倍程度に速くなっています。特筆すべきは new() (約 13 倍速) と NextBytes (約 56 倍速) でしょう。 new() はかなり複雑だった初期化処理が単に乱数を設定するだけになったこと、 NextBytes は乱数をまとめて配列に書き込むようになったことが影響していそうです。

ただし、注意すべきは Next((1 << 30) + 1) と NextInt64((1L << 62) + 1) です。
これらは意図的に遅くなる (再抽選率がほぼ 1 / 2 と高くなる) 値を選んだケースで、最善の場合 (再抽選率 0) の Next(1 << 30), NextInt64(1L << 62) と比べると 3 - 5 倍程度時間がかかっており、 Next では .NET 5 のものよりも遅くなっています。

以上のように maxValue に依存して速度が結構変わるので、注意…するほどではないと思いますが、覚えておくとよいかもしれません。

32 bit 環境での速度について

xoshiro256** は、64 bit 環境 (ulong 上での計算が高速に動作する環境) を想定して設計されたアルゴリズムです。
従来のアルゴリズムは 32 bit 環境メイン (int ベース) のため、 32 bit 環境においては System.Random の動作が若干遅くなる可能性はあります。
検証環境がないので実測はできていませんが…

(2021/08/31 追記:)
32 bit 環境 (厳密には x64 か arm64 以外のプラットフォーム) においては、 xoshiro256** の代わりに xoshiro128** アルゴリズムの実装が使用されます。これは xoshiro256** のワードサイズを 64 bit から 32 bit にしたようなもので、性質も概ね同様です。周期は $2 ^ {128} - 1$ となっています。
したがって、上述の打ち消し部分の心配は杞憂でした。きちんと考えられていますね…!

余談: 静的インスタンスの追加 (未対応)

2021/03/28 時点ではリクエストレベルですが、 PR #50297 で静的なインスタンスを取得するプロパティが提案されています。

// ライブラリ内の定義 (イメージ) 
public class Random {
    public static Random Shared { get; }
    // ...
}

// 使用例
int randomValue = Random.Shared.Next(10);

これによって、再現性が不要なら乱数インスタンスを自分でいちいち生成・保持する必要がなくなります。
また、よく見かける誤用である「乱数が必要になるたびに new Random().Next() する」ことをある程度防げるのでは、とも思い、とても便利そうです。
正式採用されることを願って…!

(2021/08/31 追記):
.NET 6 Preview 4 で Random.Shared が実装されました。🎉

おわりに

永遠に悲しみを背負い続けるのだろうと思っていた乱数周りに手が入るとは、と大変驚いて・喜んでいます。
従来のカオティックなアルゴリズムに比べて理論的にも実用的にも優れており、かつこちらで対応する必要はほぼないのでとてもありがたいです。
メジャーリリースを楽しみにしています。

はじめに

xoshiro256** 擬似乱数生成器の採用

xoshiro256** とは