如何准确测量排序算法的性能

Question

我在C中有很多排序算法，我想对其进行基准测试。我对这样做的良好方法感到关切。可能影响基准测试性能的因素包括(但不限于)：具体的实现编码、编程语言、编译器(和编译器选项)、基准机以及关键的输入数据和时间测量方法。如何将上述变量对基准结果的影响降到最低？

为了给您举几个例子，我考虑了两种不同语言上的多个实现，以调整前两个变量。此外，我可以在相当普通的(和指定的)参数上用不同的编译器编译代码。现在我将在我的机器上运行测试，它的特点是涡轮增压和诸如此类的东西，并且经常促进核心运行的东西到月球。当然，我将禁用该功能，并执行多次运行，并可能使用它们的平均完成时间进行调整。关于输入数据，我将采取不同的数组大小，从非常小到相对较大。我不知道理想的增量应该是什么样子，以及元素的范围应该是什么。此外，我认为应该允许重复的元素。

我知道对算法的理论分析是所有这些方法的原因，但是我用实际的基准来补充我的研究是至关重要的。一旦收集到数据，您将如何解决上述问题，并对这些变量进行调整？我对我正在使用的技术很满意，但对于研究某一主题的严格方法，我就不那么满意了。谢谢。

Answer 1

您不能对抽象算法进行基准测试，只能对它们的特定实现进行基准测试，这些算法是用特定计算机上运行的特定编译器编译的。

选择几个不同的相关编译器和机器(例如哈斯韦尔、冰湖和/或Zen2，以及苹果的M1，如果你能拿到一个和/或一个AArch64云服务器)并测量你真正的实现。如果您关心像ARM Cortex-A53这样的顺序CPU，也可以在其中一个CPU上进行测量.(使用GEM5或类似的性能模拟器进行仿真可能值得一试。也可能相关的是像Intel Silvermont这样的低功耗实现，它的故障窗口要小得多，但也有一个更短的管道，所以更小的分支误判了惩罚。)

如果某些算法允许在源代码中进行有用的微优化，或者编译器发现，这是该算法的真正优势。

使用您在实践中为您所关心的用例编译的选项，比如clang -O3 -march=native，或者仅仅是-O2。

在云服务器上进行基准测试使您很难/不可能获得空闲系统，除非您为一个巨大的实例支付大量费用，但现代AArch64服务器是相关的，并且可能具有不同的内存带宽比、分支比、错误预测成本与缓存大小和带宽。

(您很可能会发现，在您测试的所有或大多数系统上，相同的代码是最快的排序实现。

是的，各种尺码都很好。

您通常希望使用随机数据进行测试，可能总是从同一个PRNG种子中生成，因此每次都要对相同的数据进行排序。

您可能还想测试一些不寻常的情况，比如已经排序或几乎排序过的情况，因为对于这些情况来说，算法非常快是有用的。

如果您关心对整数以外的事物进行排序，则可能需要使用不同大小的结构进行测试，并以int键作为成员。或者一个做了大量工作的比较函数，如果您想研究如何使用一个不像一个比较机器指令那么简单的比较函数，那么这个比较函数是如何处理的。

与以往一样，在微基准测试中，阵列热身(页面错误)和CPU频率等问题也有很多缺陷。Idiomatic way of performance evaluation?

取其平均完成时间

您可能想要丢弃高离群值，或取中位数，这将对您的影响。通常，这意味着“发生了什么事情”在运行期间，以扰乱它。如果您在相同的数据上运行相同的代码，通常您可以期望相同的性能。(具有页面粒度的代码/堆栈地址的随机化通常不会影响在预测器或数据缓存冲突中相互混叠的分支，但是代码的一个部分中的微小更改可以通过类似于重新编译的效果来改变其他代码的性能。)

如果您想看看当它自己拥有机器时，它将如何运行，那么您不想考虑在其他干扰的情况下运行。如果您试图在“真实世界”云服务器条件下进行基准测试，或者使用其他线程在实际程序中执行其他工作，这就不同了，您将需要找到实际的其他负载，这些负载使用一些共享资源，如L3占用空间和内存带宽。

Answer 2

可能影响基准测试性能的

内容包括(但不限于)：具体的实现编码、编程语言、编译器(和编译器选项)、基准测试机器以及关键的输入数据和时间测量方法。

让我们从一个非常不同的角度来看待这个问题--如何向人类展示信息。

有了两个变量，你就可以得到一个很好的二维结果网格，比如：

        A = 1        A = 2

B = 1   4 seconds    2 seconds

B = 2   6 seconds    3 seconds

这很容易显示，也便于人类理解和得出结论(例如，从我愚蠢的示例表中可以得出两个非常不同的观察结果- "A=1比A=2快一倍(不管B)“和"B=1比B=2快(不管是A)")。

有了3个变量，你得到了一个三维的结果网格，用N个变量，你得到了一个N维的结果网格。人类与“二维屏幕上的三维数据”搏斗，更多的维度成为一场灾难。您可以通过“剥离”一个维度来稍微减轻这一点(例如，您可以显示多个2D网格，而不是试图显示一个3D网格)；但这对人类没有多大帮助。

您的主要目标是减少变量的数量.

为了减少变量的数量：

( a)确定每个变量对于您打算观察的内容有多重要(例如，“哪种算法”将非常重要，而“哪种语言”则不那么重要)。

( b)根据重要性和“逻辑分组”合并变量。例如，您可能会得到三个“低重要性”变量(语言、编译器、编译器选项)，并将它们合并到一个"language+compiler+options“变量中。

注意，很容易忽略一个变量。例如，您可以在一台计算机上对“算法1”进行基准测试，在几乎相同的计算机上对“算法2”进行基准测试，但忽略了以下事实：(尽管这两种基准测试都使用了相同的语言、编译器、编译器选项和CPU)，一台计算机拥有更快的RAM芯片，而忽略了作为可能变量的"RAM速度“。

您的次要目标是减少每个变量可以拥有的值的数量。

您不需要拥有12346.78亿行的大型表/s；您也不希望在余生中使用基准来生成这么大的表。

为了减少每个变量可以拥有的值的数量：

( a)找出哪个值最重要

( b)按重要性顺序选择正确的值数(忽略/跳过所有其他值)

例如，如果将三个“较低的重要性”变量(语言、编译器、编译器选项)合并到一个变量中；那么您可能会决定，两个可能性(“GCC编译的C与-O3一起编译”和"C++由MSVC用-Ox编译“)非常重要，值得担心(因为您打算观察什么)，而所有其他可能性都会被忽略。

如何将上述变量对基准测试结果的影响降到最低？一旦收集到数据，您将如何解决上述问题，并对这些变量进行调整？

通过识别变量(作为主要目标的一部分)并显式地决定变量可能具有哪些值(作为次要目标的一部分)。

你已经这么做了。我描述的是一种正式的方法，用来做人们不自觉/本能地做的事情。例如，，您已经确定"turbo boost“是一个变量，并且您已经确定"turbo boost禁用”是您所关心的变量的唯一值(但请注意，这可能会产生后果--例如，考虑“在实践中没有涡轮增压的情况下进行的单线程合并排序”和“不受关闭turbo boost影响的并行合并排序”)。

我希望通过描述一种正式的方法，你会对你已经做出的无意识/本能的决定产生信心，并意识到在你提出问题之前，你已经走上了正确的道路。