2
\$\begingroup\$

I have this benchmark program for my indexed linked list.

It looks like this:

com.github.coderodde.util.benchmark.LinkedListBenchmarkRunner

package com.github.coderodde.util.benchmark;

public class LinkedListBenchmarkRunner {

    public static void main(String[] args) {
        long seed = System.currentTimeMillis();

        System.out.println("<<< LinkedList seed = " + seed + " >>>");
        System.out.println();

        LinkedListBenchmark benchmark = new LinkedListBenchmark(seed);

        benchmark.warmup();
        System.out.println();
        benchmark.benchmark();
    }
}

com.github.coderodde.util.benchmark.LinkedListBenchmark

package com.github.coderodde.util.benchmark;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
import java.util.stream.Collectors;
import org.apache.commons.collections4.list.TreeList;

final class LinkedListBenchmark {

    private static final int ADD_FIRST_OPERATIONS           = 100_000;
    private static final int ADD_LAST_OPERATIONS            = 100_000;
    private static final int ADD_AT_OPERATIONS              = 10_000;
    private static final int ADD_COLLECTION_AT_OPERATIONS   = 4_000;
    private static final int ADD_LAST_COLLECTION_OPERATIONS = 10_000;
    private static final int REMOVE_VIA_INDEX_OPERATIONS    = 10_000;
    private static final int REMOVE_OBJECT_OPERATIONS       = 1_000;

    private static final int MAXIMUM_COLLECTION_SIZE = 20;

    private static final int MAXIMUM_INTEGER = 1_000;

    private final long seed;

    private Random randomJavaUtilLinkedList;
    private Random randomJavaUtilArrayList;
    private Random randomRoddeList;
    private Random randomTreeList;

    private com.github.coderodde.util.LinkedList<Integer> roddeList = 
            new com.github.coderodde.util.LinkedList<>();

    private LinkedList<Integer> linkedList = new LinkedList<>();
    private ArrayList<Integer> arrayList = new ArrayList<>();
    private TreeList<Integer> treeList = new TreeList<>();

    private long totalMillisRoddeList  = 0L;
    private long totalMillisLinkedList = 0L;
    private long totalMillisArrayList  = 0L;
    private long totalMillisTreeList   = 0L;

    LinkedListBenchmark(long seed) {
        this.seed = seed;
    }

    void warmup() {
        profile(BenchmarkChoice.WARMUP);
    }

    void benchmark() {
        profile(BenchmarkChoice.BENCHMARK);
    }

    private static  Integer getRandomInteger(Random random) {
        return random.nextInt(MAXIMUM_INTEGER + 1);
    }

    private static List<Integer> createRandomCollection(Random random) {
        int size = 1 + random.nextInt(MAXIMUM_COLLECTION_SIZE);

        List<Integer> list = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            list.add(getRandomInteger(random));
        }

        return list;
    }

    private enum BenchmarkChoice { WARMUP, BENCHMARK }

    private void initRandomGenerators() {
        randomJavaUtilLinkedList = new Random(seed);
        randomJavaUtilArrayList  = new Random(seed);
        randomRoddeList          = new Random(seed);
        randomTreeList           = new Random(seed);
    }

    private void listsEqual() {
        listsEqual(roddeList, linkedList, arrayList, treeList);
    }

    private static void listsEqual(List<Integer>... lists) {
        if (lists.length < 2) {
            throw new IllegalArgumentException("lists.length < 2");
        }

        for (int i = 0; i < lists.length - 1; i++) {
            if (lists[i].size() != lists[lists.length - 1].size()) {
                throw new IllegalStateException("Different size");
            }

            Iterator<Integer> iterator1 = lists[i].iterator();
            Iterator<Integer> iterator2 = lists[lists.length - 1].iterator();

            int elementIndex = 0;

            while (iterator1.hasNext() && iterator2.hasNext()) {
                Integer integer1 = iterator1.next();
                Integer integer2 = iterator2.next();

                if (!integer1.equals(integer2)) {
                    throw new IllegalStateException(
                            "Data mismatch: " + integer1 + " vs. " + 
                            integer2 + " at list " + i + 
                            ", element index: " + elementIndex);
                }

                elementIndex++;
            }

            if (iterator1.hasNext() || iterator2.hasNext()) {
                throw new IllegalStateException("Bad iterators");
            }
        }
    }

    private void profile(BenchmarkChoice benchmarkChoice) {

        printTitle(benchmarkChoice);
        initRandomGenerators();

        profileAddFirst();
        profileAddLast();
        profileAddViaIndex();
        profileAppendCollection();
        profileAddCollection();
        profileRemoveViaIndex();
        profileRemoveObject();
        profileListIteratorAddition();
        profileListIteratorRemoval();
        profileStream();
        profileParallelStream();

        printTotalDurations();

        resetLists();
        zeroTimeDurationCounters();
    }

    private void zeroTimeDurationCounters() {
        totalMillisArrayList  = 0;
        totalMillisLinkedList = 0;
        totalMillisRoddeList  = 0;
        totalMillisTreeList   = 0;
    }

    private void resetLists() {
        roddeList = new com.github.coderodde.util.LinkedList<>();
        linkedList = new java.util.LinkedList<>();
        arrayList = new ArrayList<>();
        treeList = new TreeList<>();
    }

    private void profileAddFirst() {
        profileAddFirstRoddeList();
        profileAddFirstLinkedList();
        profileAddFirstArrayList();
        profileAddFirstTreeList();

        listsEqual();
        System.out.println();
    }

    private void profileAddLast() {
        profileAddLastRoddeList();
        profileAddLastLinkedList();
        profileAddLastArrayList();
        profileAddLastTreeList();

        listsEqual();
        System.out.println();
    }

    private void profileAddViaIndex() {
        profileAddIndexRoddeList();
        profileAddIndexLinkedList();
        profileAddIndexArrayList();
        profileAddIndexTreeList();

        listsEqual();
        System.out.println();
    }

    private void profileAddCollection() {
        profileAddCollectionRoddeList();
        profileAddCollectionLinkedList();
        profileAddCollectionArrayList();
        profileAddCollectionTreeList();

        listsEqual();
        System.out.println();
    }

    private void profileAppendCollection() {
        profileAppendCollectionRoddeList();
        profileAppendCollectionLinkedList();
        profileAppendCollectionArrayList();
        profileAppendCollectionTreeList();

        listsEqual();
        System.out.println();
    }

    private void profileRemoveViaIndex() {
        profileRemoveViaIndexRoddeList();
        profileRemoveViaIndexLinkedList();
        profileRemoveViaIndexArrayList();
        profileRemoveViaIndexTreeList();

        listsEqual();
        System.out.println();
    }

    private void profileRemoveObject() {
        profileRemoveObjectRoddeList();
        profileRemoveObjectLinkedList();
        profileRemoveObjectArrayList();
        profileRemoveObjectTreeList();

        listsEqual();
        System.out.println();
    }

    private void profileListIteratorAddition() {
        profileListIteratorAdditionRoddeList();
        profileListIteratorAdditionLinkedList();
        profileListIteratorAdditionArrayList();
        profileListIteratorAdditionTreeList();

        listsEqual();
        System.out.println();
    }

    private void profileListIteratorRemoval() {
        profileListIteratorRemovalRoddeList();
        profileListIteratorRemovalLinkedList();
        profileListIteratorRemovalArrayList();
        profileListIteratorRemovalTreeList();

        listsEqual();
        System.out.println();
    }

    private void profileStream() {
        profileStreamRoddeList();
        profileStreamLinkedList();
        profileStreamArrayList();
        profileStreamTreeList();

        listsEqual();
        System.out.println();
    }

    private void profileParallelStream() {
        profileParallelStreamRoddeList();
        profileParallelStreamLinkedList();
        profileParallelStreamArrayList();
        profileParallelStreamTreeList();

        Collections.sort(treeList);
        Collections.sort(roddeList);
        Collections.sort(arrayList);
        Collections.sort(linkedList);

        listsEqual();
        System.out.println();
    }

    private void printTotalDurations() {
        System.out.println("--- Total time elapsed ---");
        System.out.println(
                roddeList.getClass().getName() + 
                        " in (ms): " + 
                        totalMillisRoddeList);

        System.out.println(
                linkedList.getClass().getName() + 
                        " in (ms): " + 
                        totalMillisLinkedList);

        System.out.println(
                arrayList.getClass().getName() + 
                        " in (ms): " + 
                        totalMillisArrayList);

        System.out.println(
                treeList.getClass().getName() + 
                        " in (ms): " + 
                        totalMillisTreeList);
    }

    private long profileAddFirst(
            List<Integer> list, 
            int operations, 
            Random random) {

        long startMillis = System.currentTimeMillis();

        for (int i = 0; i < operations; i++) {
            list.add(0, getRandomInteger(random));
        }

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        System.out.println(
                list.getClass().getName() + 
                        ".addFirst in (ms): " + 
                        durationMillis);

        return durationMillis;
    }

    private long profileAddLast(
            List<Integer> list, 
            int operations, 
            Random random) {

        long startMillis = System.currentTimeMillis();

        for (int i = 0; i < operations; i++) {
            list.add(list.size(), getRandomInteger(random));
        }

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        System.out.println(
                list.getClass().getName() + 
                        ".addLast in (ms): " + 
                        durationMillis);

        return durationMillis;
    }

    private long profileAddIndex(
            List<Integer> list, 
            int operations, 
            Random random) {

        long startMillis = System.currentTimeMillis();

        for (int i = 0; i < operations; i++) {
            int index = random.nextInt(list.size());
            Integer value = getRandomInteger(random);
            list.add(index, value);
        }

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        System.out.println(
                list.getClass().getName() + 
                        ".add(int, E) in (ms): " + 
                        durationMillis);

        return durationMillis;
    }

    private long profileAddCollection(
            List<Integer> list, 
            int operations, 
            Random random) {

        long startMillis = System.currentTimeMillis();

        for (int i = 0; i < operations; i++) {
            List<Integer> collection = createRandomCollection(random);
            int index = random.nextInt(list.size());
            list.addAll(index, collection);
        }

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        System.out.println(
                list.getClass().getName() + 
                        ".addAll(int, Collection) in (ms): " +
                        durationMillis);

        return durationMillis;
    }

    private long profileAppendCollection(
            List<Integer> list, 
            int operations, 
            Random random) {

        long startMillis = System.currentTimeMillis();

        for (int i = 0; i < operations; i++) {
            List<Integer> collection = createRandomCollection(random);
            list.addAll(collection);
        }

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        System.out.println(
                list.getClass().getName() + 
                        ".addAll(Collection) in (ms): " +
                        durationMillis);

        return durationMillis;
    }

    private long profileRemoveViaIndex(
            List<Integer> list, 
            int operations, 
            Random random) {

        long startMillis = System.currentTimeMillis();

        for (int i = 0; i < operations; i++) {
            list.remove(random.nextInt(list.size()));
        }

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        System.out.println(
                list.getClass().getName() +
                        ".remove(int) in (ms): " +
                        durationMillis);

        return durationMillis;
    }

    private long profileRemoveObject(
            List<Integer> list, 
            int operations, 
            Random random) {

        long startMillis = System.currentTimeMillis();

        for (int i = 0; i < operations; i++) {
            list.remove(Integer.valueOf(getRandomInteger(random)));
        }

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        System.out.println(
                list.getClass().getName() +
                        ".remove(Object) in (ms): " +
                        durationMillis);

        return durationMillis;
    }

    private long profileListIteratorRemoval(List<Integer> list) {
        long startMillis = System.currentTimeMillis();
        Iterator<Integer> iterator = list.iterator();
        int counter = 0;

        while (iterator.hasNext()) {
            iterator.next();

            // Remove every 2nd element:
            if (counter % 10 == 0) {
                try {
                    iterator.remove();
                } catch (AssertionError ae) {
                    System.err.println(ae.getMessage());
                    System.exit(1);
                }
            }

            counter++;
        }

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        System.out.println(
                list.getClass().getName() +
                        ".iterator().remove() in (ms): " +
                        durationMillis);

        return durationMillis;
    }

    private long profileListIteratorAddition(
            List<Integer> list, Random random) {

        long startMillis = System.currentTimeMillis();
        ListIterator<Integer> iterator = list.listIterator(1);
        int counter = 0;

        while (iterator.hasNext()) {
            iterator.next();

            // Remove every 2nd element:
            if (counter % 10 == 0) {
                try {
                    Integer integer = Integer.valueOf(random.nextInt(10_000));
                    iterator.add(integer);
                } catch (AssertionError ae) {
                    System.err.println(ae.getMessage());
                    System.exit(1);
                }
            }

            counter++;
        }

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        System.out.println(
                list.getClass().getName() +
                        ".iterator().add() in (ms): " +
                        durationMillis);

        return durationMillis;
    }

    private long profileStream(List<Integer> list) {
        long startMillis = System.currentTimeMillis();

        List<Integer> newList =
                list.stream().map(x -> 2 * x).collect(Collectors.toList());

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        list.clear();
        list.addAll(newList);

        System.out.println(
                list.getClass().getName() +
                        ".stream() in (ms): " + durationMillis);

        return durationMillis;
    }

    private long profileParallelStream(List<Integer> list) {
        long startMillis = System.currentTimeMillis();

        List<Integer> newList = list.stream()
                        .parallel()
                        .map(x -> 2 * x)
                        .collect(Collectors.toList());

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        list.clear();
        list.addAll(newList);

        System.out.println(
                list.getClass().getName() +
                        ".stream().parallel() in (ms): " + durationMillis);

        return durationMillis;
    }

    private void profileAddFirstRoddeList() {
        totalMillisRoddeList += 
                profileAddFirst(
                        roddeList, 
                        ADD_FIRST_OPERATIONS, 
                        randomRoddeList);
    }

    private void profileAddFirstLinkedList() {
        totalMillisLinkedList += 
                profileAddFirst(linkedList, 
                                ADD_FIRST_OPERATIONS, 
                                randomJavaUtilLinkedList);
    }

    private void profileAddFirstArrayList() {
        totalMillisArrayList += 
                profileAddFirst(arrayList, 
                                ADD_FIRST_OPERATIONS, 
                                randomJavaUtilArrayList);
    }

    private void profileAddFirstTreeList() {
        totalMillisTreeList += 
                profileAddFirst(treeList,
                                ADD_FIRST_OPERATIONS,
                                randomTreeList);
    }

    private void profileAddLastRoddeList() {
        totalMillisRoddeList += 
            profileAddLast(roddeList, ADD_LAST_OPERATIONS, randomRoddeList);
    }

    private void profileAddLastLinkedList() {
        totalMillisLinkedList += 
                profileAddLast(
                        linkedList, 
                        ADD_LAST_OPERATIONS, 
                        randomJavaUtilLinkedList);
    }

    private void profileAddLastArrayList() {
        totalMillisArrayList += 
                profileAddLast(arrayList, 
                               ADD_LAST_OPERATIONS, 
                               randomJavaUtilArrayList);
    }

    private void profileAddLastTreeList() {
        totalMillisTreeList += 
                profileAddLast(treeList, 
                               ADD_LAST_OPERATIONS, 
                               randomTreeList);
    }

    private void profileAddIndexRoddeList() {
        totalMillisRoddeList += 
                profileAddIndex(roddeList, ADD_AT_OPERATIONS, randomRoddeList);
    }

    private void profileAddIndexLinkedList() {
        totalMillisLinkedList += 
                profileAddIndex(
                        linkedList, 
                        ADD_AT_OPERATIONS, 
                        randomJavaUtilLinkedList);
    }

    private void profileAddIndexArrayList() {
        totalMillisArrayList +=
                profileAddIndex(
                        arrayList, 
                        ADD_AT_OPERATIONS, 
                        randomJavaUtilArrayList);
    }

    private void profileAddIndexTreeList() {
        totalMillisTreeList +=
                profileAddIndex(
                        treeList, 
                        ADD_AT_OPERATIONS, 
                        randomTreeList);
    }

    private void profileAddCollectionRoddeList() {
        totalMillisRoddeList +=
                profileAddCollection(
                        roddeList, 
                        ADD_COLLECTION_AT_OPERATIONS, 
                        randomRoddeList);
    }

    private void profileAddCollectionLinkedList() {
        totalMillisLinkedList += 
                profileAddCollection(
                        linkedList,
                        ADD_COLLECTION_AT_OPERATIONS,
                        randomJavaUtilLinkedList);
    }

    private void profileAddCollectionArrayList() {
        totalMillisArrayList +=
                profileAddCollection(
                        arrayList,
                        ADD_COLLECTION_AT_OPERATIONS,
                        randomJavaUtilArrayList);
    }

    private void profileAddCollectionTreeList() {
        totalMillisTreeList +=
                profileAddCollection(
                        treeList,
                        ADD_COLLECTION_AT_OPERATIONS,
                        randomTreeList);
    }

    private void profileAppendCollectionRoddeList() {
        totalMillisRoddeList +=
                profileAppendCollection(
                        roddeList, 
                        ADD_LAST_COLLECTION_OPERATIONS, 
                        randomRoddeList);
    }

    private void profileAppendCollectionLinkedList() {
        totalMillisLinkedList +=
                profileAppendCollection(
                        linkedList, 
                        ADD_LAST_COLLECTION_OPERATIONS, 
                        randomJavaUtilLinkedList);
    }

    private void profileAppendCollectionArrayList() {
        totalMillisArrayList +=
                profileAppendCollection(
                        arrayList, 
                        ADD_LAST_COLLECTION_OPERATIONS, 
                        randomJavaUtilArrayList);
    }

    private void profileAppendCollectionTreeList() {
        totalMillisTreeList +=
                profileAppendCollection(
                        treeList, 
                        ADD_LAST_COLLECTION_OPERATIONS, 
                        randomTreeList);
    }

    private void profileRemoveViaIndexRoddeList() {
        totalMillisRoddeList += 
                profileRemoveViaIndex(
                        roddeList, 
                        REMOVE_VIA_INDEX_OPERATIONS, 
                        randomRoddeList);
    }

    private void profileRemoveViaIndexLinkedList() {    
        totalMillisLinkedList += 
                profileRemoveViaIndex(
                        linkedList, 
                        REMOVE_VIA_INDEX_OPERATIONS, 
                        randomJavaUtilLinkedList);
    }

    private void profileRemoveViaIndexArrayList() {
        totalMillisArrayList += 
                profileRemoveViaIndex(
                        arrayList, 
                        REMOVE_VIA_INDEX_OPERATIONS, 
                        randomJavaUtilArrayList);
    }

    private void profileRemoveViaIndexTreeList() {
        totalMillisTreeList += 
                profileRemoveViaIndex(
                        treeList, 
                        REMOVE_VIA_INDEX_OPERATIONS, 
                        randomTreeList);
    }

    private void profileRemoveObjectRoddeList() {
        totalMillisRoddeList += 
                profileRemoveObject(
                        roddeList, 
                        REMOVE_OBJECT_OPERATIONS, 
                        randomRoddeList);
        roddeList.checkInvariant();
    }

    private void profileRemoveObjectLinkedList() {    
        totalMillisLinkedList += 
                profileRemoveObject(
                        linkedList, 
                        REMOVE_OBJECT_OPERATIONS, 
                        randomJavaUtilLinkedList);
    }

    private void profileRemoveObjectArrayList() {
        totalMillisArrayList += 
                profileRemoveObject(
                        arrayList, 
                        REMOVE_OBJECT_OPERATIONS, 
                        randomJavaUtilArrayList);
    }

    private void profileRemoveObjectTreeList() {
        totalMillisTreeList += 
                profileRemoveObject(
                        treeList,
                        REMOVE_OBJECT_OPERATIONS, 
                        randomTreeList);
    }

    private void profileListIteratorRemovalRoddeList() {
        totalMillisRoddeList += profileListIteratorRemoval(roddeList);
    }

    private void profileListIteratorRemovalLinkedList() {
        totalMillisLinkedList += profileListIteratorRemoval(linkedList);
    }

    private void profileListIteratorRemovalArrayList() {
        totalMillisArrayList += profileListIteratorRemoval(arrayList);
    }

    private void profileListIteratorRemovalTreeList() {
        totalMillisTreeList += profileListIteratorRemoval(treeList);
    }

    private void profileListIteratorAdditionRoddeList() {
        totalMillisRoddeList += 
                profileListIteratorAddition(roddeList, randomRoddeList);
    }

    private void profileListIteratorAdditionLinkedList() {
        totalMillisLinkedList +=
                profileListIteratorAddition(
                        linkedList, 
                        randomJavaUtilLinkedList);
    }

    private void profileListIteratorAdditionArrayList() {
        totalMillisArrayList += 
                profileListIteratorAddition(
                        arrayList, 
                        randomJavaUtilArrayList);
    }

    private void profileListIteratorAdditionTreeList() {
        totalMillisTreeList += 
                profileListIteratorAddition(treeList, randomTreeList);
    }

    private void profileStreamRoddeList() {
        totalMillisRoddeList += profileStream(roddeList);
    }

    private void profileStreamLinkedList() {
        totalMillisLinkedList += profileStream(linkedList);
    }

    private void profileStreamArrayList() {
        totalMillisArrayList += profileStream(arrayList);
    }

    private void profileStreamTreeList() {
        totalMillisTreeList += profileStream(treeList);
    }

    private void profileParallelStreamRoddeList() {
        totalMillisRoddeList += profileParallelStream(roddeList);
    }

    private void profileParallelStreamLinkedList() {
        totalMillisLinkedList += profileParallelStream(linkedList);
    }

    private void profileParallelStreamArrayList() {
        totalMillisArrayList += profileParallelStream(arrayList);
    }

    private void profileParallelStreamTreeList() {
        totalMillisTreeList += profileParallelStream(treeList);
    }

    private void printTitle(BenchmarkChoice benchmarkChoice) {
        switch (benchmarkChoice) {
            case WARMUP:
                System.out.println("=== WARMUP RUN ===");
                break;

            case BENCHMARK:
                System.out.println("=== BENCHMARK RUN ===");
                break;
        }
    }
}

My output is as follows:

<<< LinkedList seed = 1629264992750 >>>

=== WARMUP RUN ===
com.github.coderodde.util.LinkedList.addFirst in (ms): 57
java.util.LinkedList.addFirst in (ms): 5
java.util.ArrayList.addFirst in (ms): 493
org.apache.commons.collections4.list.TreeList.addFirst in (ms): 34

com.github.coderodde.util.LinkedList.addLast in (ms): 8
java.util.LinkedList.addLast in (ms): 27
java.util.ArrayList.addLast in (ms): 3
org.apache.commons.collections4.list.TreeList.addLast in (ms): 40

com.github.coderodde.util.LinkedList.add(int, E) in (ms): 40
java.util.LinkedList.add(int, E) in (ms): 1821
java.util.ArrayList.add(int, E) in (ms): 99
org.apache.commons.collections4.list.TreeList.add(int, E) in (ms): 13

com.github.coderodde.util.LinkedList.addAll(Collection) in (ms): 26
java.util.LinkedList.addAll(Collection) in (ms): 22
java.util.ArrayList.addAll(Collection) in (ms): 5
org.apache.commons.collections4.list.TreeList.addAll(Collection) in (ms): 23

com.github.coderodde.util.LinkedList.addAll(int, Collection) in (ms): 37
java.util.LinkedList.addAll(int, Collection) in (ms): 1431
java.util.ArrayList.addAll(int, Collection) in (ms): 74
org.apache.commons.collections4.list.TreeList.addAll(int, Collection) in (ms): 15

com.github.coderodde.util.LinkedList.remove(int) in (ms): 35
java.util.LinkedList.remove(int) in (ms): 4138
java.util.ArrayList.remove(int) in (ms): 181
org.apache.commons.collections4.list.TreeList.remove(int) in (ms): 11

com.github.coderodde.util.LinkedList.remove(Object) in (ms): 12
java.util.LinkedList.remove(Object) in (ms): 10
java.util.ArrayList.remove(Object) in (ms): 39
org.apache.commons.collections4.list.TreeList.remove(Object) in (ms): 22

com.github.coderodde.util.LinkedList.iterator().add() in (ms): 18
java.util.LinkedList.iterator().add() in (ms): 13
java.util.ArrayList.iterator().add() in (ms): 596
org.apache.commons.collections4.list.TreeList.iterator().add() in (ms): 19

com.github.coderodde.util.LinkedList.iterator().remove() in (ms): 69
java.util.LinkedList.iterator().remove() in (ms): 8
java.util.ArrayList.iterator().remove() in (ms): 738
org.apache.commons.collections4.list.TreeList.iterator().remove() in (ms): 28

com.github.coderodde.util.LinkedList.stream() in (ms): 17
java.util.LinkedList.stream() in (ms): 16
java.util.ArrayList.stream() in (ms): 7
org.apache.commons.collections4.list.TreeList.stream() in (ms): 68

com.github.coderodde.util.LinkedList.stream().parallel() in (ms): 41
java.util.LinkedList.stream().parallel() in (ms): 29
java.util.ArrayList.stream().parallel() in (ms): 88
org.apache.commons.collections4.list.TreeList.stream().parallel() in (ms): 123

--- Total time elapsed ---
com.github.coderodde.util.LinkedList in (ms): 360
java.util.LinkedList in (ms): 7520
java.util.ArrayList in (ms): 2323
org.apache.commons.collections4.list.TreeList in (ms): 396

=== BENCHMARK RUN ===
com.github.coderodde.util.LinkedList.addFirst in (ms): 37
java.util.LinkedList.addFirst in (ms): 4
java.util.ArrayList.addFirst in (ms): 415
org.apache.commons.collections4.list.TreeList.addFirst in (ms): 15

com.github.coderodde.util.LinkedList.addLast in (ms): 7
java.util.LinkedList.addLast in (ms): 4
java.util.ArrayList.addLast in (ms): 3
org.apache.commons.collections4.list.TreeList.addLast in (ms): 25

com.github.coderodde.util.LinkedList.add(int, E) in (ms): 18
java.util.LinkedList.add(int, E) in (ms): 1410
java.util.ArrayList.add(int, E) in (ms): 95
org.apache.commons.collections4.list.TreeList.add(int, E) in (ms): 6

com.github.coderodde.util.LinkedList.addAll(Collection) in (ms): 9
java.util.LinkedList.addAll(Collection) in (ms): 7
java.util.ArrayList.addAll(Collection) in (ms): 5
org.apache.commons.collections4.list.TreeList.addAll(Collection) in (ms): 2

com.github.coderodde.util.LinkedList.addAll(int, Collection) in (ms): 18
java.util.LinkedList.addAll(int, Collection) in (ms): 1376
java.util.ArrayList.addAll(int, Collection) in (ms): 65
org.apache.commons.collections4.list.TreeList.addAll(int, Collection) in (ms): 16

com.github.coderodde.util.LinkedList.remove(int) in (ms): 22
java.util.LinkedList.remove(int) in (ms): 4055
java.util.ArrayList.remove(int) in (ms): 171
org.apache.commons.collections4.list.TreeList.remove(int) in (ms): 8

com.github.coderodde.util.LinkedList.remove(Object) in (ms): 8
java.util.LinkedList.remove(Object) in (ms): 4
java.util.ArrayList.remove(Object) in (ms): 36
org.apache.commons.collections4.list.TreeList.remove(Object) in (ms): 1

com.github.coderodde.util.LinkedList.iterator().add() in (ms): 32
java.util.LinkedList.iterator().add() in (ms): 7
java.util.ArrayList.iterator().add() in (ms): 595
org.apache.commons.collections4.list.TreeList.iterator().add() in (ms): 73

com.github.coderodde.util.LinkedList.iterator().remove() in (ms): 58
java.util.LinkedList.iterator().remove() in (ms): 4
java.util.ArrayList.iterator().remove() in (ms): 726
org.apache.commons.collections4.list.TreeList.iterator().remove() in (ms): 24

com.github.coderodde.util.LinkedList.stream() in (ms): 4
java.util.LinkedList.stream() in (ms): 4
java.util.ArrayList.stream() in (ms): 5
org.apache.commons.collections4.list.TreeList.stream() in (ms): 7

com.github.coderodde.util.LinkedList.stream().parallel() in (ms): 3
java.util.LinkedList.stream().parallel() in (ms): 22
java.util.ArrayList.stream().parallel() in (ms): 4
org.apache.commons.collections4.list.TreeList.stream().parallel() in (ms): 29

--- Total time elapsed ---
com.github.coderodde.util.LinkedList in (ms): 216
java.util.LinkedList in (ms): 6897
java.util.ArrayList in (ms): 2120
org.apache.commons.collections4.list.TreeList in (ms): 206
```
\$\endgroup\$
2
  • \$\begingroup\$ I see a lot of redundancy. Why would you have class that handles all methods at once? That doesn't look like a good strategy to me. Maybe you want to just compare two list implementations? \$\endgroup\$ Sep 12 '21 at 15:18
  • \$\begingroup\$ Currently the code doesn't compile as the implementations are missing. If I try and comment them out then I get lots of compiler errors due to the way the class is setup. That's enough reason for me to leave it to above remark to be honest. Redesign so it just evaluates one particular list, possibly using virtual or abstract test methods if you need list-specific code to be run. \$\endgroup\$ Sep 12 '21 at 15:29
3
\$\begingroup\$

There's a lot of scope for consolidating the benchmark code. Reducing some of the duplication can make it easier to update the code and help focus on core functionality of some of the methods. With that in mind, here's a few suggested refactorings...

A List is a List

You've got four lists of different types, all with their own variables, that are declared as the specific type of list. The point of your benchmark is to compare how each of your lists does the same action. Declaring the variables as the generic List<> instead would be the first step I'd take. The only line that actually seems to need to know is:

roddeList.checkInvariant();

Consider if this really needs to be in your benchmarking, or if it belongs somewhere else in your tests.

Benchmark data

There're three elements that make up your benchmark data. There's the list itself, the random number generator and the duration counter. Putting these pieces in the same class would allow them to be passed around together, again making it a little bit easier to share the code.

Things that are the same can go in lists

Once benchmark data is consolidated, all of the items start looking the same, so they can be put into a list. This could look something like this:

private static class BenchmarkElement {
    Random random;
    List<Integer> list;
    long total;

    public BenchmarkElement(List<Integer> list) {
        this.list = list;
        this.total = 0;
    }
}

BenchmarkElement linkedList = new BenchmarkElement(new LinkedList<>());
BenchmarkElement arrayList = new BenchmarkElement(new ArrayList<>());
BenchmarkElement treeList = new BenchmarkElement(new TreeList<>());
BenchmarkElement roddeList = new BenchmarkElement(new com.github.coderodde.util.LinkedList<>());

List<BenchmarkElement> lists = asList(linkedList, arrayList, treeList, roddeList);

Lists are iterable..

Having separate variables for each list, means that you need to repeat the code, with a different variable name each time you want to do something. Once the benchmark elements are all contained in a list, you can instead iterate over the list instead. So Instead of doing this:

private void profileAddFirst() {
    profileAddFirstRoddeList();
    profileAddFirstLinkedList();
    profileAddFirstArrayList();
    profileAddFirstTreeList();

    listsEqual();
    System.out.println();
}

With four slightly different versions of:

private void profileAddFirstRoddeList() {
    totalMillisRoddeList +=
            profileAddFirst(
                    roddeList,
                    ADD_FIRST_OPERATIONS,
                    randomRoddeList);
}

It becomes possible to do something like this:

private void profileAddFirst() {
    lists.forEach(listElement ->
            listElement.total +=
                    profileAddFirst(
                            listElement.list,
                            ADD_FIRST_OPERATIONS,
                            listElement.random));

    listsEqual();
    System.out.println();
}

Functions are first class citizens

Once a few functions have been refactored as above, it becomes clear that there's a common pattern emerging in the code. For each of the benchmark lists, we call a specific profiling function, supplying required parameters and adjusting the running totals for that list. We then check if all the lists are equal and print a blank line to terminate the results. By passing in the method to call, it's possible to share this functionality between the various calls. So, something like this:

interface TriProfileMethod {
    long accept(List<Integer> list, Integer operations, Random random);
}
private void profileMethod(TriProfileMethod profilable, Integer operations) {
    lists.forEach(listElement ->
            listElement.total +=
                    profilable.methodToProfile(
                    profilable.accept(
                            listElement.list,
                            operations,
                            listElement.random));

    listsEqual();
    System.out.println();
}

Allows calls like this:

profileMethod(this::profileAddFirst, ADD_FIRST_OPERATIONS);
profileMethod(this::profileAddLast, ADD_LAST_OPERATIONS);
profileMethod(this::profileAddIndex, ADD_AT_OPERATIONS);

Consider what needs to be a parameter

Constants like ADD_FIRST_OPERATIONS are being passed into methods like profileAddFirst, in order to set the number of iterations that the method performs. However no other values are being passed into these methods and the constants are available from within them. Rather than passing in the value, consider removing it from the parameter list and just accessing it from within the methods.

Extending into two profiling methods

By consolidating the parameters to the profiling functions and continuing to centralise the shared processing, to profiling method patterns appear.

  1. Standard processing iterates through the list, starting a timer for each element and executing a profiling procedure and checking the elapsed duration, before validating that all the lists are equal.
  2. Stream processing is almost the same, but the profiling method returns a new list, which needs to be used to create the returned list, after the timer has stopped.

This gives two methods:

private void profileMethod(Consumer<BenchmarkElement> method, String name) {
    lists.forEach(listElement -> {
        long startMillis = System.currentTimeMillis();

        method.accept(listElement);

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        listElement.total += durationMillis;

        System.out.println(listElement.list.getClass().getName() +
                "." + name + " in (ms): " +
                durationMillis);
    });

    listsEqual();
    System.out.println();
}

private void profileStreamMethod(Function<BenchmarkElement, List<Integer>> method, String name) {
    lists.forEach(listElement -> {
        long startMillis = System.currentTimeMillis();

        List<Integer> newList = method.apply(listElement);

        long endMillis = System.currentTimeMillis();
        long durationMillis = endMillis - startMillis;

        listElement.list.clear();
        listElement.list.addAll(newList);
        listElement.total += durationMillis;

        System.out.println(
                listElement.list.getClass().getName() +
                        "." + name + " in (ms): " + durationMillis);

        Collections.sort(listElement.list);
    });

    listsEqual();
    System.out.println();
}

By extracting this timer code, it makes the individual profiling methods much more concise and focused on what it is they're doing:

private void profileAddFirst(BenchmarkElement element) {
    for (int i = 0; i < ADD_FIRST_OPERATIONS; i++) {
        element.list.add(0, getRandomInteger(element.random));
    }
}

Putting it together

Combining the above, with a few other minor changes (removal of unnecessary boxing, vararg warnings, using the enum name rather than a switch statement) leads to code that's about a third of the size of the original. There's still work that could be done but I think this is a good first step along that journey.

package com.github.coderodde.util.benchmark;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Collectors;

import org.apache.commons.collections4.list.TreeList;

import static java.util.Arrays.asList;

public class LinkedListBenchmark {

    private static final int ADD_FIRST_OPERATIONS = 100_000;
    private static final int ADD_LAST_OPERATIONS = 100_000;
    private static final int ADD_AT_OPERATIONS = 10_000;
    private static final int ADD_COLLECTION_AT_OPERATIONS = 4_000;
    private static final int ADD_LAST_COLLECTION_OPERATIONS = 10_000;
    private static final int REMOVE_VIA_INDEX_OPERATIONS = 10_000;
    private static final int REMOVE_OBJECT_OPERATIONS = 1_000;

    private static final int MAXIMUM_COLLECTION_SIZE = 20;

    private static final int MAXIMUM_INTEGER = 1_000;

    private final long seed;

    private static class BenchmarkElement {
        Random random;
        List<Integer> list;
        long total;

        public BenchmarkElement(List<Integer> list) {
            this.list = list;
            this.total = 0;
        }
    }

    BenchmarkElement linkedList = new BenchmarkElement(new LinkedList<>());
    BenchmarkElement arrayList = new BenchmarkElement(new ArrayList<>());
    BenchmarkElement treeList = new BenchmarkElement(new TreeList<>());
    BenchmarkElement roddeList = new BenchmarkElement(new com.github.coderodde.util.LinkedList<>());

    List<BenchmarkElement> lists = asList(linkedList, arrayList, treeList, roddeList);

    LinkedListBenchmark(long seed) {
        this.seed = seed;
    }

    void warmup() {
        profile(BenchmarkChoice.WARMUP);
    }

    void benchmark() {
        profile(BenchmarkChoice.BENCHMARK);
    }

    private static int getRandomInteger(Random random) {
        return random.nextInt(MAXIMUM_INTEGER + 1);
    }

    private static List<Integer> createRandomCollection(Random random) {
        int size = 1 + random.nextInt(MAXIMUM_COLLECTION_SIZE);

        List<Integer> list = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            list.add(getRandomInteger(random));
        }

        return list;
    }

    private enum BenchmarkChoice {WARMUP, BENCHMARK}

    private void initRandomGenerators() {
        lists.forEach(l -> l.random = new Random(seed));
    }

    private void listsEqual() {
        if (lists.size() < 2) {
            throw new IllegalArgumentException("lists.length < 2");
        }

        for (int i = 0; i < lists.size() - 1; i++) {
            if (lists.get(i).list.size() != lists.get(lists.size() - 1).list.size()) {
                throw new IllegalStateException("Different size");
            }

            Iterator<Integer> iterator1 = lists.get(i).list.iterator();
            Iterator<Integer> iterator2 = lists.get(lists.size() - 1).list.iterator();

            int elementIndex = 0;

            while (iterator1.hasNext() && iterator2.hasNext()) {
                Integer integer1 = iterator1.next();
                Integer integer2 = iterator2.next();

                if (!integer1.equals(integer2)) {
                    throw new IllegalStateException(
                            "Data mismatch: " + integer1 + " vs. " +
                                    integer2 + " at list " + i +
                                    ", element index: " + elementIndex);
                }

                elementIndex++;
            }

            if (iterator1.hasNext() || iterator2.hasNext()) {
                throw new IllegalStateException("Bad iterators");
            }
        }
    }

    private void profile(BenchmarkChoice benchmarkChoice) {

        printTitle(benchmarkChoice);
        initRandomGenerators();

        profileMethod(this::profileAddFirst, "addFirst");
        profileMethod(this::profileAddLast, "addLast");
        profileMethod(this::profileAddIndex, "add(int, E)");
        profileMethod(this::profileAppendCollection, "addAll(Collection)");
        profileMethod(this::profileAddCollection, "addAll(int, Collection)");
        profileMethod(this::profileRemoveViaIndex, "remove(int)");
        profileMethod(this::profileRemoveObject, "remove(Object)");

        ((com.github.coderodde.util.LinkedList<Integer>) roddeList.list).checkInvariant(); // This doesn't seem to be part of what you want to profile?

        profileMethod(this::profileListIteratorAddition, ".iterator().add()");
        profileMethod(this::profileListIteratorRemoval, ".iterator().remove()");
        profileStreamMethod(this::profileStream, "stream()");
        profileStreamMethod(this::profileParallelStream, "stream().parallel()");

        printTotalDurations();

        resetLists();
        zeroTimeDurationCounters();
    }

    private void zeroTimeDurationCounters() {
        lists.forEach(list -> list.total = 0);
    }

    private void resetLists() {
        roddeList.list = new com.github.coderodde.util.LinkedList<>();
        linkedList.list = new java.util.LinkedList<>();
        arrayList.list = new ArrayList<>();
        treeList.list = new TreeList<>();
    }

    private void profileStreamMethod(Function<BenchmarkElement, List<Integer>> method, String name) {
        lists.forEach(listElement -> {
            long startMillis = System.currentTimeMillis();

            List<Integer> newList = method.apply(listElement);

            long endMillis = System.currentTimeMillis();
            long durationMillis = endMillis - startMillis;

            listElement.list.clear();
            listElement.list.addAll(newList);
            listElement.total += durationMillis;

            System.out.println(
                    listElement.list.getClass().getName() +
                            "." + name + " in (ms): " + durationMillis);

            Collections.sort(listElement.list);
        });

        listsEqual();
        System.out.println();
    }

    private void profileMethod(Consumer<BenchmarkElement> method, String name) {
        lists.forEach(listElement -> {
            long startMillis = System.currentTimeMillis();

            method.accept(listElement);

            long endMillis = System.currentTimeMillis();
            long durationMillis = endMillis - startMillis;

            listElement.total += durationMillis;

            System.out.println(listElement.list.getClass().getName() +
                    "." + name + " in (ms): " +
                    durationMillis);
        });

        listsEqual();
        System.out.println();
    }

    private void printTotalDurations() {
        System.out.println("--- Total time elapsed ---");

        lists.forEach(benchmarkElement ->
                System.out.println(
                        benchmarkElement.list.getClass().getName() +
                                " in (ms): " +
                                benchmarkElement.total)
        );
    }

    private void profileAddFirst(BenchmarkElement element) {
        for (int i = 0; i < ADD_FIRST_OPERATIONS; i++) {
            element.list.add(0, getRandomInteger(element.random));
        }
    }

    private void profileAddLast(BenchmarkElement element) {
        for (int i = 0; i < ADD_LAST_OPERATIONS; i++) {
            element.list.add(element.list.size(), getRandomInteger(element.random));
        }
    }

    private void profileAddIndex(BenchmarkElement element) {
        for (int i = 0; i < ADD_AT_OPERATIONS; i++) {
            int index = element.random.nextInt(element.list.size());
            Integer value = getRandomInteger(element.random);
            element.list.add(index, value);
        }
    }

    private void profileAddCollection(BenchmarkElement element) {
        for (int i = 0; i < ADD_COLLECTION_AT_OPERATIONS; i++) {
            List<Integer> collection = createRandomCollection(element.random);
            int index = element.random.nextInt(element.list.size());
            element.list.addAll(index, collection);
        }
    }

    private void profileAppendCollection(BenchmarkElement element) {
        for (int i = 0; i < ADD_LAST_COLLECTION_OPERATIONS; i++) {
            List<Integer> collection = createRandomCollection(element.random);
            element.list.addAll(collection);
        }
    }

    private void profileRemoveViaIndex(BenchmarkElement element) {
        for (int i = 0; i < REMOVE_VIA_INDEX_OPERATIONS; i++) {
            element.list.remove(element.random.nextInt(element.list.size()));
        }
    }

    private void profileRemoveObject(BenchmarkElement element) {
        for (int i = 0; i < REMOVE_OBJECT_OPERATIONS; i++) {
            element.list.remove(getRandomInteger(element.random));
        }
    }

    private void profileListIteratorRemoval(BenchmarkElement element) {
        Iterator<Integer> iterator = element.list.iterator();
        int counter = 0;

        while (iterator.hasNext()) {
            iterator.next();

            // Remove every 2nd element:
            if (counter % 10 == 0) {
                try {
                    iterator.remove();
                } catch (AssertionError ae) {
                    System.err.println(ae.getMessage());
                    System.exit(1);
                }
            }

            counter++;
        }
    }

    private void profileListIteratorAddition(BenchmarkElement element) {
        ListIterator<Integer> iterator = element.list.listIterator(1);
        int counter = 0;

        while (iterator.hasNext()) {
            iterator.next();

            // Remove every 2nd element:
            if (counter % 10 == 0) {
                try {
                    iterator.add(element.random.nextInt(10_000));
                } catch (AssertionError ae) {
                    System.err.println(ae.getMessage());
                    System.exit(1);
                }
            }

            counter++;
        }
    }

    private List<Integer> profileStream(BenchmarkElement element) {
        return element.list.stream().map(x -> 2 * x).collect(Collectors.toList());
    }

    private List<Integer> profileParallelStream(BenchmarkElement element) {
        return element.list.stream()
                .parallel()
                .map(x -> 2 * x)
                .collect(Collectors.toList());
    }

    private void printTitle(BenchmarkChoice benchmarkChoice) {
        System.out.println("=== " + benchmarkChoice.toString() + " RUN ===");
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.