为什么 ArrayList 性能在被引用为 List 时会有所不同?

2022-09-04 23:14:25

kjellkod 的文章中提到,如果我们传入作为参数接收的方法,那么我们就会失去性能,因为 ArrayList 实现了额外的 RandomAccess 接口。文章中的示例:ArrayListList

// SLOWER: as shown in http://ideone.com/1wnF1
private static void linearInsertion(Integer[] intArray, List<Integer> list) {
[...]
int list_size = list.size();
for (int i = 0; i < list_size; i++) {
if (integer.compareTo(list.get(i)) >= 0) { // ... more code

// FASTER: as shown in http://ideone.com/JOJ05
private static void linearInsertion(Integer[] intArray, ArrayList<Integer> list) {
[...]
int list_size = list.size();
for (int i = 0; i < list_size; i++) {
if (integer.compareTo(list.get(i)) >= 0) { // ... more code

从参考:

建议通用列表算法在应用如果将给定列表应用于顺序访问列表时性能较差的算法之前,检查给定列表是否是此接口的实例,并在必要时更改其行为以保证可接受的性能。

但是,如果我们真的在上面的方法中传递ArrayList并检查,那么在这两种情况下都是正确的。因此,我的第一个问题是,为什么Java VM应该在第一种方法中将其解释为顺序列表?list instanceof RandomAccess

我已经修改了文章中的测试,以检查我的计算机上的此行为。当在ideone上运行测试时,它显示的结果类似于kjellkod。但是当我在本地运行它时,我得到了意想不到的结果,这与文章的解释以及我的理解背道而驰。在我的情况下,ArrayList as List 迭代似乎比将其引用为 ArrayList 快 5-25%:

enter image description here

如何解释这种差异?它是否取决于体系结构或处理器内核的数量?我的工作机器配置是Windows 7 Professional x64,Intel Core i5-3470(4核,4线程),16 GB RAM。


答案 1

因此,我的第一个问题是,为什么Java VM应该在第一种方法中将其解释为顺序列表?

JVM 没有顺序或随机访问列表的概念。(除标记界面外)它是实现的开发人员,它认识到ArrayList在O(1)时间而不是O(n)时间内执行随机访问查找。

它是否取决于体系结构或处理器内核的数量?

不,您将看到例如32位Windows和例如任何64位JVM之间的差异。-client-server


我怀疑你第二次运行了列表测试。这可能会更快,因为代码在JIT和CPU缓存中都受到更多警告。我建议你至少执行每个测试三次,首先运行最长的测试,忽略你执行的第一次运行。

注意:contains() 是列表的 O(n),这就是为什么你的时间增长 O(n^2) 显然,如果你想忽略重复项,你不会使用 List,并且查看真正低效的代码的行为可能会令人困惑,因为你很容易受到优化和优化的微妙之处的影响。通过比较已经相当优化的代码,您将获得更有意义的结果。


答案 2

尽管两种方法中的代码相同,但理论上仍然存在差异,因为在JVM级别调用接口方法与调用类方法不同。它们是 2 个不同的字节码操作:和 。查看 http://bobah.net/d4d/source-code/misc/invokevirtual-vs-invokeinterface-performance-benchmarkinvokeinterfaceinvokevirtual