📊 statistics

The Right Call for Software Benchmarking: Consistent Decisions in Stateful Environments

本文认为，在自适应机制会使绝对性能测量产生偏差的有状态计算环境中，软件基准测试应当被重新定义为一个决策问题，其核心在于通过旨在获得一致的性能差异估计值而非绝对值的实验设计，来识别出最快的程序。

原作者： Gábor Melis

发布于 2026-06-17

📖 1 分钟阅读☕ 轻松阅读

原作者： Gábor Melis

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你是一名赛车工程师，正试图弄清楚两种新引擎设计中哪一个更快。你把它们带到了赛道上，但出现了一个问题：赛道本身是不可预测的。有时会刮风，有时沥青路面很烫，有时会有流浪狗跑过终点线，有时计时器会出现故障。这些就是论文中提到的“有状态（stateful）”因素——即那些你无法完全控制或预测的事物。

如果你只是运行引擎 A 五次，然后再运行引擎 B 五次，最后取平均值，你可能会得到错误答案。为什么？因为可能在运行引擎 A 时风平浪静，而在运行引擎 B 时却刮起了大风。环境的“噪声”使你的结果产生了偏差。

这篇由 Google DeepMind 的 Gábor Melis 撰写的论文指出，在这样一个混乱的世界里，试图测量单个程序的绝对速度是徒劳的。相反，我们应该停止关注“有多快”，而开始关注“哪一个更快”。

以下是该论文的核心内容，通过简单的概念进行了拆解：

1. 问题所在：“绝对速度”的幻象

论文指出，在现代计算机中，试图测量一个程序运行时间的完美、绝对数值，就像是在测量一个站在蹦床上的人的精确高度一样，而蹦床本身是在跳动的。环境（蹦床）会根据之前发生的事情而改变。

陷阱： 如果你先测量程序 A，然后再测量程序 B，计算机的“情绪”（缓存、温度、后台任务）可能在两者之间发生了变化。
结果： 你的测量结果会产生偏差。你无法信任那些绝对数值。

2. 解决方案：“面对面”竞赛（差值/Delta）

与其问“程序 A 有多快？”（这很难），不如问“程序 A 是否比程序 B 快？”（这更容易）。

类比： 想象两名跑者在泥泞的赛道上跑步。如果泥泞变得更深了，两名跑者都会变慢。如果你分别测量他们，你可能会因为第二个跑者时泥泞变深了而认为第二个跑者更慢。但如果你让他们同时进行（或者进行一场紧密交替的比赛），泥泞会对他们产生同等的影响。即使绝对时间很混乱，他们之间的差异依然是清晰可见的。
论文的观点： 通过关注在同一次实验中测得的两个程序之间的差异（即“delta”），环境噪声会被抵消。你不需要知道为什么计算机变慢了，你只需要知道它对两个程序来说都同样变慢了。

3. 策略：“分组（Block）”对比“随机化（Shuffle）”

论文测试了两种进行这种“面对面”比赛的方法，以确保“泥泞”不会欺骗你。

“分组”法（旧方法）： 你运行程序 A 10 次，然后运行程序 B 10 次。
- 缺陷： 论文表明这种方法存在风险。如果计算机的状态发生缓慢变化（例如赛道随时间推移逐渐变热），程序 A 可能会得到一个“凉爽”的开始，而程序 B 则会得到一个“炎热”的结束。即便你运行一百万次，这种偏差也不会消失。这就像是在早上让第一个跑者跑，然后在中午让第二个跑者跑。
“随机化”法（新方法）： 你为每一次运行抛掷硬币。正面：运行 A。反面：运行 B。
- 优势： 这是论文的大力推荐。通过随机混合这些运行过程，你可以确保任何环境“噪声”（比如突然的温度升高）对两个程序的影响大致相等。即使噪声非常狡猾并试图作弊，随机混合也会让噪声无法一致地偏袒其中一个程序。

4. 保障：“我们知道自己是对的”

论文不仅仅是说“尝试这样做”，它还使用数学证明了，如果你使用这种随机混合方法：

一致性： 如果你运行实验足够长的时间，无论计算机多么混乱，你最终都会找到真正的赢家。
有限预算： 你不需要无限的时间。论文提供了一种方法，可以让你计算出需要进行多少次运行，才能达到比如 95% 的把握确定程序 A 比程序 B 快。

5. 关于其他方法

论文还研究了人们衡量软件的其他流行方法，例如“配对基准测试（paired benchmarking）”（运行 A 然后 B，再运行 A 然后 B）或使用像 Google Benchmark 这样的库。

结论： 这些方法可能会减少数值中的“抖动（jitter）”（方差），让结果看起来更平滑。然而，论文认为它们并没有解决**偏差（bias）**问题。由于它们没有考虑到计算机状态的长期漂移，它们仍然可能选错赢家。随机混合法是唯一被证明在数学上能对抗这些隐藏“诡计”的方法。

总结

把软件基准测试想象成在一间灯光不断闪烁的房间里玩“石头剪刀布”。

旧方法： 测量玩“石头”用了多久，然后再测量玩“剪刀”用了多久。闪烁的灯光可能会让“剪刀”看起来更慢，仅仅是因为那个时刻灯光不好。
新方法（本论文）： 在同一轮中同时玩“石头”和“剪刀”，并随机切换谁先出招。闪烁的灯光对两者的影响是平等的。即使你无法准确判断这一轮到底用了多久，你也能清晰地看出谁赢得了这一轮。

论文的结论是，为了构建更好的软件（如编译器或数据库），我们必须停止追求完美的绝对数值，而开始使用这些“随机化的面对面”竞赛来寻找真正的赢家。

技术摘要：软件基准测试的正解

1. 问题陈述

现代计算系统高度依赖状态化机制（例如 CPU 热节流、缓存状态、操作系统调度和并发工作负载）来优化性能。虽然这些机制提高了效率，但它们在连续测量之间引入了时间依赖性。因此，不受控的环境状态产生了一个“混杂因素”，使得对程序绝对性能（例如平均运行时间）的朴素估计器产生偏差且不一致。

本文认为，在这样的状态化环境中，要在不建立强有力的（通常是无法验证的）关于底层环境动力学假设的情况下，估计单个程序的绝对损失（代价）在理论上是难以实现的。依赖于绝对数值或简单平均值的传统基准测试方法会失效，因为不受控的状态 $U$ 以无法建模或控制的方式影响测量结果，从而导致误导性的优化决策。

2. 方法论与框架

2.1 将其形式化为决策问题

作者将软件基准测试重新定义为一个决策问题，而非绝对性能的估计问题：即在给定配置 $c$ 下，识别集合 $\mathcal{F}$ 中最快的程序。

目标： 寻找 $\arg \min_{f \in \mathcal{F}} l(f)$ ，其中 $l(f)$ 是期望损失。
核心洞察： 虽然估计绝对损失 $l(f)$ 会受到不受控状态的偏差影响，但估计两个程序之间的性能差（delta） $\delta(f, g) = l(f) - l(g)$ 可以是无偏的，前提是环境噪声对两个程序的影响是相似的。这依赖于一个 ceteris paribus（“其他条件不变”）的假设：不受控的噪声以加性方式（或在对数空间中以乘性方式）且一致地影响集合中的所有程序。

2.2 测量模型

本文提出了一个生成模型：

一个不受控的状态 $U$ 随时间演化。
根据先前的观测结果选择一个程序 $F_i$ 。
观测到的运行时间 $T_i$ 是真实运行时间与当前不受控状态的函数。
状态 $U$ 是不可观测的，且其分布是未知的。

2.3 实验设计

为了实现对差值（delta）的一致估计，本文提出了两种主要的实验设计，利用对称性来抵消偏差：

差值设计 ( $\mathcal{D}_\Delta$ )： 一类通用的设计，其中下一个程序的选择仅取决于之前的选择（而非不可观测的状态），并且为所有程序分配非零概率。
分块实验 ( $\beta$ )： 程序在块中运行，每个程序在块内出现的次数相等（不放回采样）。本文分析了单块和多块设计。
- 发现： 固定块大小可能会导致渐近偏差，因为执行顺序与演化的状态之间存在相关性。
- 解决方案： 需要使用增长型块大小（即块大小随总运行次数增加）来确保渐近一致性和消除偏差。
简单随机化实验 ( $\alpha$ )： 每个运行阶段独立且均匀随机地选择程序（有放回采样）。
- 发现： 即使在存在对抗性、自相关环境噪声的情况下，该设计也能实现最优的渐近收敛速率 $O(n^{-1/2})$ ，且无需复杂的分块结构。

2.4 决策规则

本文定义了一个决策规则：如果估计的差值 $\hat{\delta}(f^*, g)$ 对于所有竞争者 $g$ 都足够为负，则选择程序 $f^*$ 。

该规则使用对抗性噪声包络（adversarial noise envelopes）来提供有限样本保证，而不假设特定的噪声分布。
它区分了“事前”（频率派）和“事后”（贝叶斯派）视角，采用了频率派的前验方法，以确保对未知环境动态的鲁棒性。

3. 核心贡献

将基准测试形式化为决策问题： 本文在通用的、难以处理的测量模型下，将基准测试任务形式化为寻找最快程序的问题，将重点从绝对估计转向相对决策。
绝对性能的“幻象”： 本文证明，在状态化环境中，一致地估计绝对性能数值需要极其苛刻的假设（例如状态的平稳分布、零均值随机游走）。
基于差值（Delta）的方法论： 提倡关注性能差异 ( $\delta$ ) 而非绝对值。在不受控状态对所有程序产生一致影响的假设下，程序特有的偏差会在差值计算中抵消。
具有保证的实验设计：
- 引入了分块和简单随机化设计，这些设计可以实现对比值的一致估计。
- 证明了简单随机化设计 ( $\alpha$ ) 达到了最优的渐近收敛速率 ( $O(n^{-1/2})$ )，并且对对抗性噪声具有鲁棒性。
- 分析了分块设计 ( $\beta$ )，指出虽然它们可以降低方差，但需要增长型块大小才能避免渐近偏差。
有限样本保证： 本文通过动态规划（DP）公式和解析近似（鞅近似和非对称近似）来计算在给定置信水平下检测特定性能差异所需的最小运行次数。

4. 结果与验证

理论界限： 作者证明了对于简单随机化设计，噪声差 $\bar{E}_f - \bar{E}_g$ 为 $O_p(n^{-1/2})$ ，尽管存在状态化、相关的环境噪声，这仍与独立噪声的速率一致。
偏差分析： 研究表明，在某些场景下（例如当不受控状态取决于程序序列时），固定块大小的设计会产生渐近偏差。增长型块大小是消除此类偏差的必要条件。
实证验证：
- 本文将解析近似值与用于最坏情况置信度的动态规划（DP）模拟进行了对比验证。
- 结果显示，在双程序案例中，非对称近似比鞅近似提供了更紧致的界限。
- 实验证实了 $O(n^{-1/2})$ 的缩放关系：将检测阈值减半大约需要将运行次数增加到原来的四倍。
- 简单随机化 ( $\alpha$ ) 设计在较低的检测阈值下，通常能以比分块 ( $\beta$ ) 设计更少的运行次数获得非零置信度，因为后者容易受到固定块结构中可利用信息的攻击。

5. 意义与主张

本文声称为状态化环境下的有限预算基准测试提供了一种鲁棒的方法论。通过优先考虑性能差异而非绝对度量，并利用特定的实验设计（特别是简单随机化），开发者可以：

做出一致的决策，确定哪个程序更快，即使底层的环境动态是未知且不可控的。
在有限样本范畴内获得决策的概率保证，从而避免被有偏的绝对估计器所误导。
加速性能敏感型软件（编译器、机器学习框架、数据库）的开发，通过可靠地检测那些被系统状态噪声掩盖的微小性能差异。

作者明确指出，其方法并不试图逆向工程复杂的系统动态（如热控制器），而是利用对称性和随机化使这些动态变得无关紧要，从而实现“哪个更快”的决策。作者承认，虽然该方法提高了样本效率和决策可靠性，但它依赖于这样一个假设：即不受控状态对比较集中的所有程序产生相似的影响；如果该假设被违反（例如，程序与硬件之间存在特定的交互），则需要额外的控制措施。