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

Question

我有一个包含1000000个项目的LinkedList。我测量了一个项目的检索，首先是索引100000，然后是索引900000。在这两种情况下，LinkedList都要经过100000次操作才能获得所需的索引。那么，为什么从最后开始的检索比从一开始慢得多呢？使用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));
}
}
}

MyDigit类别：

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

LinkedList获取方法：

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是一个很好的例子，说明了基于基本信息学的算法推理的局限性。关于这里的代码的基本推理，以及将计算机视为一个简单的von neumann模型，将规定任何一个基准都需要10万步才能从一端到达所需的项目，因此，基准应该报告相等的次数，给出或接受一些统计噪声。

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

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:reference中)，以及一个指向其同级跟踪器对象的"上一个"one_answers"下一个"指针。

这些都不能保证在内存中是连续的。

它们可能被涂得到处都是。即使只是在1000000个列表中的每个元素中循环，根本不跟随指针，如果跟踪器到处都是，理论上最坏的情况是1000000个未命中。

缓存未命中速度如此之慢，CPU速度如此之快，以至于您可以放心地将遍历每个跟踪器(或1000000大小阵列中的每个项)的工作视为完全免费，所需CPU时间为零，只要您不遇到缓存未命中：缓存未命中往往会主导时间需求。

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

您的代码是孤立运行的(它不做太多其他事情)；因此，您的init运行不受阻碍，虽然java对此没有任何连续的保证，但您的实际内存布局看起来像：一个MyDigit对象，然后是一个linkedlist跟踪器，然后是另一个MyDigit对象，再然后是另个linkedlisttracker，依此类推

尽管如此，从最后一个节点开始会涉及大量缓存未命中，而从前面开始(从页面的"字节0"开始也有好处)则不会受到严重影响。

作为参考，这里有一张图表，假设最佳缓存，提取一定大小的数据块的访问时间-请注意，当您达到4M时，biiig峰值。