为什么从 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

状态class：

@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));
        }
    }
}

我的数字class:

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 是关于算法的基本 informatics-based 推理局限性的一个很好的例子。关于此处代码的基本推理，以及将计算机视为简单的冯·诺依曼模型，将表明任一基准测试都需要 100k 步才能从一个 'end' 到所需的项目，因此，基准测试应该报告相同的时间，给予或接受一些统计噪音。

事实上，一个比另一个慢一个数量级。

LinkedList 在这类问题上几乎总是输家。事实上，根据经验，所有代码库都应该禁止使用 LinkedList。它几乎总是比基本推理表明的要慢得多，并且在极少数情况下 LinkedList（实际上，在实际基准测试中，而不是理论上！）胜过 ArrayList，几乎总是有一种更合适的不同类型，例如，说， ArrayDeque.

但是，为什么？

有很多原因。但通常它与缓存分页有关。

注意：对于 CPU 设计专家：我过于简单化了很多，试图解释关键方面（即缓存未命中淹没了任何算法期望）。

现代 CPU 具有分层的记忆层。到目前为止，最慢的是 'main memory'（即 16GB RAM 或您拥有的诸如此类的东西）。 CPU 实际上根本无法从主内存中读取。然而 O(n) 分析认为他们可以。

然后是缓存层，一般是3层（L1到L3），甚至比寄存器更快。

当你读取一些内存时，实际发生的是系统检查你要读取的内容是否映射到其中一个缓存，并且只有整页内存可以，所以它首先检查你的哪一页数据在，然后检查所述页面是否在这些缓存之一中。如果是，很好，操作成功。

如果没有，呃。 CPU 无法完成您的工作。因此，CPU 会去做其他事情，或者只会转动它的拇指至少 500 个周期（更多关于更快的 CPUs！），同时它从其中一个缓存和副本中逐出一些页面从主内存中将您想要的页面移到其中一个缓存中。

只有这样才能继续

Java保证数组连续。如果你声明，比如说，new int[1000000] java 将保证所有 1000000 个 4 字节序列都彼此相邻，所以如果你遍历它，你会得到最小可能的 'cache miss'事件（您从不在其中一个缓存中的内存中读取的位置）。

所以，如果你有一个 ArrayList，也就是说，由一个数组支持，那么这个数组是连续的。但是，内部的对象不一定是。与 new int[1000000] 不同，在 new Object[1000000] 中，您只有连续的指针；他们指向的实际对象不需要。

但是，对于您设置的这个测试，这并不重要，实际上您的代码中没有任何内容 'follows the pointer'。

在 LinkedLists 中，你最终根本没有数组，取而代之的是 2*X（X 是列表的大小）个对象：你正在存储的 X 个对象，以及 X 'trackers' ;每个跟踪器包含一个指向实际存储对象的指针（在 java: 引用中），以及一个 'previous' 和 'next' 指针，指向其兄弟跟踪器对象。

None保证内存中连续.

它们可以被涂得一干二净。即使只是遍历 1000000 个列表中的每个元素，根本不遵循指针，如果跟踪器遍布整个地方，理论上最坏的情况是 1000000 个案例未命中。

缓存未命中是如此之慢，而 CPU 如此之快，您可以安全地考虑遍历每个跟踪器（或遍历 1000000 大小的数组中的每个项目）的工作 完全免费，零 CPU 时间要求，只要你不运行缓存未命中：缓存未命中往往支配时间要求。

您必须进一步调查，但对于您所看到的，这里有一个合理的解释：

您的代码运行是孤立的（它没有做太多其他事情）；所以你的 init 是运行ning 畅通无阻，虽然 java 没有连续保证任何这些，但你的实际内存布局看起来像：一个 MyDigit 对象，然后是一个链表跟踪器，然后是另一个 mydigit 对象，然后另一个链表跟踪器，依此类推。

然而，从最后一个节点开始涉及许多缓存未命中，而从前面开始（也有从页面的 'byte 0' 开始的好处）受到的影响几乎没有那么严重。

For reference, here is a chart of access times of fetching a certain sized chunk of data, assuming optimal caching - 注意达到 4M 时的 biiig 尖峰。

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

Why is getting a value from the end of a LinkedList much slower than from the start?

java

linked-list

jmh