Compare the ArrayList with LinkedList on iterating new objects

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.

Leave a Comment