基准测试：我何时可以停止测量？

Question

基准测试：我何时可以停止测量？

9

我有一系列的函数，它们都旨在完成相同的任务。相同的输入产生相同的输出，但执行所需时间因函数而异。我想确定哪一个是“最快的”，并且我希望对我的测量结果有一定的“统计显著性”。

查阅维基百科和互联网告诉我，统计显著性意味着通过p值阈值使测量或一组测量与零假设不同。这在这里如何应用？函数A比函数B更快的零假设是什么？

一旦我定义好了整个设置，我该如何确定何时停止测量？通常会看到基准测试运行三次，然后报告平均值；为什么不是五次或七次？根据this page on Statistical Significance（我承认我没有完全理解），费舍尔使用8作为他需要用98％的置信度来测量某些东西的样本数量；为什么是8？

- mmr

5个回答

4

您提出了两个问题：

1. 如何进行统计显著性测试，以确定函数A的平均时间是否大于函数B的平均时间？ 2. 如果您想要一定的置信度来回答这个问题，需要采集多少样本？

对于第一个问题，最常见的答案是计算置信区间或执行t检验。这与任何其他具有随机变化的科学实验没有什么不同。要计算函数A的平均响应时间的95％置信区间，只需取平均值并将标准误差乘以1.96加到两侧即可。标准误差是方差除以N的平方根。也就是说，

95% CI = mean +/- 1.96 * sqrt(sigma2/N))

其中sigma2是函数A速度的方差，N是您用于计算平均值和方差的运行次数。

您的第二个问题涉及统计功效分析和实验设计。您描述了一个连续的设置，要询问是否继续采样。顺序实验的设计实际上是统计学中非常棘手的问题，因为通常情况下，您不允许计算置信区间或P值，然后在未达到所需显着性水平的前提下进行附加采样。如果您希望这样做，最好设置一个贝叶斯模型，并计算速度A大于速度B的后验概率。然而，这是非常过度的。

在计算环境中，通常很容易实现非常小的置信区间，因为绘制大N很容易，并且方差通常很小--一个函数显然获胜。

考虑到维基百科和大多数在线资源在统计方面仍然很糟糕，我建议购买 Introductory Statistics with R。您将学习统计学和应用所学工具。

- Tristan

谢谢提供的参考！但是假设我已经取了N个样本。我能否为从N中抽取的任意三次运行计算CI，然后为任意四次运行，然后为任意五次运行等等，直到N，以确定我是否已经达到阈值？从你的话来看，“您不允许计算置信区间或p值……”但如果我已经收集了数据，那可以吗？为什么我不能只检查我已有的数据，看看我是否需要继续？ - mmr

1

在某些预测试数据上进行任何你想要的操作是完全可以的，你可以试着玩一下，看看什么样的N会给你想要的置信区间类型。但是，当你计算最终的置信区间时，你不能基于一个N是该特定样本的特征函数（即N-1先前观察值的平均值）的样本。需要牢记的问题是：我用来选择N的过程是否能导致与N个随机抽样等效的结果？例如，将N增加到CI小于1总是创建小于1的CI，而随机抽样N不会这样。 - Tristan

1

你真的关心统计显著性还是普通显著性？最终，你可能需要在可读性与性能之间做出判断 - 统计显著性并不能真正帮助你。

我使用的一些经验法则：

在可能的情况下，测试足够长的时间，使你有信心小的波动（比如其他事情短暂地中断了你的测试）不会产生太大影响。通常我认为30秒就足够了，但这取决于你的应用程序。测试时间越长，测试结果就越可靠 - 但显然你的结果会延迟 :)
多次运行测试可能是有用的，但如果你计时足够长的话，那么它就不像我认为的那么重要了。它可以减轻其他形式的错误，使得一个整个测试花费的时间比应该花费的时间更长。如果测试结果看起来可疑，当然要再运行一次。如果你看到不同运行的结果明显不同，那就运行几次，并尝试发现规律。

- Jon Skeet

我非常关注统计显著性；我想要用数字信心来说明，在给定的计算机设置上，这个函数或方法比那个方法更快。对于你的测试，为什么是30秒？这个数字从哪里来？基于经验的直觉？而且你说“再运行几次”——多少次？有某种公式，还是只是一个草率的估算？ - mmr

1

如果区别不是绝对明显的话，就选择更易读的版本。那几乎总是最好的方法。至于30秒 - 是的，基于经验的直觉。至于“还要多少次” - 直到你得到一组看起来合理的数字为止。所有这些都只是基于直觉感觉而言。 - Jon Skeet

2

+1 关于绝对明显的差异。在统计学中，我们称之为“眼内敲击测试”（又称“它直接打在你的眼睛之间”）。 - MusiGenesis

1

你引用的研究听起来更像是一个高度控制的环境。这只是一个纯实用的答案，已经一次又一次地证明其在性能测试中的有效性。

如果你正在对现代、多任务、多核计算环境中的代码进行基准测试，那么为了获得有用的基准测试结果，所需迭代次数随着要测量的操作时间的缩短而增加。

因此，如果你有一个需要 ~5 秒钟的操作，通常需要 10 到 20 次迭代。只要迭代之间的偏差保持相当恒定，那么你的数据就足够可靠，可以得出结论。通常你需要丢弃前两个迭代，因为系统通常会预热缓存等等。

如果你正在测试毫秒级别的东西，你需要成千上万次的迭代。这将消除其他进程等产生的噪音。

一旦你达到亚毫秒级别——10 纳秒级别——你需要数百万次的迭代。

虽然不完全科学，但在现代计算系统上进行“真实世界”的测试也是如此。

在比较结果时，考虑执行速度的差异百分比，而不是绝对值。小于 5% 的差异几乎可以忽略不计。

- bbum

但是为什么是10到20呢？这些数字从哪里来的？有公式吗，还是你只是猜测？为什么噪声是5%，而不是与速度的标准偏差相关的值？ - mmr

0

你试图回答的根本问题是，你观察到的事件有多大可能性是偶然发生的？这个硬币公平吗？扔一次：正面朝上。不公平，它总是正面朝上。错误的结论！扔10次，得到7个正面朝上，现在你得出什么结论？1000次，700个正面朝上？

对于简单的情况，我们可以想象如何确定何时停止测试。但你的情况略有不同——你真的在进行统计分析吗？

你对测试有多少控制？重复测试是否增加了任何价值？你的计算机是确定性的（也许）。爱因斯坦对疯狂的定义是重复某事并期望不同的结果。所以当你运行你的测试时，你会得到可重复的答案吗？如果你做的测试足够好，我不确定统计分析是否有帮助。

对于你正在做的事情，我认为第一件关键的事情是确保你真的在测量你认为的东西。运行每个测试的时间足够长，以隐藏任何启动或关闭效应。有用的性能测试往往会运行相当长的时间，因为这个原因。确保你实际上没有在测试工具中测量时间，而是在你的代码中测量时间。

你有两个主要变量：在一个测试中运行你的方法的迭代次数？运行多少次测试？

维基百科说：

除了表达人口的变异性外，标准差通常用于衡量统计结论的置信度。例如，民意调查数据中的误差范围是通过计算如果进行多次相同的调查结果的预期标准偏差来确定的。报告的误差范围通常约为标准差的两倍。

因此，如果您的目标是确保一个函数比另一个函数更快，您可以运行每个函数的多个测试，计算平均值和标准差。我预计，如果您在任何一个测试中的迭代次数很高，则标准差将很低。

如果我们接受误差范围的定义，您可以看到两个平均值是否比它们的总误差范围更远。

- djna

每次我运行测试时，速度的数字都会略有不同。这就是基准测试的方式——现代计算机环境是不受控制的，正如其他人已经指出的那样。因此，运行相同的测试两次将给出不同的速度答案，但不会得到不同的结果。 - mmr

我已经更新了答案，建议查看标准差。 - djna

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MusiGenesis · Accepted Answer

我不建议将统计原理应用于基准测试结果。一般而言，“统计学显著性”这个术语是指你的结果在意外情况下产生的可能性，并且不能代表真实值的准确评估。在统计学中，由于简单概率，随着测量次数的增加，结果偶然出现的可能性逐渐降低。在计算机代码基准测试中，可以简单地增加试验次数（统计学中的“n”），以使偶然结果的可能性低于您定义的任何任意阈值（统计学上的“alpha”或统计学显著水平）。

为了简化：通过运行您的代码大量次数来进行基准测试，不必担心统计测量问题。

注意：这个答案有点简化了此事，旨在以易懂的方式阐明概念。评论如“你显然不懂统计学”将导致残酷的打击。请记得礼貌待人。