experiment 设计

设计目标

基准测试比较的是本应计算同一事物的多个实现。experiment 阐明“同一”的含义（判定器），把失败缩小到便于调试的程度（缩减），并判断随规模变化的偏好何时强到足以成为部署规则（交叉点分析）。一切都是显式输入的纯函数。

数学背景

作为关系的判定器

对于输入 $x$ 和第 $k$ 步，参考判定器定义一个期望结果 $e_k(x)$ ，以及针对实际结果 $a$ 的判断 $V(x, k, e, a) \in \text{ValidationStatus}$ 。相等是特例 $V = \text{Valid} \iff a = e$ ；浮点代码通常需要容差 $\lvert a - e\rvert \le \epsilon$ ，而感知 IEEE 的代码还要比较标志。

关系判定器判定一对实现， $R(x, k, a^{(i)}, a^{(j)})$ 。它不需要参考，但只能检测出分歧：如果所有实现都有同一个缺陷，关系仍然成立。运行器检查 $m$ 个实现的全部 $\binom{m}{2}$ 个无序对；当关系是等价关系（例如结果完全相等）时，这些配对虽有冗余但代价低廉，而单个偏离的实现会出现在 $m-1$ 个配对中，因此很容易被识别出来。

作为贪心下降的缩减

设 $C(x)$ 为 $x$ 的候选， $P$ 为失败谓词。shrink 计算

x_0 = x, \qquad x_{j+1} = \text{first } y \in C(x_j) \text{ with } P(y),

并在没有候选满足 $P$ 时，或在对 $P$ 求值 max_steps 次之后停止。

终止性。 内层循环的每次迭代对 $P$ 求值一次并使计数器加一；当计数器达到 max_steps 或某次迭代什么也没接受时，外层循环停止。即使 $C$ 有环，最多也只发生 max_steps 次求值。
不变量。 若 $P(x_0)$ 成立，则对每个被接受的 $x_j$ ， $P(x_j)$ 都成立，因为只有当 $P$ 对某个候选成立时它才会被接受。因此结果仍然是一个失败的输入。（shrink 不测试 $x_0$ 本身。）
局部极小性。 如果循环因没有候选失败而停止，结果就是一个局部极小： $C(\text{result})$ 中没有元素满足 $P$ 。如果因预算耗尽而停止，则未必如此。

取 $C(n) = [\lfloor n/2\rfloor, n-1]$ 和阈值谓词 $P(n) = (n \ge t)$ ，下降过程在可以时减半，然后逐一递减，在 $O(\log n + t)$ 个被接受的步骤内恰好到达 $t$ 。

交叉点检测

设 $s_1 < s_2 < \dots < s_N$ 为排好序的规模， $\ell_i \in \{A, B, \text{Unknown}\}$ 为 $s_i$ 处的判定结果。转变的次数为

T = \bigl\lvert\{\, i \in \{2, \dots, N\} : \ell_{i-1} \ne \ell_i,\ \ell_{i-1} \ne \text{Unknown},\ \ell_i \ne \text{Unknown} \,\}\bigr\rvert .

如果相对差值 $r(s)$ 关于规模单调，则标签 $\text{label}(r(s_i))$ 构成单调序列 $A \dots A\, U \dots U\, B \dots B$ （或其逆序），因此表现良好的偏好至多有一次转变。 $T = 1$ 给出唯一那次转变的分界 $(s_{i-1}, s_i)$ ； $T > 1$ 意味着偏好翻转了不止一次，无法用单个阈值表达； $T = 0$ 意味着不存在一对相邻的、确定且不同的标签。

comparator_label(r, t) 用与 stats 相同的阈值规则把相对差值映射为标签：若 $r \le -t$ 则为 $A$ ，若 $r \ge t$ 则为 $B$ ，否则为 Unknown。宽度为 $2t$ 的 Unknown 带防止 $r = 0$ 附近的噪声产生虚假的转变。

设计决策

判定器是值

问题。 每个用例都需要自己的正确性概念。选择。 判定器是带 id 的函数记录。理由。 它们可以捕获容差和上下文，在每个验证事件中都有名字，并且可以内联构建。

到达判定器的是结果，而不只是值

判定器看到的是 ExecutionOutcome，因此它可以接受有文档记录的 ExpectedDifference、比较引发的标志，或者要求两侧都触发陷阱。运行器在调用判定器之前会预先分类工作进程崩溃、超时、解码错误和 Unsupported，因此判定器只判定真实的结果。

贪心的首次改进式缩减

方案。 穷举搜索最小的失败输入；delta 调试；贪心下降。选择。 带显式候选函数和求值预算的贪心下降。理由。 每次求值都可能运行完整的操作序列，因此真正限制代价的是预算；候选函数让用户编码输入的结构（把规模减半、删除一个元素）。被接受的路径会被记录下来，读者可以看到反例是如何得到的。

保守的交叉点

问题。 交叉点会成为部署规则（DeploymentPolicy::Piecewise），并被应用于从未测量过的输入。选择。 只有恰好一次转变时才接受分界；否则报告 NonMonotonic，把策略留给用户。理由。 基于嘈杂、反复翻转的偏好建立的规则只会编码噪声。

正确性与不变量

shrink 最多对谓词求值 max_steps 次，并且只要初始输入满足谓词，就返回一个满足它的输入。
只有恰好存在一次转变时，crossover_from_labels 才返回 Found，其分界由该次转变的两个相邻规模组成。
只有当两个结果都是 Value 且被比较器接受时，ReferenceOracle::equal 才返回 Valid。
对于 $t > 0$ ，comparator_label 把实数轴划分为 $(-\infty, -t]$ 、 $(-t, t)$ 、 $[t, \infty)$ 。

被否决的方案

在原始计时上做统计变点检测。 需要噪声模型；而基于实际阈值的标签是可解释的。
对分界进行插值。 两个测量规模之间的规模并未被测量；结果改为给出那两个测量过的规模。
delta 调试。 对序列很强大，但需要固定的输入表示；候选函数更通用。

边界

crossover_from_labels 不对定义域排序，也不使用 ScaleDomain.compare；请传入已排序的值。
跨越 Unknown 标签的转变（A、Unknown、B）不计数，因此这样的序列报告 NoCrossover。
判定器不在这里运行；由运行器运行它们。运行器不使用 ReferenceOracle.sequence_length。
shrink 不检查初始输入是否失败。