Ale*_*nov 7 java linked-list jmh
我有一个包含 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;
}
}
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，也就是说，由一个数组支持，那么该数组就可以保证是连续的。但是，里面的对象不一定是。与 with new int[1000000]、 with不同new Object[1000000]，你只是让所有的指针都是连续的；他们指向的实际对象不一定是。
但是，对于您设置的此测试，这并不重要，您的代码中实际上没有“跟随指针”。
在 LinkedLists 中，您最终没有任何数组，取而代之的是 2*X（X 是列表的大小）对象：您正在存储的 X 个对象，以及 X 个“跟踪器”；每个跟踪器都包含一个指向所存储的实际对象的指针（在 java 中：引用），以及指向其兄弟跟踪器对象的“上一个”和“下一个”指针。
这些都不能保证在内存中是连续的。
它们可能会被涂抹得遍体鳞伤。即使只是循环遍历 1000000 列表中的每个元素，根本不跟随指针，如果跟踪器到处都是，理论上最坏的情况是 1000000 例未命中。
缓存未命中如此之慢，而 CPU 如此之快，以至于您可以放心地将遍历每个跟踪器（或遍历 1000000 大小的数组中的每个项目）的工作视为完全免费、零 CPU 时间，只要您不这样做不会遇到缓存未命中：缓存未命中往往支配时间要求。
您必须进一步调查，但对于您所看到的情况，这里有一个合理的解释：
你的代码是独立运行的（它没有做太多其他的事情）；所以你的 init 运行不受阻碍，虽然 java 没有连续保证任何这些，但你的实际内存布局看起来像：一个 MyDigit 对象，然后是一个链表跟踪器，然后是另一个 mydigit 对象，然后是另一个链表跟踪器，依此类推。
尽管如此，从最后一个节点开始会导致许多缓存未命中，而从前面（也有从页面的“字节 0”开始）的影响几乎没有那么严重。
作为参考，这里是获取特定大小数据块的访问时间图表，假设最佳缓存- 请注意达到 4M 时的 biiig 峰值。
