java - 为什么遍历 LinkedList 很慢？

Question

Java 8

我有一个相当大的集合(大约 1 亿个元素)，我需要遍历它并执行一些操作。有两种选择:

1. 遍历一次并完成整个工作(这会使代码显着复杂化)

2. 遍历它两次，在第一次迭代中完成一半的工作，在第二次迭代中休息(这将显着简化代码)

所以，我认为迭代并没有那么昂贵，并写了一个简单的例子来衡量它(我不经常写基准测试，因此它可能看起来有点傻):

    Collection<Double> col = new LinkedList<>();
    for(int i = 0; i < 30000000; i++){
        col.add(Math.sqrt(i + 1));
    }
    long start1 = System.nanoTime();
    Double res = 0.0;
    for(Double d : col){
        res += d + d;
    }
    long end1 = System.nanoTime();
    System.out.println(end1 - start1);
    System.out.println("=================================");
    long start2 = System.nanoTime();
    Double res2 = 0.0;
    for(Double d : col){
        res2 += d;
    }
    for(Double d : col){
        res2 += d;
    }
    long end2 = System.nanoTime();
    System.out.println(end2 - start2);

平均结果如下:

1107881047第一

2133450162 第二个(慢两倍)

因此，迭代是一个相当缓慢的过程。但是我不明白为什么？我以为我们做的工作量几乎相同，所以性能会有很大不同。

值得注意的是，如果我使用 ArrayList 而不是链表，结果是:

3858616604第一

422297749 第二个(比第一个快十倍，比上面的例子快两倍)

您不能简要解释一下这种性能差异吗？

Answer 1

首先，对于基准测试，您最好使用 JMH tool

现在，回到最初的问题。当您遍历 ArrayList 时，您实质上是对数组进行顺序扫描，这是一个连续的内存块。 CPU 完美地将数据从主内存预取到 CPU 缓存。因此速度非常快。

在 LinkedList 的情况下，您必须通过对象引用从一个元素转到另一个元素。通常情况下，每个节点的对象都可以驻留在内存中的任何位置。所以你必须不断地从一个内存位置跳到一个完全不相关的位置。 CPU 无法预测，无法从主存中获取数据。因此，您一直在等待数据。