java - 如果将 ArrayList 引用为 List，为什么性能会有所不同？

Question

它在 kjellkod's article 中被提及如果我们在接收 List 作为参数的方法中传递 ArrayList，那么我们会失去性能，因为 ArrayList 实现了额外的 RandomAccess界面。 文章示例:

// 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

来自引用:

Generic list algorithms are encouraged to check whether the given list is an instanceof this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.

但是，如果我们真的在上面的方法中传递了ArrayList，并且勾选了list instanceof RandomAccess，那么这两种情况都会成立。 所以，我的第一个问题是为什么 Java VM 应该在第一种方法中将其解释为顺序列表？

我修改了文章中的测试以检查我机器上的这种行为。在 ideone 上运行测试时, 它显示类似于 kjellkod 的结果。但是当我在本地运行时，我得到了意想不到的结果，这与文章解释和我的理解相反。在我的例子中，ArrayList 作为 List 迭代似乎比将其作为 ArrayList 引用快 5-25%:

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

Answer 1

So, my first question is why the Java VM should interpret this as a sequential list in the first method?

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

Does it depend on architecture or number of processor cores?

不，您会看到 -client 之间的区别，例如32 位 Windows 和 -server 例如任何 64 位 JVM。

---

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

注意:对于一个列表，contains() 是 O(n) 这就是为什么你的时间增长 O(n^2)代码可能会令人困惑，因为您很容易受到优化和未优化的细微差别的影响。通过比较已经合理优化的代码，您将获得更有意义的结果。