java - 为什么从 LinkedList 的末尾获取值比从开始要慢得多？

Question

我有一个包含 1,000,000 个项目的 LinkedList。我首先在索引 100,000 和索引 900,000 处测量了一个项目的检索。在这两种情况下，LinkedList 都经过 100,000 次操作才能获得所需的索引。那么为什么从最后检索比从开始检索慢这么多呢？
使用 JMH 进行的测量。

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 10)
@Measurement(iterations = 10)
public class ComparationGet {

    static int val1 = 100_000;
    static int val2 = 500_000;
    static int val3 = 900_000;

    @Benchmark
    public void testGet1LinkedListFromStart(Blackhole blackhole, MyState state) {
        MyDigit res1 = state.linkedList.get(val1);
        blackhole.consume(res1);
    }

    @Benchmark
    public void testGet2LinkedListFromEnd(Blackhole blackhole, MyState state) {
        MyDigit res1 = state.linkedList.get(val3);
        blackhole.consume(res3);
    }
}

结果:

from start:
ComparationGet.testGet1LinkedListFromStart  avgt   10  0,457 ± 0,207  ms/op

from end:
ComparationGet.testGet2LinkedListFromEnd  avgt   10  5,789 ± 3,094  ms/op

状态类:

@State(Scope.Thread)
public class MyState {
    public List<MyDigit> linkedList;


    private int iterations = 1_000_000;

    @Setup(Level.Invocation)
    public void setUp() {
        linkedList = new LinkedList<>();

        for (int i = 0; i < iterations; i++) {
            linkedList.add(new MyDigit(i));
        }
    }
}

我的数字类:

public class MyDigit{
    private int val;

    public MyDigit(int val) {
        this.val = val;
    }
}

链表获取方法:

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Answer 1

LinkedList 是基于基本信息学的算法推理局限性的一个很好的例子。此处代码的基本推理，以及将计算机视为简单的冯诺依曼模型，将规定任一基准测试需要 100k 步才能从一个“端”到达所需项目，因此，基准测试应报告相等的时间，给出或采取一些统计噪音。
实际上，一个比另一个慢一个数量级。
LinkedList 在此类问题中几乎总是失败者。事实上，根据经验，LinkedList 应该被禁止出现在所有代码库中。它几乎总是比基本推理所表明的要慢得多，并且在 LinkedList 会(实际上，在实际基准测试中，不是理论上!)胜过 ArrayList 的罕见情况下，几乎总是有一种更合适的不同类型，例如， ArrayDeque .
但为什么？
有很多原因。但通常它与缓存分页有关。
注意:对于 CPU 设计专家:我已经过度简化了很多，试图解释关键方面(即缓存未命中淹没了任何算法预期)。
现代 CPU 具有分层的内存层。到目前为止，最慢的是“主内存”(即 16GB 的 RAM 或诸如此类的东西)。 CPU 根本无法从主内存中读取数据 .然而 O(n) 分析认为他们可以。
然后是缓存层，通常是 3 层(L1 到 L3)，甚至比寄存器更快。
当您读取一些内存时，实际发生的情况是系统会检查您要读取的内容是否映射到其中一个缓存中，并且只有整个页面的内存可以映射，因此它首先检查您的数据位于哪个页面中，然后然后检查所述页面是否在这些缓存之一中。如果是，很好，操作成功。
如果没有，呵呵。 CPU 无法完成您的工作。因此，相反，CPU 会去做其他事情，或者只是将其拇指旋转至少 500 个周期(在更快的 CPU 上更多!)缓存之一。
只有这样才能继续下去。
Java 保证数组是 连续 .如果你声明，比如说，new int[1000000] java 将保证所有 1000000 个 4 字节序列都彼此相邻，因此如果您对其进行迭代，您将获得最少可能的“缓存未命中”事件(您从不在其中之一的内存中读取)缓存)。
因此，如果您有一个 ArrayList，也就是说，由一个数组支持，那么该数组就可以保证是连续的。但是，里面的对象不一定是。与 new int[1000000] 不同, 与 new Object[1000000] ，您只有 指针都是连续的；他们指向的实际对象不一定是。
但是，对于您设置的此测试，这并不重要，您的代码中实际上没有“跟随指针”。
在 LinkedLists 中，您最终没有任何数组，取而代之的是 2*X(X 是列表的大小)对象:您正在存储的 X 个对象，以及 X 个“跟踪器”；每个跟踪器都包含一个指向所存储的实际对象的指针(在 java 中:引用)，以及指向其兄弟跟踪器对象的“上一个”和“下一个”指针。
这些都不能保证在内存中是连续的 .
它们可能会被涂抹得遍体鳞伤。即使只是循环遍历 1000000 列表中的每个元素，根本不跟随指针，如果跟踪器到处都是，理论上最坏的情况是 1000000 例未命中。
缓存未命中如此之慢，而 CPU 如此之快，以至于您可以放心地将遍历每个跟踪器(或遍历 1000000 大小的数组中的每个项目)的工作视为 完全免费，零 CPU 时间要求 ，只要您不遇到缓存未命中:缓存未命中往往会支配时间要求。
您必须进一步调查，但对于您所看到的情况，这里有一个合理的解释:
你的代码是独立运行的(它没有做太多其他的事情)；所以你的 init 运行不受阻碍，虽然 java 没有连续保证任何这些，你的实际内存布局看起来像:一个 MyDigit 对象，然后是一个链表跟踪器，然后是另一个 mydigit 对象，然后是另一个链表跟踪器，依此类推。
尽管如此，从最后一个节点开始会导致许多缓存未命中，而从前面(也有从页面的“字节 0”开始)的影响几乎没有那么严重。
For reference, here is a chart of access times of fetching a certain sized chunk of data, assuming optimal caching - 当您达到 4M 时，请注意 biiig 峰值。