如何准确衡量排序算法的性能
How to accurately measure performance of sorting algorithms
我有一堆 C 中的排序算法，我希望对其进行基准测试。我担心这样做的良好方法。可能影响基准性能的因素包括（但不限于）：实现的特定编码、编程语言、编译器（和编译器选项）、基准测试机器以及关键的输入数据和时间测量方法。如何将上述变量对基准测试结果的影响降至最低？
为了给你举几个例子，我考虑了两种不同语言的多种实现来调整前两个变量。此外，我可以使用不同的编译器在相当普通（和指定）的参数上编译代码。现在我要 运行 在我的机器上进行测试，它具有涡轮增压和诸如此类的功能，并且经常将核心 运行 东西提升到月球。当然，我会禁用它并进行多次运行，并且可能会用他们的平均完成时间来对此进行调整。关于输入数据，我将采用不同的数组大小，从非常小到相对较大。我不知道理想的增量应该是什么样的，以及元素的范围应该是多少。我还认为应该允许重复的元素。
我知道算法的理论分析解释了所有这些方法，但我用实际基准来补充我的研究是至关重要的。您将如何着手解决上述问题，并在收集数据后针对这些变量进行调整？我对我正在使用的技术很满意，但对研究某个主题的严格方法则不太满意。谢谢。
您无法对抽象算法进行基准测试，只能对它们的特定实现进行基准测试，使用特定编译器运行在特定机器上编译。
选择几个不同的相关编译器和机器（例如 Haswell、Ice Lake、and/or Zen2 和 Apple M1，如果你能得到的话，and/or AArch64 云服务器) 并衡量您的实际实施。如果您关心像 ARM Cortex-A53 这样的有序 CPU，也可以在其中之一上进行测量。 （使用 GEM5 或类似的性能模拟器进行模拟可能值得尝试。也可能相关的是像 Intel Silvermont 这样的低功耗实现，其乱序 window 小得多，但也有更短的管道，因此更小的分支预测错误惩罚.)
如果某些算法允许在源代码中进行有用的微优化，或者编译器发现，那是该算法的真正优势。
使用您在实践中针对您关心的用例使用的选项进行编译，例如 clang -O3 -march=native，或只是 -O2。
云服务器上的基准测试使得很难/不可能获得空闲系统，除非你为一个巨大的实例付出很多，但现代 AArch64 服务器是相关的并且可能具有不同的内存带宽与分支错误预测成本与. 缓存大小和带宽。
（您可能会发现相同的代码是您测试的所有或大多数系统上最快的排序实现。
回复：尺寸：是的，各种尺寸都不错。
您通常希望使用随机数据进行测试，这些数据可能总是从相同的 PRNG 种子生成，因此您每次都对相同的数据进行排序。
您可能还想测试一些不寻常的情况，例如已经排序或几乎已排序，因为对于这些情况，速度特别快的算法很有用。
如果您关心对整数以外的事物进行排序，您可能希望使用不同大小的结构进行测试，并使用 int 键作为成员。或者，如果您想探索排序如何使用不像一个比较机器指令那么简单的比较函数，或者做一些工作的比较函数。
与微基准测试一样，在数组预热（页面错误）和 CPU 频率等方面存在许多陷阱。
taking their mean completion time
您可能想要舍弃高异常值，或采用对您有影响的中位数。通常这意味着 运行 打扰它期间“发生了一些事情”。如果您 运行 在相同的数据上使用相同的代码，通常您可以获得相同的性能。 （具有页面粒度的代码/堆栈地址的随机化通常不会影响分支在预测器中是否相互别名，或者数据缓存冲突未命中，但是代码的一部分中的微小变化可以通过这样的效果改变其他代码的性能如果你正在重新编译。）
如果你想看看当它有自己的机器时它会如何 运行，你不想考虑 运行 其他东西干扰的地方。如果您尝试在“真实世界”云服务器条件下进行基准测试，或者其他线程在真实程序中执行其他工作，那是不同的，您需要提出使用一些共享资源的实际其他负载，例如L3 占用空间和内存带宽。
Things that could affect benchmark performance include (but are not limited to): specific coding of the implementation, programming language, compiler (and compiler options), benchmarking machine and critically the input data and time measuring method.
让我们从一个非常不同的角度来看这个问题——如何向人类呈现信息。
使用 2 个变量，您会得到一个漂亮的二维结果网格，可能像这样：
A = 1 A = 2
B = 1 4 seconds 2 seconds
B = 2 6 seconds 3 seconds
这很容易展示，也很容易让人理解并从中得出结论（例如，从我的愚蠢示例中 table 做出 2 个截然不同的观察是微不足道的 - “A=1 是 A=2 的两倍（不考虑 B）” 并且“B=1 比 B=2 快（不考虑 A）").
使用 3 个变量，您将获得 3 维结果网格，使用 N 个变量，您将获得 N 维结果网格。人类与“2 维屏幕上的 3 维数据”作斗争，更多维度成为灾难。您可以通过“剥离”一个维度来稍微缓解这种情况（例如，您可以显示多个 2D 网格，而不是尝试呈现结果的 3D 网格）；但这对人类帮助不大。
您的主要目标是减少变量的数量。
减少变量个数：
a) 确定每个变量对于您打算观察的内容的重要性（例如，“哪种算法”极其重要，“哪种语言”不太重要）。
b) 根据重要性和“逻辑分组”合并变量。例如，您可能会获得三个“重要性较低”的变量（语言、编译器、编译器选项）并将它们合并为一个“语言+编译器+选项”变量。
请注意，很容易忽略一个变量。例如，您可能在一台计算机上对“算法 1”进行基准测试，在几乎相同的计算机上对“算法 2”进行基准测试，但忽略了这样一个事实：（即使两个基准测试使用相同的语言、编译器、编译器选项和 CPU）一台计算机具有更快的速度RAM 芯片，忽略“RAM 速度”作为可能的变量。
您的次要目标是减少每个变量可以拥有的值的数量。
您不想要拥有 123456.78 亿行的大量 table/s；而且您不想花费余生进行基准测试来生成如此大的 table.
要减少每个变量可以具有的值的数量：
a) 找出最重要的价值观
b) Select 按重要性排序的正确数量的值（以及 ignore/skip 所有其他值）
例如，如果您将三个“重要性较低”的变量（语言、编译器、编译器选项）合并为一个变量；那么您可能会决定 2 种可能性（“由 GCC 使用 -O3 编译的 C”和“由 MSVC 使用 -Ox 编译的 C++”）足够重要以担心（对于您打算观察的内容）所有其他可能性都被忽略了。
How do I minimize the effect of said variables on the benchmark's results?
How would you go about resolving the mentioned issues, and adjust for these variables once the data is collected?
通过识别变量（作为主要目标的一部分）并明确决定变量可能具有哪些值（作为次要目标的一部分）。
你已经在这样做了。我所描述的是一种正式的方法，可以做人们 unconsciously/instinctively 无论如何都会做的事情。 例如，您已经确定“涡轮增压”是一个变量，并且您已经决定“ turbo boost disabled”是你关心的那个变量的唯一值（但请注意这可能会产生后果 - 例如考虑“没有涡轮增压的单线程合并排序它可能会在实践中”与“并行合并排序这不受关闭涡轮增压的影响")。
我希望通过描述正式方法，您可以对自己已经做出的 unconscious/instinctive 决定充满信心，并意识到在提出问题之前您已经走在了正确的道路上。
我有一堆 C 中的排序算法，我希望对其进行基准测试。我担心这样做的良好方法。可能影响基准性能的因素包括（但不限于）：实现的特定编码、编程语言、编译器（和编译器选项）、基准测试机器以及关键的输入数据和时间测量方法。如何将上述变量对基准测试结果的影响降至最低？
为了给你举几个例子，我考虑了两种不同语言的多种实现来调整前两个变量。此外，我可以使用不同的编译器在相当普通（和指定）的参数上编译代码。现在我要 运行 在我的机器上进行测试，它具有涡轮增压和诸如此类的功能，并且经常将核心 运行 东西提升到月球。当然，我会禁用它并进行多次运行，并且可能会用他们的平均完成时间来对此进行调整。关于输入数据，我将采用不同的数组大小，从非常小到相对较大。我不知道理想的增量应该是什么样的，以及元素的范围应该是多少。我还认为应该允许重复的元素。
我知道算法的理论分析解释了所有这些方法，但我用实际基准来补充我的研究是至关重要的。您将如何着手解决上述问题，并在收集数据后针对这些变量进行调整？我对我正在使用的技术很满意，但对研究某个主题的严格方法则不太满意。谢谢。
您无法对抽象算法进行基准测试，只能对它们的特定实现进行基准测试，使用特定编译器运行在特定机器上编译。
选择几个不同的相关编译器和机器（例如 Haswell、Ice Lake、and/or Zen2 和 Apple M1，如果你能得到的话，and/or AArch64 云服务器) 并衡量您的实际实施。如果您关心像 ARM Cortex-A53 这样的有序 CPU，也可以在其中之一上进行测量。 （使用 GEM5 或类似的性能模拟器进行模拟可能值得尝试。也可能相关的是像 Intel Silvermont 这样的低功耗实现，其乱序 window 小得多，但也有更短的管道，因此更小的分支预测错误惩罚.)
如果某些算法允许在源代码中进行有用的微优化，或者编译器发现，那是该算法的真正优势。
使用您在实践中针对您关心的用例使用的选项进行编译，例如 clang -O3 -march=native，或只是 -O2。
云服务器上的基准测试使得很难/不可能获得空闲系统，除非你为一个巨大的实例付出很多，但现代 AArch64 服务器是相关的并且可能具有不同的内存带宽与分支错误预测成本与. 缓存大小和带宽。
（您可能会发现相同的代码是您测试的所有或大多数系统上最快的排序实现。
回复：尺寸：是的，各种尺寸都不错。
您通常希望使用随机数据进行测试，这些数据可能总是从相同的 PRNG 种子生成，因此您每次都对相同的数据进行排序。
您可能还想测试一些不寻常的情况，例如已经排序或几乎已排序，因为对于这些情况，速度特别快的算法很有用。
如果您关心对整数以外的事物进行排序，您可能希望使用不同大小的结构进行测试，并使用 int 键作为成员。或者，如果您想探索排序如何使用不像一个比较机器指令那么简单的比较函数，或者做一些工作的比较函数。
与微基准测试一样，在数组预热（页面错误）和 CPU 频率等方面存在许多陷阱。
taking their mean completion time
您可能想要舍弃高异常值，或采用对您有影响的中位数。通常这意味着 运行 打扰它期间“发生了一些事情”。如果您 运行 在相同的数据上使用相同的代码，通常您可以获得相同的性能。 （具有页面粒度的代码/堆栈地址的随机化通常不会影响分支在预测器中是否相互别名，或者数据缓存冲突未命中，但是代码的一部分中的微小变化可以通过这样的效果改变其他代码的性能如果你正在重新编译。）
如果你想看看当它有自己的机器时它会如何 运行，你不想考虑 运行 其他东西干扰的地方。如果您尝试在“真实世界”云服务器条件下进行基准测试，或者其他线程在真实程序中执行其他工作，那是不同的，您需要提出使用一些共享资源的实际其他负载，例如L3 占用空间和内存带宽。
Things that could affect benchmark performance include (but are not limited to): specific coding of the implementation, programming language, compiler (and compiler options), benchmarking machine and critically the input data and time measuring method.
让我们从一个非常不同的角度来看这个问题——如何向人类呈现信息。
使用 2 个变量，您会得到一个漂亮的二维结果网格，可能像这样：
A = 1 A = 2
B = 1 4 seconds 2 seconds
B = 2 6 seconds 3 seconds
这很容易展示，也很容易让人理解并从中得出结论（例如，从我的愚蠢示例中 table 做出 2 个截然不同的观察是微不足道的 - “A=1 是 A=2 的两倍（不考虑 B）” 并且“B=1 比 B=2 快（不考虑 A）").
使用 3 个变量，您将获得 3 维结果网格，使用 N 个变量，您将获得 N 维结果网格。人类与“2 维屏幕上的 3 维数据”作斗争，更多维度成为灾难。您可以通过“剥离”一个维度来稍微缓解这种情况（例如，您可以显示多个 2D 网格，而不是尝试呈现结果的 3D 网格）；但这对人类帮助不大。
您的主要目标是减少变量的数量。
减少变量个数：
a) 确定每个变量对于您打算观察的内容的重要性（例如，“哪种算法”极其重要，“哪种语言”不太重要）。
b) 根据重要性和“逻辑分组”合并变量。例如，您可能会获得三个“重要性较低”的变量（语言、编译器、编译器选项）并将它们合并为一个“语言+编译器+选项”变量。
请注意，很容易忽略一个变量。例如，您可能在一台计算机上对“算法 1”进行基准测试，在几乎相同的计算机上对“算法 2”进行基准测试，但忽略了这样一个事实：（即使两个基准测试使用相同的语言、编译器、编译器选项和 CPU）一台计算机具有更快的速度RAM 芯片，忽略“RAM 速度”作为可能的变量。
您的次要目标是减少每个变量可以拥有的值的数量。
您不想要拥有 123456.78 亿行的大量 table/s；而且您不想花费余生进行基准测试来生成如此大的 table.
要减少每个变量可以具有的值的数量：
a) 找出最重要的价值观
b) Select 按重要性排序的正确数量的值（以及 ignore/skip 所有其他值）
例如，如果您将三个“重要性较低”的变量（语言、编译器、编译器选项）合并为一个变量；那么您可能会决定 2 种可能性（“由 GCC 使用 -O3 编译的 C”和“由 MSVC 使用 -Ox 编译的 C++”）足够重要以担心（对于您打算观察的内容）所有其他可能性都被忽略了。
How do I minimize the effect of said variables on the benchmark's results?
How would you go about resolving the mentioned issues, and adjust for these variables once the data is collected?
通过识别变量（作为主要目标的一部分）并明确决定变量可能具有哪些值（作为次要目标的一部分）。
你已经在这样做了。我所描述的是一种正式的方法，可以做人们 unconsciously/instinctively 无论如何都会做的事情。 例如，您已经确定“涡轮增压”是一个变量，并且您已经决定“ turbo boost disabled”是你关心的那个变量的唯一值（但请注意这可能会产生后果 - 例如考虑“没有涡轮增压的单线程合并排序它可能会在实践中”与“并行合并排序这不受关闭涡轮增压的影响")。
我希望通过描述正式方法，您可以对自己已经做出的 unconscious/instinctive 决定充满信心，并意识到在提出问题之前您已经走在了正确的道路上。