旭穹の陋室

获得准确的结果

某个算法有两个库实现并不罕见，每个库都维护自己的基准测试代码，并且每个库都声称比另一个更快。这让所有相关人员都感到困惑，尤其是不得不在两者之间做出选择的用户。

这种情况通常不是由作者的欺诈行为造成的；他们只是对“更快”的含义有不同的定义，事实上，只定义和使用一个性能指标往往是非常有问题的。

测量正确的事情

有很多事情会在基准测试中引入误差。

不同的数据集

许多算法的性能在某种程度上取决于数据集的分布。例如，为了定义什么是最快排序、最短路径或二分查找算法，你必须修正运行该算法的数据集。

这有时甚至适用于处理输入相对单一的算法。例如，向GCD实现提供顺序的数字不是一个好主意，因为它使分支非常容易预测：

// don't do this
int checksum = 0;

for (int a = 0; a < 1000; a++)
    for (int b = 0; b < 1000; b++)
        checksum ^= gcd(a, b);

然而，如果我们随机采样相同范围的数字，分支预测会变得更加困难，基准测试也需要更长的时间，因为尽管处理了相同的输入，但顺序发生了变化：

int a[1000], b[1000];

for (int i = 0; i < 1000; i++)
    a[i] = rand() % 1000, b[i] = rand() % 1000;

int checksum = 0;

for (int t = 0; t < 1000; t++)
    for (int i = 0; i < 1000; i++)
        checksum += gcd(a[i], b[i]);

尽管在大多数情况下，最合乎逻辑的选择是随机均匀地对数据进行采样，但许多现实世界的应用的分布远非均匀，因此不能只选择一个数据集。一般来说，一个好的基准测试应该是特定于应用的，并使用尽可能代表真实用例的数据集。

一些算法设计问题有不止一个关键目标。例如，哈希表除了与密钥的分布高度相关之外，还需要小心地平衡以下目标：

• add query 的延迟
• positive membership query的延迟
• negative membership query 的延迟

在哈希表实现之间进行选择的唯一方法是尝试并统计多个待考察变量（variants）。

延迟vs吞吐量

人们经常忽略的另一个方面是，执行时间是可以用多种方式定义，即使是一个查询。

当你编写这样的代码时：

for (int i = 0; i < N; i++)
    q[i] = rand();

int checksum = 0;

for (int i = 0; i < N; i++)
    checksum ^= lower_bound(q[i]);

然后对整个过程计时，并将其除以迭代次数，实际上就是在测量查询操作的吞吐量（throughout）——每单位时间可以处理多少操作。由于循环迭代的交错执行，这通常小于单独处理一个操作所实际花费的时间。

要测量实际延迟，你需要在调用之间引入一个依赖关系：

for (int i = 0; i < N; i++)
    checksum ^= lower_bound(checksum ^ q[i]);

这通常在分析可能存在流水线停滞问题的算法中能发挥很大的作用，例如，在比较分支和无分支算法时。

另一个误差来自是冷缓存效应（cold cache effect），即由于所需数据尚未在缓存中，最初的内存读取需要更长的时间。

这可以通过在开始测量之前进行预热（warm-up）来解决：

// warm-up run

volatile checksum = 0;

for (int i = 0; i < N; i++)
    checksum ^= lower_bound(q[i]);


// actual run

clock_t start = clock();
checksum = 0;

for (int i = 0; i < N; i++)
    checksum ^= lower_bound(q[i]);

如果预热比只是计算某种校验和这种方式更复杂，那么将其与答案验证相结合有时也很方便。

有时基准测试是完全错误的，因为编译器只是优化了基准代码。为了防止编译器偷工减料，你需要添加校验和并将其打印到某个地方，或者添加volatile限定符，这也可以防止任何形式的循环迭代交错执行。

对于只写数据的算法，可以使用__sync_synchronize()intrinsic函数添加内存栅栏（或称内存屏障，是一种同步机制，确保在这个屏障之前的所有内存访问（读取和写入）都在这个屏障之后的内存访问之前完成。这在多处理器环境中非常有用，可以防止因处理器的重排序造成的问题），防止编译器进行累积更新优化（即收集或者说累积多个写操作并且只进行一次实际的写操作）。

我们所描述的问题会在测量中产生偏差（bias）：它们会使得一种算法总是优于另一种算法。基准测试还可能有其他类型的问题，导致不可预测的倾斜或完全随机的噪声，从而增加方差（variance）。

这些类型的问题是由副作用（side effects）和某种形式的外部噪声引起的，主要是嘈杂的邻居（可能是指其他可能影响性能的程序或进程）和CPU动态调频：

• 如果你对计算密集型算法进行基准测试，请使用perf stat以时钟周期为单位测量其性能：这样，它将独立于时钟频率，而时钟频率的波动通常是噪声的主要来源。
• 否则，将核心频率设置为你期望的频率，并确保其不会被干扰。在Linux上，你可以使用cpupower来实现这一点（例如，sudo cpupower frequency-set -g powersave将其设置为最小值，或者sudo cpupower frequence-set -g ondemand启用睿频）。我使用了一个方便的GNOME shell扩展，它可以使用单独的按钮来设置。
• 如果适用，关闭超线程功能，并将任务固定到特定的核心。确保系统上没有其他任务在运行，关闭网络，并尽量不要摆弄鼠标。

你不能完全消除噪声和偏差。甚至程序的命名都可以影响其运行速度：可执行文件的名称最终会在环境变量中，环境变量又会在调用栈中，由此，名称的长度会影响栈的对齐，可能导致由于跨缓存线（cache line）或内存页面（memory page）边界而导致数据访问速度变慢。

在进行优化指导，尤其是向他人报告结果时，考虑噪声的因素很重要。除非你预期有两倍的提升，否则应该像进行A/B测试（是一种数据驱动的决策制定方式，通过对比两个或多个版本的结果，选取效果最好的版本）一样对待所有的微基准测试。

当你在笔记本电脑上运行一个不到一秒的程序时，性能有±5%的波动是完全正常的。因此，如果你想决定是否应该撤销或保留一个可能的+1%的改进，你需要反复运行它直到达到统计显著性（statistical significance）。这可以通过计算方差（variances）和p值（p-values）来确定。

感兴趣的读者可以探索Dror Feitelson的实验计算机科学资源的综合列表，也可以从Todd Mytkowicz等人的 “Producing Wrong Data Without Doing Anything Obviously Wrong” 开始。

你可以点击链接观看由Emery Berger进行的关于如何进行统计上合理的性能评估的精彩演讲。