Code :
package com.demo; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.concurrent.TimeUnit; import org.openjdk.jmh.annotations.Benchmark; import org.openjdk.jmh.annotations.BenchmarkMode; import org.openjdk.jmh.annotations.Fork; import org.openjdk.jmh.annotations.Mode; import org.openjdk.jmh.annotations.OutputTimeUnit; import org.openjdk.jmh.annotations.Scope; import org.openjdk.jmh.annotations.Setup; import org.openjdk.jmh.annotations.State; import org.openjdk.jmh.infra.Blackhole; import org.openjdk.jmh.runner.Runner; import org.openjdk.jmh.runner.RunnerException; import org.openjdk.jmh.runner.options.Options; import org.openjdk.jmh.runner.options.OptionsBuilder; @BenchmarkMode(Mode.AverageTime) //@BenchmarkMode(Mode.SingleShotTime) @OutputTimeUnit(TimeUnit.MILLISECONDS) //@OutputTimeUnit(TimeUnit.SECONDS) @State(Scope.Benchmark) @Fork(value = 2, jvmArgs = {"-Xms2G", "-Xmx2G"}) //clean JVM //@Warmup(iterations = 10, time = 500, timeUnit = TimeUnit.MILLISECONDS) //@Measurement(iterations = 10, time = 500, timeUnit = TimeUnit.MILLISECONDS) public class BenchmarkList { public static void main(String[] args) throws RunnerException { Options opt = new OptionsBuilder() .include(BenchmarkList.class.getSimpleName()) .warmupIterations(2) .measurementIterations(3) .build(); new Runner(opt).run(); } @State(Scope.Thread) public static class MyState { public int output = 1000; List<String> arrayList = new ArrayList<>(); List<String> linkedList = new LinkedList<>(); @Setup public void prepare(){ for(int i=0; i<output; i++) { arrayList.add("Hello"+i); } for(int i=0; i<output; i++) { linkedList.add("Hello"+i); } } } @Benchmark public void arrayList(MyState state,Blackhole bh) throws InterruptedException { for(int i=0; i<state.output; i++) { bh.consume(state.arrayList.get(i)); } } @Benchmark public void linkList(MyState state,Blackhole bh) throws InterruptedException { for(int i=0; i<state.output; i++) { bh.consume(state.linkedList.get(i)); } } }
Output :
Note : For Iterating elements the time complexity of LinkedList and ArrayList is O(n) i.e but there is a significant difference between iterating a arraylist and a linkedlist
ArrayList
is what you want. LinkedList
is almost always a (performance) bug.
Why LinkedList
sucks:
- It uses lots of small memory objects, and therefore impacts performance across the process.
- Lots of small objects are bad for cache-locality.
- Any indexed operation requires a traversal, i.e. has O(n) performance. This is not obvious in the source code, leading to algorithms O(n) slower than if
ArrayList
was used. - Getting good performance is tricky.
- Even when big-O performance is the same as
ArrayList
, it is probably going to be significantly slower anyway. - It’s jarring to see
LinkedList
in source because it is probably the wrong choice.