generator 设计

设计目标

基准测试必须能在多年以后、在另一个目标上以相同的输入重新运行。generator 提供为此所需的两个基本组件：一种把一个运行种子转化为相互独立的具名流的种子派生方法，以及一个记录实际所用输入的指纹。两者都是其参数的纯函数。

数学背景

所有算术都在 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}

前两行是以种子为密钥、使用 64 位偏移基和素数的 FNV-1a；第三行乘以 $\lfloor 2^{64}/\varphi\rfloor$ ，即 SplitMix64 的黄金比例增量；最后三行是 SplitMix64 的输出终结器。¹1 G. L. Steele、D. Lea 和 C. H. Flood，“Fast splittable pseudorandom number generators”，OOPSLA 2014。终结器常数取自 SplitMix64。

单射性

每一步都是 64 位字上的双射：

$x \mapsto x \oplus a$ 是它自身的逆；
当 $a$ 为奇数时， $x \mapsto a\,x$ 在模 $2^{64}$ 下可逆，因为 $\gcd(a, 2^{64}) = 1$ ；五个乘数都是奇数；
当 $k \ge 1$ 时， $x \mapsto x \oplus (x \gg k)$ 可逆：最高的 $k$ 位不变，较低的每个 $k$ 位块都可以由其上方的块恢复。

由此直接得到两个推论。

不同的索引永不碰撞。 对固定的 $s$ 和 $D$ ， $h_m$ 是固定的，而 $i \mapsto z_0 \mapsto z_1 \mapsto z_2 \mapsto$ 结果是双射的复合。对于每个运行种子，id 不同的两个数据集、重复或区组都会得到不同的种子。
不同的运行种子永不碰撞。 对固定的 $D$ 和 $i$ ， $s \mapsto h_0$ 是双射，FNV 的每一步 $h \mapsto (h \oplus c)\,p$ 都是双射，其余部分也是。改变运行种子会改变每个派生种子。

碰撞只可能发生在不同的域之间，在那里 FNV-1a 的行为类似随机函数：对于 $N$ 个域字符串，发生任何碰撞的概率至多约为 $N^2 / 2^{65}$ 。

终结器提供雪崩效应：翻转一个输入位会以接近 $1/2$ 的概率翻转每个输出位。因此，即使相邻索引的 $z_0$ 只在低位上不同，它们产生的种子也互不相关。

链式派生

measurement_seed(s, d, r, b) 以域 "dataset"、"repetition" 和 "block" 三次应用 derive_seed。对外层调用应用推论 2，对每一层应用推论 1，可知在其他量固定时改变 $d$ 、 $r$ 、 $b$ 中的任何一个都会改变结果。

指纹

stable_fingerprint(x) 为 "sha256:"，后接 $x$ 的 UTF-8 字节的 SHA-256 十六进制摘要。制造碰撞需要约 $2^{128}$ 的工作量，因此在 $N$ 个指纹中发生意外碰撞的概率至多为 $N^2/2^{257}$ 。

设计决策

派生流，而非单一全局生成器

问题。 如果只有一个随机流，增加一个数据集或调整调用顺序就会改变之后的每个输入。选择。 每个使用者都从运行种子、一个域和一个索引派生自己的种子。理由。 输入只取决于它们的名称和 id，而不取决于生成顺序，因此可以单独重新生成部分数据集，增加数据集也不会改变其他数据集。

整数混合，而非库提供的生成器

派生过程只使用 64 位整数上的乘法、异或和移位，每个 MoonBit 后端对它们的实现都完全相同。基于浮点或平台的生成器在 native、JS 和 wasm 之间可能不同。

码点，而非字节

域按 Unicode 码点逐个进行哈希。对 ASCII 域而言这就是标准的 FNV-1a；对其他字符，它与基于 UTF-8 字节的 FNV-1a 不同，但仍然是确定性的。如果其他工具必须复现这些种子，请使用 ASCII 域名称。

SHA-256 指纹

问题。 产物中必须能标识输入，而又不存储输入本身。方案。 FNV 或其他快速的非密码学哈希；SHA-256。选择。 带算法前缀的 SHA-256。理由。 指纹要跨机器、跨年份进行比较；一次碰撞会悄无声息地把两个输入合并。前缀为将来使用其他算法留出了无歧义的余地。

运行器原样传递种子

运行器向夹具提供一个携带运行种子本身的 GenerationContext。由夹具决定它需要哪些域并自行派生，例如 derive_seed(context.seed, context.case_id, context.dataset_key.dataset_id)。把派生留在夹具中，使一个夹具可以抽取多个相互独立的流。

正确性与不变量

确定性与可移植性。 结果只取决于参数，并且在每个目标上逐位相同。
单射性：对索引和种子都成立，如上文所推导。
指纹格式。 总是 sha256: 后接 64 个小写十六进制数字。
纯粹性。 没有函数在调用之间保留状态。

被否决的方案

有状态的全局随机生成器。 依赖顺序。
seed + index。 相邻的种子会把相关的流送给不混合其种子的生成器。
用快速非密码学哈希计算内容哈希。 对审计用途而言太容易碰撞。

边界

generator 提供的是种子，而不是随机数：抽取值是你的生成器函数的工作。
派生过程不是密码学意义上的：种子可以从运行种子预测出来，这正是其目的所在。
stable_fingerprint 不带密钥，不能认证数据。
输入的规范序列化由调用者负责。

G. L. Steele、D. Lea 和 C. H. Flood，“Fast splittable pseudorandom number generators”，OOPSLA 2014。终结器常数取自 SplitMix64。 ↩