bench 设计

设计目标

floating 中的性能结论必须可复现，且不能与噪声混淆。bench 将 Maremark 框架变成一个小型的、专属于本仓库的工具集：基准是带有正确性预言的不可变规格，每次运行都记录其环境和协议，计时结果采用稳健的配对统计量进行归约，其不确定性以 bootstrap 置信区间报告。测量（计时、流式 JSONL）在各核心的测试包和 tools/benchmark.py 中进行；本包只描述实验并归约其数据。

数学背景

一次观测测量的是什么

Maremark 首先为每个实现和数据集校准批大小：从协议规定的最小迭代次数 $n_0$ 开始，对一个批次计时；当批次时长短于目标批次时间 $T$（Development 预设中为 5 ms，RegressionGate 中为 10 ms）且未达到迭代上限时，按下式重试

$$n_{k+1} = \min\Bigl(n_{\max},\ \max\bigl(n_k + 1,\ \lceil n_k T / t_k \rceil\bigr)\Bigr),$$

其中 $t_k$ 是测得的批次时间。随后，一次观测是对 $n$ 次调用的一个计时批次，记录为每次调用的平均时间 $x = t_{\text{batch}} / n$（单位为微秒）。在批次内取平均可消除时钟粒度的影响；剩余的批次间波动由下文的统计方法处理。

区块与配对

确认阶段由 $m$ 个区块组成（Development 为 $m = 10$，RegressionGate 为 $20$）。在区块 $j$ 中，每个实现各测量一次，$K$ 个实现按循环顺序 $(j + o) \bmod K$ 排列，偏移 $o$ 由种子导出，因此在连续 $K$ 个区块中每个实现排在首位的次数相同。对于基线 $B$ 和候选 $C$，观测按区块排序并配对：

$$d_j = c_j - b_j, \qquad j = 1, \dots, m .$$

缓慢漂移（频率调节、热状态、后台负载）对同一区块的 $b_j$ 和 $c_j$ 影响相近，并在 $d_j$ 中相互抵消。

点估计

记 $\operatorname{med}$ 为样本中位数，

$$\Delta_{\%} = 100 \cdot \frac{\operatorname{med}(d)}{\operatorname{med}(b)}, \qquad \text{speedup} = \frac{\operatorname{med}(b)}{\operatorname{med}(b) + \operatorname{med}(d)} .$$

中位数的崩溃点为 50 %：最多一半的区块可以受到任意干扰（批次被抢占、缺页风暴），而估计值不会被任意移动。这就是 bench 归约对离群值的处理方式：不丢弃任何观测。Maremark 的协议也指定了离群值策略（Development 为 ReportOnly，RegressionGate 为 TukeyFence）；它是所记录的协议标识的一部分，但观测是未经过滤地输出的，本包中的归约也不应用过滤。

判定将 $\Delta_{\%}$ 与实际阈值 $\delta$ 比较：若 $\Delta_{\%} \le -\delta$ 则为 Faster，若 $\Delta_{\%} \ge \delta$ 则为 Slower，否则为 Equivalent。小于 $\delta$ 的差异无论测量得多精确，都被视为无关紧要。

样本分位数

Maremark 使用线性插值分位数（Hyndman 与 Fan 的第 7 型¹1 R. J. Hyndman, Y. Fan, “Sample quantiles in statistical packages”, The American Statistician 50(4), 1996. ）：对于已排序的值 $s_0 \le \dots \le s_{N-1}$ 以及 $f \in [0, 1]$，令 $h = f (N - 1)$，

$$Q(f) = s_{\lfloor h \rfloor} + \bigl(h - \lfloor h \rfloor\bigr) \bigl(s_{\lceil h \rceil} - s_{\lfloor h \rfloor}\bigr),$$

因此 $Q(1/2)$ 就是通常的中位数（$N$ 为偶数时取中间两个值的平均）。

bootstrap 置信区间

$\operatorname{med}(d)$ 的不确定性用百分位 bootstrap²2 B. Efron, R. J. Tibshirani, An Introduction to the Bootstrap, Chapman & Hall, 1993, 第 13 章。 估计。对 $r = 1, \dots, R$：

1. 从 $\{1, \dots, m\}$ 中有放回地均匀抽取 $m$ 个索引 $i_1, \dots, i_m$；
2. 计算重抽样中位数 $\theta^{*}_r = \operatorname{med}(d_{i_1}, \dots, d_{i_m})$。

排序得到 $\theta^{*}_{(1)} \le \dots \le \theta^{*}_{(R)}$。对于置信水平 $c$（百分数），令 $\alpha = (100 - c) / 200$。区间为

$$\bigl[\, L, U \,\bigr] = \bigl[\, Q^{*}(\alpha),\ Q^{*}(1 - \alpha) \,\bigr],$$

其中 $Q^{*}$ 是已排序 bootstrap 中位数的第 7 型分位数。当 $c = 95$、$R = 10\,000$ 时，区间为 $[Q^{*}(0.025), Q^{*}(0.975)]$，即在已排序重抽样的第 $249.975$ 和 $9749.025$ 个位置（从 0 开始）做线性插值。该区间针对的是以微秒为单位（而非百分数）的 $\operatorname{med}(d)$。

随机索引来自 xorshift64* 生成器³3 S. Vigna, “An experimental exploration of Marsaglia’s xorshift generators, scrambled”, ACM TOMS 42(4), 2016. ，以调用者的种子作为种子（零种子会被替换为一个固定常数），索引取状态对 $m$ 的模；取模偏差至多为 $m / 2^{64}$。种子固定时，该区间是数据的确定性函数，因此重新运行分析可以精确复现它。

回归判定

is_significant_regression 要求同时满足

$$\Delta_{\%} \ge \delta \quad\text{and}\quad L > 0 :$$

中位数减速必须具有实际意义，并且中位数配对差的 95 % 区间必须在变慢一侧排除零。第一个条件防止标记微小但测量精确的变化，第二个条件防止标记幅度大但噪声多的变化。

设计决策

使用配对中位数而非均值

计时分布右偏，且偶尔出现较大的离群值。差值的均值和 $t$ 区间会被这些离群值主导；按区块配对的差值的中位数是稳健的，不需要正态性假设，而 bootstrap 无需中位数的方差公式即可给出其区间。

每种用途固定参数

confirmatory_regression 固定 $\delta = 3\,\%$、$R = 10\,000$ 和 $c = 95\,\%$，因此调用者无法削弱回归门槛。paired_hotspot 从调用者获取 $\delta$ 和种子，并使用 $R = 2000$ 生成探索性的热点报告。它以 0.95 传入置信水平；Maremark 将该值解释为百分数，因此它报告的区间是 bootstrap 分布中央的 0.95 %，几乎就是 bootstrap 中位数处的一个点。测试套件只打印由此得到的 $\Delta_{\%}$，不受影响。

按最小中位数自动调优

tune_dataset 以每个候选的有效确认样本的中位数为其评分，返回中位数最小的候选，完全相等时按候选 id 决定。该评分同时作为主准则和次准则传给 @tune.select_best，因此在与最快者相差不超过 $\delta$ 的候选中，次准则最小者胜出，而它仍是最快者；所以实际阈值对选择没有影响。两个候选在不同规模间的交叉点由 Maremark 根据各数据集的标签计算。

带预言的不可变夹具

immutable_bench 对每个规模只生成一次输入，并将每个输出与独立的参考结果核对。计算出错误结果的更快实现会使运行失败，而不是在比较中胜出。

环境即数据

environment 在每次运行中记录目标、配置文件和数据类型标签，并将只有外部工具才知道的信息（机器、频率策略、提交）标记为 external-metadata。这样，阅读两份产物的人就能判断它们的数据是否可比；本包自身不会跨环境比较运行。

正确性 / 不变式

• 归约的确定性。 对于固定的观测和种子，paired_hotspot、confirmatory_regression 和 tune_dataset 每次运行都返回相同的值（按区块 id 排序、带种子的生成器、确定性的平局决胜）。
• 配对。 样本按区块顺序配对。样本数不等是错误（MismatchedPairs），绝不会被静默截断。
• 区间有序性。 $L \le U$，因为 $Q^{*}$ 关于其参数单调，且当 $c > 0$ 时 $\alpha < 1 - \alpha$。
• 尺度不变性。 将所有样本乘以常数 $\lambda > 0$ 会使 $\operatorname{med}(d)$、$L$ 和 $U$ 都乘以 $\lambda$，而 $\Delta_{\%}$、判定和结论保持不变，因此时间单位无关紧要。

被否决的替代方案

• 取平均前丢弃离群值。 任何栅栏都需要一个调节常数，并且会静默改变样本；中位数使其变得不必要。
• 两组样本的非配对比较。 测量 $B$ 与 $C$ 之间的漂移会直接进入差值。
• 基于正态理论的区间。 它们假设误差对称，而计时数据并不具备这一性质。

边界

• 不负责计时、进程控制或文件输出：这些由 Maremark 的运行器和 tools/benchmark.py 完成。
• 没有绝对性能目标；阈值适用于相对差异。
• 性能结果从不改变正确性结论，且基准只在 native 目标上运行。

Footnotes

1. R. J. Hyndman, Y. Fan, “Sample quantiles in statistical packages”, The American Statistician 50(4), 1996. ↩

2. B. Efron, R. J. Tibshirani, An Introduction to the Bootstrap, Chapman & Hall, 1993, 第 13 章。 ↩

3. S. Vigna, “An experimental exploration of Marsaglia’s xorshift generators, scrambled”, ACM TOMS 42(4), 2016. ↩