JDK にバグ報告してみたおはなしと、 Java における LXM の不思議な実装について

はじめに

どの擬似乱数生成器が速いのかを BenchmarkDotNet で調べるために、いろいろな擬似乱数生成器を C# に移植して遊んでいたのが発端です。

Java では、JDK 17 から LXM ファミリという擬似乱数生成器が追加されています。
簡単に説明すると、線形合同法 (LCG) と xoroshiro/xoshiro を組み合わせて (Mix して) 出力する擬似乱数生成器です。組み合わせは 8 種類あり、内部状態 96 bit の小規模なものから 1152 bit の大規模なものまで取り揃えています。

実例として、 L32X64MixRandom の C# 移植例はこのようになります。

public sealed partial class L32X64Mix
{
    private uint _increment;
    private uint _lcgState;
    private uint _xbgState0, _xbgState1;

    public L32X64Mix(uint increment, uint lcgState, uint xbgState0, uint xbgState1)
    {
        if (xbgState0 == 0 && xbgState1 == 0)
            throw new ArgumentException("xbgState must not be all zero");

        _increment = increment | 1;
        _lcgState = lcgState;
        _xbgState0 = xbgState0;
        _xbgState1 = xbgState1;
    }

    public uint NextUInt()
    {
        // Mix
        uint result = _lcgState + _xbgState0;
        result = (result ^ result >> 16) * 0xd36d884b;
        result = (result ^ result >> 16) * 0xd36d884b;
        result = (result ^ result >> 16);

        // LCG
        _lcgState = _lcgState * 0xadb4a92d + _increment;

        // xoroshiro64
        (uint s0, uint s1) = (_xbgState0, _xbgState1);
        s1 ^= s0;
        s0 = BitOperations.RotateLeft(s0, 26) ^ s1 ^ s1 << 9;
        s1 = BitOperations.RotateLeft(s1, 13);
        (_xbgState0, _xbgState1) = (s0, s1);

        return result;
    }
}

これは 32 bit LCG + xoroshiro64 の組み合わせの最も小規模な LXM で、主に 32 bit 環境を主眼とした実装です。ちなみに RandomGenerator#getDefault() でもこれが生成されます。
~~デフォルトは L64X128 とかのほうが良かったのでは、と思わなくもない~~

テスト結果が合わない

擬似乱数生成器の実装において、テストはとてつもなく重要です。
うっかり間違った実装をしたとしても結果はランダムなので、全く気づけなくなります。

今回は Java の実装から乱数を出力させてテストケースを作成しました。特定のシードで初期化してから 20 個の nextLong() の結果があっていればおそらく大丈夫でしょう、ということで…

import java.util.random.*;

class javaprng {
    public static void main(String[] args) {

        RandomGenerator rng = RandomGeneratorFactory.of("L32X64MixRandom").create(42);
        for (int i = 0; i < 20; i++) {
            System.out.printf("%016x%n", rng.nextLong());
        }
    }
}

C# 移植側の nextLong() 互換実装はこんな感じです。

public sealed partial class L32X64Mix
{
    public ulong Next()
    {
        return (ulong)NextUInt() << 32 ^ (ulong)NextUInt();
    }
}

というわけでテストにかけてみたのですが、これが何度直しても通りません。
Java 側と C# 移植側の出力を比べるとどうにも合わないのです…。

この diff を見ると、半々程度の割合で上位 32 bit が合っていない場合があるようです。
そこで、改めて Java 側の nextLong() の実装を確認することにしました。

public long nextLong() {
    return ((long)nextInt() << 32) ^ (long)nextInt();
}

L32X64MixRandom は 32 bit ベースなので、 nextInt() がメインの遷移・出力関数です。これを 2 個つなげて long つまり 64 bit にしている、ように見えます。
ところが、その認識が誤っていたことに気づきました。

念のため説明しておくと、 Java には組み込みの符号なし整数型 (C# でいう ulong) がありません。
そのため long にキャストして拡張しているわけなのですが、これは符号付き整数型のため、符号拡張が行われます。
ということはつまり、 nextInt() が負の (最上位ビットが 1 の) 数を返した場合に、符号拡張のため上位 32 bit にも情報がはみ出します。具体例を挙げると、nextInt() が 0xfedcba98 を返した場合、 (long)nextInt() は 0x00000000fedcba98 ではなく 0xfffffffffedcba98 になります。

これを上位ビットと xor でつなげているため、下から 32 ビット目 (2 個めの nextInt() の最上位ビット) が 1 のときに上位 32 bit が反転するという現象が起きているわけです。
この情報をもとに diff をよく見ていただけると分かるかと思います。

そうなると、果たしてそれは妥当なのか、という疑問が浮かびました。乱数の出力が変わってしまっているわけですから、本来の性質を保てているか分からなくなってしまうのでは？と思いました。

なので、バグ報告をしてみることにしました。

JDK に報告してみる

バグレポートは https://bugreport.java.com/bugreport/ から投げることができます。アカウントなどは不要のようです。

ここにバグの概要や環境情報、再現用コードや回避手段などを記入して投げます。

1 日程度待つと、中の人が確認してくれた上で、チケットが発行された旨のメールが届きます。

これでチケットが web 上で確認できるようになりました。私が記入した内容が載っているので、知りたい方はご参照ください。英語に不安がある……

また、あとから何かに気づいたなど追加情報がある場合は、このメールにあるリンクから送信することができます。

あとは中の人たちがよしなにしてくれるのを待ちます。

バグじゃなかった？

チケット公開から 1 日ほど経ったころ、チケットが resolved になりました。 "Not an Issue" とのこと…

中の人曰く (意訳)、

報告者は、ランダムな 32 bit をつなげて 64 bit にするのが正しいと仮定しているが、これはドキュメント化されていない挙動である (ので、それが正解とは限らない) 。
現在の実装は驚くべきものに見えるかもしれないが、均等分布性は損なわれていない。

(現行実装の) nextLong() から 2 つの nextInt() の結果を復元することは可能であり、情報の損失や生成はない。
nextInt() 2 個と nextLong() の間には全単射の関係があり、前者が一様分布なら、後者も一様分布になる。

もし接続が xor ^ ではなく or | だったら、それは不具合だっただろう。

ということで、これで問題ないとのことです。なんと……

ただ実際、仮に直したとしても再現性が維持できなくなる問題が出てくるので、これはこれで良かったのではないか、とも思います。

なので、 C# における nextLong() の正しい互換実装はこのようになります:

public sealed partial class L32X64Mix
{
    public ulong Next()
    {
        // see https://bugs.openjdk.org/projects/JDK/issues/JDK-8304120
        return (ulong)NextUInt() << 32 ^ (ulong)(long)(int)NextUInt();
    }
}

せっかくなので、本当に問題ないかどうか、擬似乱数生成器のテストフレームワークである PractRand に nextLong() の出力を与えてテストしてみました。

RNG_test using PractRand version 0.94
RNG = L32X64MixRandomJava64, seed = 0x19aa8a23
test set = expanded, folding = extra

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 512 megabytes (2^29 bytes), time= 2.9 seconds
  no anomalies in 1220 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 1 gigabyte (2^30 bytes), time= 7.7 seconds
  no anomalies in 1293 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 2 gigabytes (2^31 bytes), time= 15.4 seconds
  no anomalies in 1368 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 4 gigabytes (2^32 bytes), time= 29.2 seconds
  no anomalies in 1448 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 8 gigabytes (2^33 bytes), time= 60.3 seconds
  no anomalies in 1542 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 16 gigabytes (2^34 bytes), time= 117 seconds
  no anomalies in 1636 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 32 gigabytes (2^35 bytes), time= 213 seconds
  no anomalies in 1716 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 64 gigabytes (2^36 bytes), time= 455 seconds
  no anomalies in 1807 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 128 gigabytes (2^37 bytes), time= 914 seconds
  no anomalies in 1902 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 256 gigabytes (2^38 bytes), time= 1667 seconds
  no anomalies in 1983 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 512 gigabytes (2^39 bytes), time= 3541 seconds
  no anomalies in 2058 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 1 terabyte (2^40 bytes), time= 7137 seconds
  no anomalies in 2132 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 2 terabytes (2^41 bytes), time= 14111 seconds
  no anomalies in 2194 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 4 terabytes (2^42 bytes), time= 29294 seconds
  no anomalies in 2255 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 8 terabytes (2^43 bytes), time= 59262 seconds
  no anomalies in 2313 test result(s)

rng=L32X64MixRandomJava64, seed=0x19aa8a23
length= 16 terabytes (2^44 bytes), time= 119867 seconds
  no anomalies in 2366 test result(s)

時間の都合で 16 TB までですが、問題は検出されませんでした。
実際のところも問題なさそうです。