算法的性能突然增加了~10倍

Question

背景信息

我最近为我的班级提供了关于算法和数据结构的分类.该任务是实现一个解决方案,以找到随机生成的数组的最大子阵列.我们被要求实施强力算法和递归分治算法.

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

然而,确定这比我预期的要复杂一点.

好奇心

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

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

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

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

我的问题是:在"热身"之后,算法突然表现得更好的原因是什么？

Answer 1

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

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

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

这样做的结果是,当您对Java代码进行性能测试时,必须首先通过循环运行代码来"预热"JVM,这足以使性能关键方法全部被JIT编译.

在这种情况下,您的递归解决方案似乎从JIT编译中获得了比蛮力解决方案更多的好处.这可能表明JIT编译器正在寻找一些优化,这极大地有利于递归解决方案 - 可能将这些递归调用转换为迭代代码？