generator の設計

設計目標

ベンチマークは、何年も後に同じ入力で、また別のターゲットで再実行できなければなりません。generator はそのために必要な 2 つのプリミティブを提供します。1 つの実行シードを独立した名前付きのストリームに変えるシード導出と、実際に使われた入力を記録するフィンガープリントです。どちらも引数の純粋関数です。

数学的背景

すべての算術は 64 ビットワード上で $2^{64}$ を法として行います。排他的論理和を $\oplus$ 、論理右シフトを $\gg$ と書きます。

導出

ドメイン文字列 $D = c_1 c_2 \dots c_m$ （Unicode コードポイント）とインデックス $i$ に対して、derive_seed(s, D, i) は次を計算します

\begin{aligned} h_0 &= s \oplus \mathtt{0xCBF29CE484222325}, \\ h_j &= (h_{j-1} \oplus c_j)\cdot \mathtt{0x100000001B3}, \qquad j = 1, \dots, m, \\ z_0 &= (h_m \oplus i)\cdot \mathtt{0x9E3779B97F4A7C15}, \\ z_1 &= (z_0 \oplus (z_0 \gg 30))\cdot \mathtt{0xBF58476D1CE4E5B9}, \\ z_2 &= (z_1 \oplus (z_1 \gg 27))\cdot \mathtt{0x94D049BB133111EB}, \\ \mathrm{derive\_seed}(s, D, i) &= z_2 \oplus (z_2 \gg 31). \end{aligned}

最初の 2 行は、シードを鍵とし、64 ビットのオフセット基底と素数を使う FNV-1a です。3 行目は SplitMix64 の黄金比インクリメントである $\lfloor 2^{64}/\varphi\rfloor$ を掛けます。最後の 3 行は SplitMix64 の出力ファイナライザです。¹1 G. L. Steele, D. Lea and C. H. Flood, “Fast splittable pseudorandom number generators”, OOPSLA 2014. ファイナライザの定数は SplitMix64 のものです。

単射性

各ステップは 64 ビットワードの全単射です:

$x \mapsto x \oplus a$ はそれ自身が逆写像です。
$a$ が奇数のとき、 $\gcd(a, 2^{64}) = 1$ なので $x \mapsto a\,x$ は $2^{64}$ を法として可逆です。5 つの乗数はすべて奇数です。
$k \ge 1$ のとき、 $x \mapsto x \oplus (x \gg k)$ は可逆です。上位 $k$ ビットは変わらず、その下の $k$ ビットの各ブロックはすぐ上のブロックから復元できます。

ここから直ちに 2 つの帰結が得られます。

異なるインデックスは決して衝突しません。 $s$ と $D$ を固定すると $h_m$ は固定され、 $i \mapsto z_0 \mapsto z_1 \mapsto z_2 \mapsto$ 結果は全単射の合成です。ID の異なる 2 つのデータセット、反復、ブロックは、どの実行シードについても異なるシードを得ます。
異なる実行シードは決して衝突しません。 $D$ と $i$ を固定すると $s \mapsto h_0$ は全単射であり、FNV の各ステップ $h \mapsto (h \oplus c)\,p$ も全単射で、残りも同様です。実行シードを変えると、導出されるすべてのシードが変わります。

衝突が起こりうるのは異なるドメインの間だけで、そこでは FNV-1a はランダムな関数のように振る舞います。 $N$ 個のドメイン文字列について、何らかの衝突が起こる確率は高々およそ $N^2 / 2^{65}$ です。

ファイナライザは雪崩効果をもたらします。入力の 1 ビットを反転すると、出力の各ビットが $1/2$ に近い確率で反転します。そのため、連続するインデックスでは $z_0$ が下位ビットしか違わなくても、互いに無関係なシードが生成されます。

連鎖した導出

measurement_seed(s, d, r, b) は、ドメイン "dataset"、"repetition"、"block" で derive_seed を 3 回適用します。外側の呼び出しに帰結 2 を、各レベルに帰結 1 を適用すると、 $d$ 、 $r$ 、 $b$ のいずれか 1 つを他を固定して変えれば結果が変わることがわかります。

フィンガープリント

stable_fingerprint(x) は、 $x$ の UTF-8 バイト列の SHA-256 の 16 進ダイジェストに "sha256:" を前置したものです。衝突にはおよそ $2^{128}$ の計算量が必要なので、 $N$ 個のフィンガープリントの間で偶発的な衝突が起こる確率は高々 $N^2/2^{257}$ です。

設計上の決定

1 つのグローバルな生成器ではなく派生したストリーム

問題。 乱数ストリームが 1 つだけだと、データセットを追加したり呼び出しの順序を変えたりすると、それ以降のすべての入力が変わります。選択。 各利用者が、実行シード、ドメイン、インデックスから自分のシードを導出します。理由。 入力は生成の順序ではなく名前と ID だけに依存するため、データセットの一部だけを単独で再生成でき、データセットを追加しても他は変わりません。

ライブラリの生成器ではなく整数の混合

導出は 64 ビット整数の乗算、排他的論理和、シフトだけを使い、これらはどの MoonBit バックエンドでも同一に実装されています。浮動小数点に基づく生成器やプラットフォームの生成器では、native、JS、wasm の間で結果が異なる可能性があります。

バイトではなくコードポイント

ドメインは Unicode コードポイント 1 つずつハッシュされます。ASCII のドメインでは標準の FNV-1a と同じですが、それ以外の文字では UTF-8 バイト列に対する FNV-1a とは異なります。それでも決定的です。別のツールでシードを再現する必要がある場合は、ASCII のドメイン名を使ってください。

SHA-256 フィンガープリント

問題。 入力を保存せずに、アーティファクト内で識別する必要があります。選択肢。 FNV などの高速な非暗号学的ハッシュ、または SHA-256。選択。 アルゴリズムの接頭辞付きの SHA-256。理由。 フィンガープリントはマシンや年をまたいで比較されます。衝突すれば 2 つの入力が黙って統合されてしまいます。接頭辞があるので、曖昧さなく別のアルゴリズムを導入する余地が残ります。

ランナーはシードをそのまま渡す

ランナーはフィクスチャに、実行シードそのものを含む GenerationContext を渡します。必要なドメインを決めて導出するのはフィクスチャです。例えば derive_seed(context.seed, context.case_id, context.dataset_key.dataset_id) のようにします。導出をフィクスチャに置くことで、1 つのフィクスチャが複数の独立したストリームを引けます。

正しさと不変条件

決定性と移植性。 結果は引数だけに依存し、どのターゲットでもビット単位で同一です。
上で導いたとおり、インデックスとシードについての単射性。
フィンガープリントの形式。 常に sha256: の後に小文字の 16 進数字 64 桁が続きます。
純粋性。 呼び出しの間で状態を保持する関数はありません。

採用しなかった代替案

状態を持つグローバルな乱数生成器。 順序に依存します。
seed + index。 シードを混合しない生成器には、隣接するシードが相関したストリームを供給することになります。
高速な非暗号学的ハッシュによる内容ハッシュ。 監査の目的には衝突しやすすぎます。

境界

generator が提供するのはシードであって乱数ではありません。値を引くのはジェネレータ関数の役割です。
導出は暗号学的ではありません。シードは実行シードから予測できますが、それこそが狙いです。
stable_fingerprint は鍵なしで、データを認証しません。
入力の正規シリアライズは呼び出し側に任されます。

G. L. Steele, D. Lea and C. H. Flood, “Fast splittable pseudorandom number generators”, OOPSLA 2014. ファイナライザの定数は SplitMix64 のものです。 ↩