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

Background info

我最近为我的 class 提供了关于算法和数据结构的分类 . 任务是实现一个解决方案来查找随机生成的数组maximum-subarray . 我们被要求实施强力算法和递归分治算法 .

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

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

Curiosity

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

Example

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

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

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

My question is this: 什么原因导致算法在"warmed up"之后突然表现得更好?

回答(3)

3 years ago

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

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

  • 解释Java字节码 . 基本上,解释器逐个“遍历”字节码,检查每个字节码是什么,并执行相应的操作 .

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

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

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

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

3 years ago

在没有阅读任何代码行的情况下,一个建议是,当您“预热”应用程序时,您的虚拟机将获得一些为您的应用程序修复的内存量 .

例如,假设你的5000个数组实体一个接一个地到ArrayList . 数组列表以固定大小开始,当达到它的限制时,它的大小加倍并将旧数组复制到新数组 . 如果在第二次运行中重用此ArrayList-,则此列表将处于完美的大小并且工作得更快 .

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

3 years ago

我建议你使用 -XX:+PrintCompliation 运行,你应该看到比大约10,000次调用或迭代之后,已经编译了关键方法 . 如果您想知道要查看要查看的内容,请查看要检查的代码,这将向您显示哪些方法有所不同 . 编译的重点是提高代码的性能 .


对于未经优化的代码,您将获得最快的速度 . 事实上,我会说Java是运行代码的最有效的语言之一,它没有做任何事情 .

举个公平的例子,你需要优化代码,所以我

  • 删除了Math.floor(),因为它没有做任何事情, (hi + lo) /2 总是一个整数 . 最快,最安全的方法是 (hi + lo) >>> 1

  • 使用Math.max获得最大值 .

  • 添加 break; 以在达到最大值时停止sum循环 .

对我来说,这减少了70%的时间,我得到的比例是110倍 .