java - 算法的性能突然提高了约 10 倍

Question

背景信息

我最近为我的类(class)交了一份关于算法和数据结构的作业。任务是实现一个解决方案来找到 maximum-subarray随机生成的数组。我们被要求同时实现蛮力算法和递归分而治之算法。

然后我们被要求分析运行时间，以查看在何种问题规模下蛮力算法会比递归解决方案更快。这是通过测量两种算法的运行时间(使用 System.nanoTime() 测量)来增加问题规模来完成的。

然而，确定这一点比我预期的要复杂一些。

好奇心

如果我开始运行问题大小为 5000 的两种算法超过 10 次，则递归算法的运行时间从一次运行到下一次下降大约 10 倍(从 ~1800µS执行，到 ~200µS 执行)并且它在其余迭代中保持更快。示例见下图

第二列和第三列只是为了验证两种算法都返回了正确的最大子数组

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

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

我的问题是:是什么导致算法在“预热”后突然表现得那么好？

Answer 1

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

Java 虚拟机可以通过两种方式运行程序:

1. 解释 Java 字节码。基本上，解释器一个一个地“遍历”字节码，检查每个字节码是什么，然后执行相应的操作。

2. 将字节码转换为机器码，底层CPU可以直接运行。这称为“即时编译”或 JIT。

经过 JIT 转换为机器代码的程序运行速度要快得多，但编译需要时间，这可能会使程序启动速度变慢。因此，您的 JVM 做出了妥协:最初它只是解释字节码，但如果多次执行某个方法，它会 JIT 编译 只编译那个单独的方法。一般只有一小部分程序代码会被多次执行(内循环等)，所以这种策略是有效的。

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

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