runner 设计

设计目标

基准测试结果只有在三件事都成立时才能作为证据：各实现在被测量的输入上算出了正确答案，每个实现都在相同条件下被测量，并且测量可以追溯到一个种子、一个协议和一个环境。runner 是唯一执行负载的包，它的构建方式使这些性质依靠构造而非依靠自律成立：验证先于计时，实现的顺序是平衡的，批次大小经过校准，每个原始观测都会被发出。

数学背景

区组与测量模型

对于一个数据集，运行器在区组 $b = 0, 1, \dots, E + C - 1$ 中测量 $k$ 个实现：先是 $E$ 个探索性区组，然后是 $C$ 个验证性区组（exploratory_samples 和 confirmatory_samples）。在一个区组内，每个实现运行一个批次。把实现 $i$ 在区组 $b$ 中的每次迭代时间建模为

y_{i,b} = \mu_i + \tau_{p_i(b)} + \delta\, s_i(b) + \varepsilon_{i,b},

其中 $p_i(b) \in \{0, \dots, k-1\}$ 是 $i$ 在区组内的位置， $\tau_p$ 是位置效应（区组的第一个批次在较冷的缓存下运行）， $s_i(b) = bk + p_i(b)$ 是全局槽位编号， $\delta$ 是线性漂移（热降频、后台负载）， $\varepsilon$ 是噪声。我们关心的量是 $\mu_j - \mu_i$ 。

循环拉丁方顺序

在 OrderPolicy::BalancedBlocks(order_seed) 下，区组 $b$ 按 balanced_order(k, b + o) 的顺序运行各实现，即位置 $p$ 上是实现 $(p + b + o) \bmod k$ ，偏移量为 $o = (\text{order\_seed} \oplus \text{run\_seed}) \bmod k$ 。因此实现 $i$ 位于位置

p_i(b) = (i - b - o) \bmod k .

平衡性。 对固定的 $i$ ，映射 $b \mapsto (i - b - o) \bmod k$ 是从任意 $k$ 个连续整数到 $\{0, \dots, k-1\}$ 的双射。在由 $k$ 个连续区组构成的每个完整周期中，每个实现恰好在每个位置出现一次： $k \times k$ 的位置表是一个拉丁方。

抵消。 在一个完整周期 $b_0, \dots, b_0 + k - 1$ 上对模型求和：

\begin{aligned} \sum_{b} \tau_{p_i(b)} &= \sum_{p=0}^{k-1} \tau_p, \\ \sum_{b} s_i(b) &= k \sum_{b} b + \sum_{b} p_i(b) = k \sum_{b} b + \frac{k(k-1)}{2}. \end{aligned}

两个等式的右侧都与 $i$ 无关。因此周期均值满足

\bar y_j - \bar y_i = \mu_j - \mu_i + (\bar\varepsilon_j - \bar\varepsilon_i),

不受位置效应和线性漂移影响。使用 FixedOrder 时，每个区组中都有 $p_i(b) = i$ ，差值将永远带有偏差 $\tau_j - \tau_i + \delta (j - i)$ 。

对完整周期上的均值而言，抵消是精确的；请把 $E + C$ 选为 $k$ 的倍数，使从区组 $E$ 开始继续轮换的验证性阶段覆盖完整的周期。成对差值的中位数是稳健的，而不是精确无偏的：每个区组的偏差 $\tau_{p_j(b)} - \tau_{p_i(b)} + \delta (p_j(b) - p_i(b))$ 以相同的频率取其 $k$ 个值中的每一个，当 $k = 2$ 时它在 $+c$ 和 $-c$ 之间交替。

批次校准

计时器具有分辨率 $\rho$ 和启动/停止开销 $\omega$ 。一个实际耗时 $T(n)$ 的 $n$ 次迭代批次被读作 $\hat T = T(n) + \omega + q$ ，其中 $\lvert q\rvert \le \rho$ ，运行器报告 $\hat T / n$ 。每次迭代时间的相对误差至多为

\frac{\omega + \rho}{T(n)} ,

它随批次增大而减小。校准选择 $n$ ，使 $T(n)$ 达到 target_batch_time_us $= t$ 。从 $n_0 = \min(\max(\text{min\_batch\_iterations}, 1), \text{max\_batch\_iterations})$ 开始，只要批次有效、 $T(n) < t$ 、 $T(n) <$ max_sample_time_us 且 $n <$ max_batch_iterations，下一个批次大小为

n_{j+1} = \min\Bigl(n_{\max},\ \max\Bigl(n_j + 1,\ \Bigl\lceil \frac{n_j\, t}{T(n_j)} \Bigr\rceil\Bigr)\Bigr),

当测得的时间为 $0$ 时，用 $10\, n_j$ 代替该比值。

线性代价。 若 $T(n) = c\,n$ ，第一次更新给出 $n_1 = \lceil t / c\rceil$ 且 $T(n_1) \in [t, t + c)$ ：一次重试就足够。

仿射代价。 若 $T(n) = a + c\,n$ ，其中每批次固定代价 $a > 0$ ，则更新就是 $f(n) = n t / (a + c n)$ 的不动点迭代。其不动点满足 $a + c n^* = t$ ，因此 $n^* = (t - a)/c$ ，且

f'(n) = \frac{a\, t}{(a + c n)^2}, \qquad f'(n^*) = \frac{a}{t} < 1 .

该迭代在 $n^*$ 附近以速率 $a/t$ 收缩：当固定代价为目标的 10 % 时，每次重试都把剩余差距缩小到十分之一。由于每一步至少使 $n$ 增加一，且 $n$ 以 max_batch_iterations 为上限，循环最多经过 $n_{\max} - n_0$ 次重试就会终止。

使用 QuickCheck 预设（ $t = 1000$ µs）和 1 µs 的计时器时，校准后批次的量化误差至多为 $0.1\,\%$ 。在浏览器中，performance.now() 的精度可能被降低到 100 µs 或更粗；请相应提高目标值。

设计决策

先验证再计时

问题。 一个又快又错的答案绝不能看起来像是加速。方案。 在计时循环内验证；事后验证；事先验证。选择。 对每个数据集，运行器先从新的 clone_input/prepare 和 initial_context 出发，为每个实现运行一个包含 sequence_length 次操作的验证序列，并与判定器比较。之后才开始计时。理由。 在计时内验证会把验证也计入时间；事后验证则无法把失败的输入展示在测量旁边。序列在步骤之间传递 next_context，因此有状态的操作（累加器、舍入模式、解析器状态）会按照与测量时相同的顺序被验证。

在调用判定器之前，运行器会对不是值的执行结果进行如下映射：

实现的结果	验证状态
`Unsupported(reason)`	`Unsupported(reason)`
`ParseFailure`, `Aborted`, `Timeout`	`InfrastructureFailure(...)`
`ExpectedDifference(reason)`	`ExpectedDifference(reason)`
`Value`, `RaisedFlags`, `Trapped`	由判定器决定

对于关系判定器，每个无序实现对 $i < j$ 都会逐步比较；事件归于该对中的第二个实现。提前结束的序列（next_context = None）只在双方都产生了结果的步骤上比较。Invalid 和 InfrastructureFailure 计为失败；失败会触发缩减器（若已配置），并发出一个带有种子、两个指纹、缩减路径和最小输入的 ValidationFailure。

失败不会中止测量。报告会移除失败实现在该数据集上的系列，并改为显示不匹配。

平衡的、带种子的轮换，而非随机化

问题。 位置效应和漂移效应会使固定顺序产生偏差。方案。 固定顺序；每个区组一个独立的随机排列；循环拉丁方。选择。 上文推导的循环轮换，加上带种子的偏移量。理由。 随机排列只在期望意义上平衡位置；在十个区组和三个实现的情况下，某个实现很容易有四次排在第一。轮换在每个周期上都精确地平衡位置，而种子仍决定由哪个实现开始。

校准批次，默认每个实现各自一个批次大小

问题。 单次操作太短，无法计时。选择。 每个实现分别校准（BatchPolicy::PerImplementation），使每个实现都达到目标时长。对于每批次工作量必须完全相同的实验，BatchPolicy::SharedBatchSize 把所有批次大小替换为其中的最小值 $n = \min_i n_i$ ，代价是较慢的实现的批次更短、相对计时误差更大。每次迭代的值 $\hat T / n$ 是一个批次均值：批次把独立的每次迭代噪声的方差缩小 $n$ 倍，但也把批次内部的尾部掩盖了。

显式的计时边界

时钟是 @bench.monotonic_clock_start/monotonic_clock_end（µs）。它包住哪些内容取决于夹具的 SetupPolicy：

准备	`ExcludedFromMeasurement`	`IncludedInMeasurement`
`PerRun`, `PerDataset`, `PerImplementation`	准备一次并缓存；每个批次：启动， $n \times$ （执行，折叠），停止	与排除时相同，只是那一次性的准备会落在第一个运行的批次（通常是预热批次）的计时区域内
`PerSample`, `PerBatch`	准备；启动； $n \times$ （执行，折叠）；停止；重置	启动；准备； $n \times$ （执行，折叠）；重置；停止
`PerIteration`	$n \times$ （准备；启动；执行；折叠；停止；重置），时间求和	启动； $n \times$ （准备；执行；折叠；重置）；停止

这里的 prepare 包含 clone_input。synchronize 在每次启动之前和每次停止之前立即调用。输出接收器的 finish 和 @bench.Bench::keep 在停止之后、计时之外运行；keep 阻止编译器移除结果未被使用的工作。事件发出从不发生在计时区域内。

排除准备工作的 PerIteration 是有代价的：它每个批次读取 $n$ 次计时器，因此量化误差为 $n\rho / (n c) = \rho / c$ ，不会随批次大小而减小。只对相比计时器分辨率很长的操作使用它。

夹具生命周期与哨兵样本 id

夹具的 prepare 和 reset 会收到一个 SampleContext 或 ResetContext，其 sample_id 告诉夹具运行器正在做什么：

`sample_id`	阶段
`-1`	验证序列
`-1000 - w`	预热批次 $w$
`-3`	预热后的重置（仅限长期存活的准备）
`-2 - r`	经过 $r$ 次重试后的校准批次；`-2` 也用于校准后的重置
`-100000 - r`	探索性区组 $r$
`r`	验证性区组 $r$
`confirmatory_samples`	对缓存的准备值进行最终重置

长期存活的准备（PerRun、PerDataset、PerImplementation）对每个实现和数据集准备一次，在预热后和校准后重置，并在数据集结束时再次重置。运行器为每个实现保留一个缓存，因此 PerRun 和 PerDataset 目前的行为与 PerImplementation 相同。

预热

每个实现都运行单次迭代的批次，直到它运行了 warmup_iterations 个批次并花费了 warmup_time_us，批次数上限为 $\max(\text{warmup\_iterations}, \text{max\_batch\_iterations})$ 。每个实现都适用同样的预热，因此没有哪个实现会因即时编译或缓存而在测量开始时占得优势。

通过子进程工作者隔离崩溃

问题。 一个段错误或陷入死循环的候选会终止整个实验。选择。 Implementation::worker 把每次操作作为子进程运行在一个带强制取消处理器的任务组中，并发地捕获 stdout 和 stderr，并把超时或非零退出转化为一个结果。理由。 结果是数据：它会被计数、报告，并且可以重放。对工作者而言，进程创建是被测操作的一部分，这对正确性语料和不安全代码是可以接受的，但不适用于微基准测试。

种子与身份

运行种子原样通过 GenerationContext(seed, "default", case_id, DatasetKey(scale, index), fixture.id, fixture.version) 到达夹具。请用 @generator.derive_seed 从它派生每个数据集的种子；generator 设计解释了混合方式。同一个种子也设定轮换偏移量。种子与协议、计划和环境快照一起，决定了除计时以外的一切。

正确性与不变量

对每个数据集和实现，验证先于计时。
平衡性。 在每 $k$ 个连续区组中，每个实现在每个位置恰好出现一次（上文已证明）。
每个数据集内的事件顺序。 先是验证和失败，然后每个实现一个校准事件，然后是 $k(E + C)$ 个观测（探索性在前）；摘要在最后一个数据集之后发出一次。
计数。 observation_count $= \lvert\text{scales}\rvert\cdot k (E + C)$ ；calibration_count $= \lvert\text{scales}\rvert \cdot k$ ；validation_count 是被比较的步骤数。
有效性。 当批次中的某次操作没有产生值或结束了上下文序列时，该观测为 valid = false。
终止性。 校准最多进行 $n_{\max} - n_0$ 次重试；预热最多 $\max(\text{warmup\_iterations}, n_{\max})$ 个批次；缩减最多 max_steps 次候选求值。
重置规范。 短期存活的准备值（验证序列、PerSample、PerBatch、PerIteration）恰好被重置一次。缓存的长期存活值在预热后、校准后以及数据集结束时被重置，其间被复用，因此 reset 必须让它保持可复用。

被否决的方案

每个区组一个随机排列。 只在期望意义上平衡。
Williams 设计。 它们还能平衡一阶残留效应（哪个实现刚刚在前面运行过），但对奇数 $k$ 每个周期需要 $2k$ 个区组。循环顺序在区组内总是把实现 $i - 1$ 放在 $i$ 之前。
为每次迭代计时。 对短操作而言，计时器开销和分辨率会占主导；批次可以将其摊销。
区间足够窄时停止。 序贯停止规则会使固定样本区间失效；样本数由协议固定。
计时之后再验证。 这会把错误的结果与本应被丢弃的测量分开。

边界

运行器不绑定线程、不固定 CPU 频率，也不隔离进程；它在 EnvironmentSnapshot 中记录你对这些方面的声明。
experiment_design、outlier_policy、validation_coverage 和 practical_delta_pct 存储在协议中，但不会改变运行。无论覆盖率如何设置，验证都在计时之前对每个数据集运行一次。
它不计算比较或决策；那是 stats 的工作。
它为每个规模物化一个输入；不会为每个区组重新生成输入。
protocol_identity（进而 run_id）只涵盖预热次数、验证性样本数和实际阈值。
子进程工作者需要 native 目标；run 本身需要异步运行时（native、JS 或 wasm，不支持 wasm-gc）。
实现之间的一阶残留效应没有被平衡。