不能直接用@Benchmark测ArrayList.get(i)和LinkedList.get(i),因为LinkedList.get(i)是O(n)遍历,JMH默认预热和采样会放大其抖动,大索引易触发GC或缓存失效,导致结果不可比。

为什么不能直接用 @Benchmark 测 ArrayList.get(i) 和 LinkedList.get(i)
因为 LinkedList.get(i) 是 O(n) 遍历,JMH 默认的预热和采样逻辑会放大其抖动,尤其在大索引时容易触发 GC 或 CPU 缓存失效,导致结果不可比。真实场景中,LinkedList 几乎从不用于随机读——但如果你硬要测,必须控制变量:固定索引位置、禁用 JIT 逃逸优化、避免对象创建污染。
- 用
@Fork(jvmArgsAppend = {"-XX:+UnlockDiagnosticVMOptions", "-XX:DisableIntrinsic=_toArray"})关闭可能干扰链表遍历的 JVM 内建优化 - 所有测试方法必须声明为
public且无参数,否则 JMH 无法注入基准对象 - 不要在
@Setup中复用同一份数据;ArrayList和LinkedList应各自初始化、各自填充,否则 size 不一致或引用污染会影响get()路径
怎么写一个公平的随机读 benchmark(按索引)
关键不是“测得快”,而是“测得稳”。用 ThreadLocalRandom 在每次调用中生成索引,避免预计算数组导致缓存局部性偏向 ArrayList;同时限定索引范围为 0 ~ size/2,让 LinkedList 至少有一半机会从头开始找,反映真实最坏倾向。
@Benchmark
public Integer arrayListRandomRead(ArrayList<Integer> list) {
int idx = ThreadLocalRandom.current().nextInt(list.size() / 2);
return list.get(idx);
}
@Benchmark
public Integer linkedListRandomRead(LinkedList<Integer> list) {
int idx = ThreadLocalRandom.current().nextInt(list.size() / 2);
return list.get(idx);
}
- 必须用
@State(Scope.Benchmark)标注参数类,否则 JMH 不会为每个 fork 实例化独立 list - 不要用
list.get(0)或list.get(size-1)——前者对两者都快,后者对LinkedList是 O(n),但会掩盖中间位置的性能断层 - 如果测写,
add(int index, E e)同理:统一插在size/3位置,而非末尾(那ArrayList扩容和LinkedList尾插就完全不对等)
写入性能对比必须区分 add() 位置和扩容行为
ArrayList.add(E) 在末尾是均摊 O(1),但触发扩容时是 O(n);LinkedList.add(E) 始终是 O(1)。所以单纯跑 add() 会看到 ArrayList 前期快、后期抖动大。真正可比的写法是:预分配容量 + 固定插入点。
- 在
@Setup中:arrayList = new ArrayList(SIZE);linkedList = new LinkedList();然后用循环add(null)填满到SIZE,再清空(用clear(),别new新对象) - 测插入:统一用
add(SIZE/4, value),这样既避开ArrayList末尾优化,又不让LinkedList总走头/尾指针 - JMH 参数建议:
@Fork(warmups = 3, iterations = 5)@Measurement(time = 2, timeUnit = TimeUnit.SECONDS)太少轮次压不出LinkedList的常数劣势,太多又容易被 GC 干扰
最容易被忽略的陷阱:JIT 编译器会把空循环或恒定索引优化掉
比如你写 list.get(100),HotSpot 可能直接内联成常量,或者发现 list 没变就跳过整个调用。这时候 LinkedList 看起来和 ArrayList 一样快——其实是假象。
- 必须让每次
get()的索引不可预测:用ThreadLocalRandom,且不能提取为字段(否则可能被提升为常量) - 返回值必须被使用:要么赋给
volatile字段,要么参与简单运算(如sum += x.intValue()),否则 JMH 的Blackhole.consume()必须显式调用 - 检查生成的汇编(加
-XX:+PrintAssembly)或用jmh-profiler看是否真执行了Node.next遍历——很多“慢”的结果,其实压根没走到链表逻辑里

















