java代码计算排序算法的运行时间

Question

这个问题已经有答案了:

How do I write a correct micro-benchmark in Java? (11 个回答)

已关闭 3 年前。

我有一个java代码，可以计算多种排序算法的运行时间，例如“合并排序，冒泡排序等..”。

由于分支预测，第一个算法之后的运行时间计算不正确。那么是否有办法避免分支预测以获得正确的运行时间。

Example:Running time for revers sorted array with length 200000 index is as below:
Average runtime for Merge Sort in seconds after 10 iteration is : 0.0204354182
Average runtime for Bubble Sort in seconds after 10 iteration is : 1.0596160000000001E-4

如您所见，冒泡排序的运行时间不正确，它应该比此类数组的合并排序的运行时间更长。

感谢您的帮助。

Answer 1

可能您的后续迭代正在对第一次迭代生成的已排序数组进行排序。如果您在无交换版本上使用提前输出，那么在这种情况下，BubbleSort 会很快。 MergeSort 的时间恒定，并且始终执行相同的工作量，即使对于已排序的输入也是如此。

对反转数组的副本进行排序。

多次复制输入听起来与扫描一次相比性能相差 20 倍。 (对已排序输入进行合并排序可能会退化为复制所有一半，然后复制所有另一半。在越来越小的 block 中，因此在某些时候它们开始适合 L2 缓存，然后是 L1d 缓存，如果我们谈论的是整数而不是字符串。)

The running time after the first algorithm is not calculated correctly due to branch prediction.

这听起来不太可能。它可能与稳态情况不同，但分支预测可以“学习”和“记住”的模式数量应该是 200000 个排序的一小部分。

更有可能的是，由于其他预热效应(例如 JIT 编译)以及 CPU 频率尚未从空闲上升到最大值，第一次迭代速度很慢。

参见Idiomatic way of performance evaluation? 。如果每次迭代都丢弃排序后的副本，请确保时间仍然合理；如果优化器太聪明，它可能会因为不执行工作来生成从未使用过的结果数组而击败您的基准测试。