算法性能突然提高约 10 倍

algorithm java performance-testing

2022-09-04 19:40:38

背景信息

我最近为我的算法和数据结构课程交出了一份课。任务是实现一个解决方案来查找随机生成的数组的最大子数组。我们被要求实现蛮力算法和递归分而治之算法。

然后，我们被要求分析运行时间，以查看在哪个问题大小下，蛮力算法将比递归解决方案更快。这是通过测量两种算法的运行时间（使用System.nanoTime（）测量值）来完成的，以增加问题大小。

但是，确定这一点比我预期的要棘手一些。

好奇心

如果我首先运行问题大小为5000的两种算法，超过10次，递归算法的运行时间从一次运行到下一次运行，大约10倍（从~1800μS执行，到~200μS执行），并且在其余的迭代中保持得更快。有关示例，请参阅下图

Example

第 2 列和第 3 列仅用于验证两种算法是否都返回正确的最大子数组

这在带有Java 1.6.0_29的OS X 10.7.3上进行了测试 - 在运行Windows 7和Java 1.6的PC上执行时，结果是相同的（确切的版本号未知）。

该程序的源代码可以在这里找到：https://gist.github.com/2274983

我的问题是这样的：是什么原因导致算法在“预热”后突然表现得更好？

答案 1

评论者已经指出，JIT可能导致这种行为，但OP似乎不知道那是什么。所以简单解释一下：

您的 Java 虚拟机可以通过 2 种方式运行程序：

对机器代码进行JIT的程序运行得更快，但编译需要时间，这可能会使程序启动速度变慢。所以你的JVM做了一个妥协：最初它只是解释字节码，但如果某个方法被执行多次，它只JIT编译那个单独的方法。通常只有一小部分程序代码会执行多次（内部循环等），因此此策略是有效的。

这样做的结果是，当您对 Java 代码进行性能测试时，必须首先通过在循环中运行代码足够多的次数来“预热”JVM，以使性能关键型方法全部被 JIT 编译。

在这种情况下，您的递归解决方案似乎比暴力破解解决方案从 JIT 编译中受益更多。这可能表明JIT编译器正在寻找一些优化，这极大地有利于递归解决方案 - 也许将这些递归调用转换为迭代代码？

答案 2

一个建议是，在不阅读任何代码行的情况下，当您“预热”应用程序时，您会将 VM 设置为一定数量的内存，该内存量已针对您的应用程序进行了修复。

例如，假设您的 5000 个数组实体逐个发送到 ArrayList。数组列表以固定大小开始，当它达到它的限制时，它会将其大小加倍，并将旧数组复制到新数组。如果您重用此 ArrayList-在第二次运行中，此列表将处于完美的大小并且工作速度更快。

这种情况可能发生在其他一些地方。