How do Java Collections perform compared to one another?

Question

So in a Programming Lecture, the lecturer gave us some data on the performance of some Java Collections. He used the data given in this post..

Then my buddies and I decided to test it for ourselves. But our measurements were quite different from those given in the post. We tested 'add', 'contains', 'remove' and 'clear' for the collections listed below. Threw in a few maps in there too.

HashSet TreeSet LinkedHashSet ArrayList LinkedList ArrayDeque PriorityQueue HashMap TreeMap LinkedHashMap

This is our code. We do a 100 test runs and compute the average.

import java.util.*;

public class Testing {
    public void initializeAndRun(int testCases){
        Set<Integer> hashSet = new HashSet<>();
        Set<Integer> treeSet = new TreeSet<>();
        Set<Integer> linkedHashSet = new LinkedHashSet<>();
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        Queue<Integer> arrayDeque = new ArrayDeque<>();
        Map<Integer, Integer> hashMap = new HashMap<>();
        Map<Integer, Integer> treeMap = new TreeMap<>();
        Map<Integer, Integer> linkedHashMap = new LinkedHashMap<>();



        testSet(hashSet, "Hash Set","add", testCases);
        testSet(treeSet, "Tree Set","add", testCases);
        testSet(linkedHashSet, "Linked Hash Set", "add", testCases);
        testList(linkedList, "Linked List", "add", testCases);
        testList(arrayList, "Array List", "add", testCases);
        testQueue(priorityQueue, "Priority Queue", "add", testCases);
        testQueue(arrayDeque, "Array Deque", "add", testCases);
        testMap(hashMap, "Hash Map", "add", testCases);
        testMap(treeMap, "Tree Map", "add", testCases);
        testMap(linkedHashMap, "Linked Hash Map", "add", testCases);


        System.out.println();

        testSet(hashSet, "Hash Set","contains", testCases);
        testSet(treeSet, "Tree Set","contains", testCases);
        testSet(linkedHashSet, "Linked Hash Set", "contains", testCases);
        testList(linkedList, "Linked List", "contains", testCases);
        testList(arrayList, "Array List", "contains", testCases);
        testQueue(priorityQueue, "Priority Queue", "contains", testCases);
        testQueue(arrayDeque, "Array Deque", "contains", testCases);
        testMap(hashMap, "Hash Map", "contains", testCases);
        testMap(treeMap, "Tree Map", "contains", testCases);
        testMap(linkedHashMap, "Linked Hash Map", "contains", testCases);

        System.out.println();

        testSet(hashSet, "Hash Set","remove", testCases);
        testSet(treeSet, "Tree Set","remove", testCases);
        testSet(linkedHashSet, "Linked Hash Set", "remove", testCases);
        testList(linkedList, "Linked List", "remove", testCases);
        testList(arrayList, "Array List", "remove", testCases);
        testQueue(priorityQueue, "Priority Queue", "remove", testCases);
        testQueue(arrayDeque, "Array Deque", "remove", testCases);
        testMap(hashMap, "Hash Map", "remove", testCases);
        testMap(treeMap, "Tree Map", "remove", testCases);
        testMap(linkedHashMap, "Linked Hash Map", "remove", testCases);

        System.out.println();

        testSet(hashSet, "Hash Set","clear", testCases);
        testSet(treeSet, "Tree Set","clear", testCases);
        testSet(linkedHashSet, "Linked Hash Set", "clear", testCases);
        testList(linkedList, "Linked List", "clear", testCases);
        testList(arrayList, "Array List", "clear", testCases);
        testQueue(priorityQueue, "Priority Queue", "clear", testCases);
        testQueue(arrayDeque, "Array Deque", "clear", testCases);
        testMap(hashMap, "Hash Map", "clear", testCases);
        testMap(treeMap, "Tree Map", "clear", testCases);
        testMap(linkedHashMap, "Linked Hash Map", "clear", testCases);

        System.out.println();

    }

    private void loadSet(Set<Integer> input){
        input.clear();
        Random randInt = new Random();
        for(int i = 0; i < 100000; i++){
            Integer x = randInt.nextInt(100000);
            input.add(x);
        }
    }

    private void loadList(List<Integer> input){
        input.clear();
        Random randInt = new Random();
        for(int i = 0; i < 100000; i++){
            Integer x = Integer.valueOf(randInt.nextInt(100000));
            input.add(x);
        }
    }

    private void loadQueue(Queue<Integer> input){
        input.clear();
        Random randInt = new Random();
        for(int i = 0; i < 100000; i++){
            Integer x = Integer.valueOf(randInt.nextInt(100000));
            input.add(x);
        }
    }

    private void loadMap(Map<Integer, Integer> input){
        input.clear();
        Random randInt = new Random();
        for(int i = 0; i < 100000; i++){
            Integer x = Integer.valueOf(randInt.nextInt(100000));
            input.put(x, x);
        }
    }

    private void testSet(Set<Integer> input, String name, String test, int testNo){
        long totalTime = 0;
        long start = 0;
        long end = 0;
        Random rand = new Random();
        for(int i = 0; i < testNo; i++){
            loadSet(input);
            Integer x = Integer.valueOf(rand.nextInt(10000));
            if(test.equals("add")) {
                start = System.nanoTime();
                input.add(x);
                end = System.nanoTime();
                input.remove(x);
            }else if(test.equals("contains")){
                start = System.nanoTime();
                input.contains(x);
                end = System.nanoTime();
            }else if(test.equals("remove")){
                Object[] array =  input.toArray();
                int index = rand.nextInt(array.length);
                int element = (int) array[index];
                start = System.nanoTime();
                input.remove(element);
                end = System.nanoTime();
                input.add(element);
            }else if(test.equals("clear")){
                start = System.nanoTime();

                input.clear();

                end = System.nanoTime();
            }

            totalTime += end - start;
        }

        long averageTime = totalTime/testNo;

        printResult(name, test, averageTime);
    }

    private void testList(List<Integer> input, String name, String test, int testNo){
        long totalTime = 0;
        long start = 0;
        long end = 0;
        Random rand = new Random();
        for(int i = 0; i < testNo; i++){
            loadList(input);
            Integer x = Integer.valueOf(rand.nextInt(10000));
            if(test.equals("add")) {
                start = System.nanoTime();
                input.add(x);
                end = System.nanoTime();
                input.remove(x);
            }else if(test.equals("contains")){
                start = System.nanoTime();
                input.contains(x);
                end = System.nanoTime();
            }else if(test.equals("remove")){
                Object[] array =  input.toArray();
                int index = rand.nextInt(array.length);
                int element = (int) array[index];
                start = System.nanoTime();
                input.remove(element);
                end = System.nanoTime();
                input.add(element);
            }else if(test.equals("clear")){
                start = System.nanoTime();

                input.clear();

                end = System.nanoTime();
            }

            totalTime += end - start;
        }

        long averageTime = totalTime/testNo;

        printResult(name, test, averageTime);
    }

    private void testQueue(Queue<Integer> input, String name, String test, int testNo){
        long totalTime = 0;
        long start = 0;
        long end = 0;
        Random rand = new Random();
        for(int i = 0; i < testNo; i++){
            loadQueue(input);
            Integer x = Integer.valueOf(rand.nextInt(10000));
            if(test.equals("add")) {
                start = System.nanoTime();
                input.add(x);
                end = System.nanoTime();
                input.remove(x);
            }else if(test.equals("contains")){
                start = System.nanoTime();
                input.contains(x);
                end = System.nanoTime();
            }else if(test.equals("remove")){
                Object[] array =  input.toArray();
                int index = rand.nextInt(array.length);
                int element = (int) array[index];
                start = System.nanoTime();
                input.remove(element);
                end = System.nanoTime();
                input.add(element);
            }else if(test.equals("clear")){
                start = System.nanoTime();

                input.clear();

                end = System.nanoTime();
            }

            totalTime += end - start;
        }

        long averageTime = totalTime/testNo;

        printResult(name, test, averageTime);
    }

    private void testMap(Map<Integer, Integer> input, String name, String test, int testNo){
        long totalTime = 0;
        long start = 0;
        long end = 0;
        Random rand = new Random();
        for(int i = 0; i < testNo; i++){
            loadMap(input);
            Integer x = Integer.valueOf(rand.nextInt(10000));
            if(test.equals("add")) {
                start = System.nanoTime();
                input.put(x, x);
                end = System.nanoTime();
                input.remove(x, x);
            }else if(test.equals("contains")){
                start = System.nanoTime();
                input.containsKey(x);
                end = System.nanoTime();
            }else if(test.equals("remove")){
                Set<Integer> keysSet = input.keySet();
                Integer[] array = new Integer[keysSet.size()];
                keysSet.toArray(array);
                int index = rand.nextInt(array.length);
                int element = (int) array[index];
                start = System.nanoTime();
                input.remove(element);
                end = System.nanoTime();
                input.put(element, element);
            }else if(test.equals("clear")){
                start = System.nanoTime();

                input.clear();

                end = System.nanoTime();
            }

            totalTime += end - start;
        }

        long averageTime = totalTime/testNo;

        printResult(name, test, averageTime);
    }

    private void printResult(String name, String test, long averageTime){
        System.out.printf("%s: %s: %d ns%n", name,test, averageTime);
    }

    public static void main(String[] args){
        Testing test = new Testing();
        int testCases = 100;
        test.initializeAndRun(testCases);
    }
}

And it gave the following output: Hash Set: add: 225 ns

Tree Set: add: 430 ns

Linked Hash Set: add: 46 ns

Linked List: add: 61 ns

Array List: add: 33 ns

Priority Queue: add: 45 ns

Array Deque: add: 55 ns

Hash Map: add: 40 ns

Tree Map: add: 166 ns

Linked Hash Map: add: 43 ns

Hash Set: contains: 235 ns

Tree Set: contains: 456 ns

Linked Hash Set: contains: 57 ns

Linked List: contains: 163147 ns

Array List: contains: 45355 ns

Priority Queue: contains: 35929 ns

Array Deque: contains: 53337 ns

Hash Map: contains: 90 ns

Tree Map: contains: 380 ns

Linked Hash Map: contains: 51 ns

Hash Set: remove: 506 ns

Tree Set: remove: 1236 ns

Linked Hash Set: remove: 150 ns

Linked List: remove: 54833 ns

Array List: remove: 16115 ns

Priority Queue: remove: 31837 ns

Array Deque: remove: 35739 ns

Hash Map: remove: 110 ns

Tree Map: remove: 823 ns

Linked Hash Map: remove: 129 ns

Hash Set: clear: 32998 ns

Tree Set: clear: 322 ns

Linked Hash Set: clear: 33273 ns

Linked List: clear: 213397 ns

Array List: clear: 24334 ns

Priority Queue: clear: 25343 ns

Array Deque: clear: 45598 ns

Hash Map: clear: 33457 ns

Tree Map: clear: 27 ns

Linked Hash Map: clear: 33289 ns

As you can see, results like the 'clear' on TreeSet, when compared to others don't match at all with the values given in the lecture (the ones in the post).

Are we doing something wrong? I mean, we must be! What is it? Any help please?

We tried writing our own code, as shown above. We looked at it for ages but couldn't figure anything out. Please keep in mind that we are beginner Java programmers; only been learning for 3 weeks.

Answer 1

Are we doing something wrong? I mean, we must be! What is it? Any help please?

Why? The post you linked to has no code to verify their results. It doesn't even list the JVM and architecture the test was run on.

TreeSet.clear is fast. At least, it is on JDK21; I haven't looked at earlier versions, however, I'm pretty sure it has always worked this way:

• TreeSet is nothing - it just creates a TreeMap and relegates every call to the map. The keys in this map are the values in your treeset; the values are irrelevant (PRESENT - a single new Object() made just to have some 'value' to map these keys to).
• Therefore ts.clear() just invokes the clear() method of the map that TreeSet is built on.
• TreeMap's clear does 3 things: It updates a pointer (writes a single word to a field), it increments an int field, and it sets another int field to 0. In other words, it reads in one of its fields then writes to 3 of its fields. This is a single cachepage operation that runs in about 1 clockcycle on a sufficiently pipeline-capable CPU (i.e. all of them but phone CPUs and raspberry pis, pretty much). It's hard to imagine anything that's faster.

Thus, 'TreeSet.clear is slow' is total horse manure, and the linked-to medium article, which has no code, no details on how that code was written or run, and at least one incredibly dubious result, should be disregarded entirely.

You should direct your professor to this question, and ensure they no longer spread this cruft to future students. Your fellow/future students thank you!