Java Microbenchmarks

CollectionTest.java

package hudson.cli;

import org.junit.Test;

import java.util.*;

// Micro benchmark different array ops in Java
// Originally started from http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist/7507740#7507740
// Now completely rewritten to correctly warm up the JIT compilation and take an average over many runs
// Tweaked/corrected version from http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist/7507740#7507740
public class CollectionTest {
    private static final int MAX_ELEMENTS = 5;
    private static final int WARMUP_RUNS = 10000;
    private static final int BENCHMARK_RUNS = 100000;
    String[] strings = maxArray();

    // Does a JIT warmup run and then a benchmark averaged over many runs
    abstract class Benchmarkable {
        List<String> stringList = Arrays.asList(strings);
        List<String> testList;

        abstract String getName();
        abstract void setup();
        abstract void runMethod();

        public void doBenchMark() {
            int warmupRuns = WARMUP_RUNS;
            int benchmarkRuns = BENCHMARK_RUNS;


            for(int i=0; i<warmupRuns; i++){
                setup();
                runMethod();
            }

            // Timing loop
            long totalTime = 0;
            for(int i=0; i<benchmarkRuns; i++) {
                setup();
                long startTime = System.nanoTime();
                runMethod();
                long endTime = System.nanoTime();
                totalTime += (endTime-startTime);
            }
            System.out.println("Benchmark \""+getName()+"\" took "+totalTime/benchmarkRuns+" ns/run");
        }
    }

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void listAddAll() {

        Benchmarkable arrayListAddBenchmark = new Benchmarkable() {
            @Override
            public String getName() { return "Array List addAll()"; }

            @Override
            void setup() { testList = new ArrayList<>(); }

            @Override
            void runMethod() { testList.addAll(stringList); }
        };
        arrayListAddBenchmark.doBenchMark();

        Benchmarkable linkedListAddBenchmark = new Benchmarkable() {
            @Override
            public String getName() { return "Linked List addAll()"; }

            @Override
            void setup() { testList = new LinkedList<>(); }

            @Override
            void runMethod() { testList.addAll(stringList); }
        };
        linkedListAddBenchmark.doBenchMark();
    }

    @Test
    public void listAppend() {
        Benchmarkable arrayListAddBenchmark = new Benchmarkable() {
            @Override
            public String getName() { return "Array List add() from scratch"; }

            @Override
            void setup() { testList = new ArrayList<>(); }

            @Override
            void runMethod() {
                List<String> myList = testList;
                for (String string : strings)
                    testList.add(string);

            }
        };
        arrayListAddBenchmark.doBenchMark();

        Benchmarkable linkedListAddBenchmark = new Benchmarkable() {
            @Override
            public String getName() { return "Linked List add() from scratch"; }

            @Override
            void setup() { testList = new LinkedList<>(); }

            @Override
            void runMethod() {
                List<String> myList = testList;
                for (String string : strings)
                    testList.add(string);

            }
        };
        linkedListAddBenchmark.doBenchMark();
    }

    @Test
    public void testAppendLarge() {
        Benchmarkable arrayListBenchmark = new Benchmarkable() {
            String insertString0 = getString(true, MAX_ELEMENTS / 2 + 10);
            String insertString1 = getString(true, MAX_ELEMENTS / 2 + 20);
            String insertString2 = getString(true, MAX_ELEMENTS / 2 + 30);
            String insertString3 = getString(true, MAX_ELEMENTS / 2 + 40);

            @Override
            public String getName() { return "Array List add() on end"; }

            @Override
            void setup() {
                testList = new ArrayList<String>();

                // This is the most common way to add elements
                // Important because if an addAll operation increases
                // The backing array by more than 50% over existing to hold new elements
                // Then the backing array is sized *exactly* to hold all the elements.

                // Which means the next append operation would force a resize
                // This causes a large performance hit, since it would normally be amortized

                for (String s: stringList) {
                    testList.add(s);
                }
            }

            @Override
            void runMethod() {
                testList.add(insertString0);
                testList.add(insertString1);
                testList.add(insertString2);
                testList.add(insertString3);
            }
        };
        arrayListBenchmark.doBenchMark();

        Benchmarkable linkedListBenchmark = new Benchmarkable() {
            String insertString0 = getString(true, MAX_ELEMENTS / 2 + 10);
            String insertString1 = getString(true, MAX_ELEMENTS / 2 + 20);
            String insertString2 = getString(true, MAX_ELEMENTS / 2 + 30);
            String insertString3 = getString(true, MAX_ELEMENTS / 2 + 40);

            @Override
            public String getName() { return "Linked List add() on end"; }

            @Override
            void setup() {
                testList = new LinkedList<String>();

                // To replicate the arraylist setup
                for (String s: stringList) {
                    testList.add(s);
                }
            }

            @Override
            void runMethod() {
                testList.add(insertString0);
                testList.add(insertString1);
                testList.add(insertString2);
                testList.add(insertString3);
            }
        };
        linkedListBenchmark.doBenchMark();
    }

    @Test
    public void searchAndRemove() throws Exception {

        Benchmarkable arrayListBenchmark = new Benchmarkable() {
            String searchString0 = getString(true, MAX_ELEMENTS / 2 + 10);
            String searchString1 = getString(true, MAX_ELEMENTS / 2 + 20);

            @Override
            public String getName() { return "Array List search and remove"; }

            @Override
            void setup() {
                testList = new ArrayList<String>(MAX_ELEMENTS);
                testList.addAll(stringList);
            }

            @Override
            void runMethod() {
                List<String> myList = testList;
                myList.remove(searchString0);
                myList.remove(searchString1);
            }
        };
        arrayListBenchmark.doBenchMark();

        Benchmarkable linkedListBenchmark = new Benchmarkable() {
            String searchString0 = getString(true, MAX_ELEMENTS / 2 + 10);
            String searchString1 = getString(true, MAX_ELEMENTS / 2 + 20);

            @Override
            public String getName() { return "Linked List search and remove"; }

            @Override
            void setup() {
                testList = new LinkedList<String>();
                testList.addAll(stringList);
            }

            @Override
            void runMethod() {
                List<String> myList = testList;
                myList.remove(searchString0);
                myList.remove(searchString1);
            }
        };
        linkedListBenchmark.doBenchMark();
    }

    @Test
    public void search() throws Exception {

        Benchmarkable arrayListBenchmark = new Benchmarkable() {
            String searchString0 = getString(true, MAX_ELEMENTS / 2 + 10);
            String searchString1 = getString(true, MAX_ELEMENTS / 2 + 20);

            @Override
            public String getName() { return "Array List search"; }

            @Override
            void setup() {
                testList = new ArrayList<String>(MAX_ELEMENTS);
                testList.addAll(stringList);
            }

            @Override
            void runMethod() {
                List<String> myList = testList;
                myList.contains(searchString0);
                myList.contains(searchString1);
            }
        };
        arrayListBenchmark.doBenchMark();

        Benchmarkable linkedListBenchmark = new Benchmarkable() {
            String searchString0 = getString(true, MAX_ELEMENTS / 2 + 10);
            String searchString1 = getString(true, MAX_ELEMENTS / 2 + 20);

            @Override
            public String getName() { return "Linked List search"; }

            @Override
            void setup() {
                testList = new LinkedList<String>();
                testList.addAll(stringList);
            }

            @Override
            void runMethod() {
                List<String> myList = testList;
                myList.contains(searchString0);
                myList.contains(searchString1);
            }
        };
        linkedListBenchmark.doBenchMark();
    }

    private String[] maxArray() {
        String[] strings = new String[MAX_ELEMENTS];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX_ELEMENTS; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}

Benchmarks on:
java version "1.8.0_60"
Java(TM) SE Runtime Environment (build 1.8.0_60-b27)
Java HotSpot(TM) 64-Bit Server VM (build 25.60-b23, mixed mode)

MacBook Pro (Retina, 15-inch, Mid 2014), 16GB RAM

With MAX_ELEMENTS=5

Benchmark "Array List search and remove" took 118 ns/run
Benchmark "Linked List search and remove" took 75 ns/run
Benchmark "Array List search" took 70 ns/run
Benchmark "Linked List search" took 142 ns/run
Benchmark "Array List addAll()" took 123 ns/run
Benchmark "Linked List addAll()" took 88 ns/run
Benchmark "Array List add() from scratch" took 115 ns/run
Benchmark "Linked List add() from scratch" took 99 ns/run
Benchmark "Array List add() on end" took 66 ns/run
Benchmark "Linked List add() on end" took 60 ns/run

With MAX_ELEMENTS=50

Benchmark "Array List search and remove" took 2151 ns/run
Benchmark "Linked List search and remove" took 2091 ns/run
Benchmark "Array List search" took 1861 ns/run
Benchmark "Linked List search" took 1983 ns/run
Benchmark "Array List addAll()" took 756 ns/run
Benchmark "Linked List addAll()" took 1711 ns/run
Benchmark "Array List add() from scratch" took 4855 ns/run - Probably system noise, other results yield something considerably different.
Benchmark "Linked List add() from scratch" took 3980 ns/run
Benchmark "Array List add() on end" took 212 ns/run
Benchmark "Linked List add() on end" took 260 ns/run

With MAX_ELEMENTS=500

Benchmark "Array List search and remove" took 1695 ns/run
Benchmark "Linked List search and remove" took 2472 ns/run
Benchmark "Array List search" took 6649 ns/run
Benchmark "Linked List search" took 8215 ns/run
Benchmark "Array List addAll()" took 1578 ns/run
Benchmark "Linked List addAll()" took 9045 ns/run
Benchmark "Array List add() from scratch" took 13856 ns/run
Benchmark "Linked List add() from scratch" took 14546 ns/run
Benchmark "Array List add() on end" took 55 ns/run
Benchmark "Linked List add() on end" took 70 ns/run

With MAX_ELEMENTS=5000

Benchmark "Array List search and remove" took 73845 ns/run
Benchmark "Linked List search and remove" took 79769 ns/run
Benchmark "Array List search" took 60191 ns/run
Benchmark "Linked List search" took 85151 ns/run
Benchmark "Array List addAll()" took 16944 ns/run
Benchmark "Linked List addAll()" took 82282 ns/run
Benchmark "Array List add() from scratch" took 130960 ns/run
Benchmark "Linked List add() from scratch" took 165585 ns/run
Benchmark "Array List add() on end" took 376 ns/run
Benchmark "Linked List add() on end" took 441 ns/run

With MAX_ELEMENTS = 500000

Note: reduced warmup & benchmark runs to 1000 each, because it was taking forever otherwise
Benchmark "Array List search and remove" took 2867678 ns/run
Benchmark "Linked List search and remove" took 3279577 ns/run
Benchmark "Array List search" took 2798595 ns/run
Benchmark "Linked List search" took 3266959 ns/run
Benchmark "Array List addAll()" took 922648 ns/run
Benchmark "Linked List addAll()" took 2830256 ns/run
Benchmark "Array List add() from scratch" took 3905701 ns/run
Benchmark "Linked List add() from scratch" took 4037410 ns/run
Benchmark "Array List add() on end" took 1199 ns/run
Benchmark "Linked List add() on end" took 1465 ns/run

Hello svanoort.
I think the correct notation is "ms" instead "ns".
2798595 ns is equivalent to 0,0027986 seconds, and it's very fast.
Otherwise, 2798595 ms is equivalent to 2798,595 seconds, and it's very slow.

I think you meant 10,000, correct @svanoort?
If so, here is the graph