SkipListComparison.java

package fi.helsinki.cs.rodionef;

import com.github.coderodde.util.SkipListMap;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;
import java.util.concurrent.ConcurrentSkipListMap;

public class SkipListComparison {
    
    private static final String INSERT   = "insert";
    private static final String CONTAINS = "contains";
    private static final String DELETE   = "delete";
    private static final Comparator<Integer> CMP = new Comparator<>() {
        
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1.compareTo(02);
        }
    };

    private static final Map<String, Long> DM_SKIP_LIST = new HashMap<>();
    private static final Map<String, Long> DM_C_SKIP_LIST = new HashMap<>();
    private static final Map<String, Long> DM_TREE_MAP = new HashMap<>();
    
    private static final Map<Integer, Boolean> treeMap = new TreeMap<>(CMP);
    private static final Map<Integer, Boolean> concurrentSkipListMap = 
            new ConcurrentSkipListMap<>(CMP);
    
    private static final Map<Integer, Boolean> skipListMap =
            new SkipListMap<>(CMP);
    
    private static final int ITERATIONS = 10;
    
    static {
        DM_SKIP_LIST.put(INSERT, 0L);
        DM_SKIP_LIST.put(DELETE, 0L);
        DM_SKIP_LIST.put(CONTAINS, 0L);
        
        DM_C_SKIP_LIST.put(INSERT, 0L);
        DM_C_SKIP_LIST.put(DELETE, 0L);
        DM_C_SKIP_LIST.put(CONTAINS, 0L);
        
        DM_TREE_MAP.put(INSERT, 0L);
        DM_TREE_MAP.put(DELETE, 0L);
        DM_TREE_MAP.put(CONTAINS, 0L);
    }
    
    public static void main(String[] args) {
        System.out.println("Warming up...");
        warmup();
        System.out.println("Warming up done!");
        System.out.printf("Doing %d benchmark iterations.\n", ITERATIONS);
        
        final int totalIterations = 10;
        
        for (int iter = 0; iter < totalIterations; iter++) { 
            System.out.printf("Iteration: %d.\n", iter);
            
            Integer[] input = getInputIntegerArray();

            long ta = System.currentTimeMillis();

            for (Integer i : input) {
                treeMap.put(i, Boolean.TRUE);
            }

            long tb = System.currentTimeMillis();
            
            DM_TREE_MAP.put(INSERT, tb - ta);

            ta = System.currentTimeMillis();

            for (Integer i : input) {
                concurrentSkipListMap.put(i, Boolean.TRUE);
            }
            
            tb = System.currentTimeMillis();
            
            DM_C_SKIP_LIST.put(INSERT, tb - ta);

            ta = System.currentTimeMillis();

            for (Integer i : input) {
                skipListMap.put(i, Boolean.TRUE);
            }

            tb = System.currentTimeMillis();
            
            DM_SKIP_LIST.put(INSERT, tb - ta);

            ta = System.currentTimeMillis();

            for (int i = 0; i < input.length; i++) {
                treeMap.containsKey(input[i]);
            }

            tb = System.currentTimeMillis();
            
            DM_TREE_MAP.put(CONTAINS, DM_TREE_MAP.get(CONTAINS) + tb - ta);

            ta = System.currentTimeMillis();

            for (int i = 0; i < input.length; i++) {
                concurrentSkipListMap.containsKey(input[i]);
            }

            tb = System.currentTimeMillis();
            
            DM_C_SKIP_LIST.put(CONTAINS, DM_C_SKIP_LIST.get(CONTAINS) + tb - ta);

            ta = System.currentTimeMillis();

            for (int i = 0; i < input.length; i++) {
                skipListMap.containsKey(input[i]);
            }

            tb = System.currentTimeMillis();
            
            DM_SKIP_LIST.put(CONTAINS, DM_SKIP_LIST.get(CONTAINS) + tb - ta);

            Random random = new Random(10);

            ta = System.currentTimeMillis();

            for (int i = 0; i < 1_000_000; i++) {
                treeMap.remove(random.nextInt());
            }

            for (int i = 0; i < input.length; i++) {
                treeMap.remove(input[i]);
            }

            tb = System.currentTimeMillis();
            
            DM_TREE_MAP.put(DELETE, DM_TREE_MAP.get(DELETE) + tb - ta);

            ta = System.currentTimeMillis();

            for (int i = 0; i < 1_000_000; i++) {
                concurrentSkipListMap.remove(random.nextInt());
            }

            for (int i = 0; i < input.length; i++) {
                concurrentSkipListMap.remove(input[i]);
            }

            tb = System.currentTimeMillis();
            
            DM_C_SKIP_LIST.put(DELETE, DM_C_SKIP_LIST.get(DELETE) + tb - ta);

            ta = System.currentTimeMillis();

            for (int i = 0; i < 1_000_000; i++) {
                skipListMap.remove(random.nextInt());
            }

            for (int i = 0; i < input.length; i++) {
                skipListMap.remove(input[i]);
            }

            tb = System.currentTimeMillis();
            
            DM_SKIP_LIST.put(DELETE, DM_SKIP_LIST.get(DELETE) + tb - ta);
        }
        
        printMapStatistics(DM_SKIP_LIST);
        printMapStatistics(DM_C_SKIP_LIST);
        printMapStatistics(DM_TREE_MAP);
        
        printTotalStatistics();
    }
    
    private static String getDataStructureName(Map<String, Long> m) {
        if (m == DM_TREE_MAP) {
            return "TreeMap";
        }
        
        if (m == DM_C_SKIP_LIST) {
            return "ConcurrentSkipListMap";
        }
        
        if (m == DM_SKIP_LIST) {
            return "SkipListMap";
        }
        
        throw new IllegalStateException();
    }
    
    private static long getAverageDuration(Map<String, Long> map, 
                                           String operationName, 
                                           int iterations) {
        return map.get(operationName) / iterations;
    }
    
    private static void printMapStatistics(Map<String, Long> map) {
        
        System.out.printf("%s.%s: %d milliseconds.\n",
                          getDataStructureName(map),
                          INSERT,
                          getAverageDuration(map, INSERT, ITERATIONS));
        
        System.out.printf("%s.%s: %d milliseconds.\n",
                          getDataStructureName(map),
                          CONTAINS,
                          getAverageDuration(map, CONTAINS, ITERATIONS));
        
        System.out.printf("%s.%s: %d milliseconds.\n",
                          getDataStructureName(map),
                          DELETE,
                          getAverageDuration(map, DELETE, ITERATIONS));
    }
    
    private static long getTotalDuration(Map<String, Long> m) {
        long duration = getAverageDuration(m, CONTAINS, ITERATIONS);
        duration += getAverageDuration(m, INSERT, ITERATIONS);
        duration += getAverageDuration(m, DELETE, ITERATIONS);
        
        return duration;
    }
    
    private static void printTotalStatistics() {
        
        System.out.printf("TreeMap: %d milliseconds.\n", 
                          getTotalDuration(DM_TREE_MAP));
        
        System.out.printf("ConcurrentSkipListMap: %d milliseconds.\n", 
                          getTotalDuration(DM_C_SKIP_LIST));
        
        System.out.printf("SkipListMap: %d milliseconds.\n", 
                          getTotalDuration(DM_SKIP_LIST));
    }

    private static Integer[] getInputIntegerArray() {
        Random random = new Random(1);
        Integer[] input = new Integer[1_000_000];

        for (int i = 0; i < input.length; i++) {
            input[i] = random.nextInt(1_000_000);
        }

        return input;
    }
    
    private static void warmup() {
        
        Random random = new Random(100L);
        Integer[] input = getInputIntegerArray();

        for (Integer i : input) {
            treeMap.put(i, Boolean.TRUE);
        }
        
        for (Integer i : input) {
            concurrentSkipListMap.put(i, Boolean.TRUE);
        }

        for (Integer i : input) {
            skipListMap.put(i, Boolean.TRUE);
        }

        for (int i = 0; i < input.length; i++) {
            treeMap.containsKey(input[i]);
        }

        for (int i = 0; i < input.length; i++) {
            concurrentSkipListMap.containsKey(input[i]);
        }

        for (int i = 0; i < input.length; i++) {
            skipListMap.containsKey(input[i]);
        }

        for (int i = 0; i < 1_000_000; i++) {
            treeMap.remove(random.nextInt());
        }

        for (int i = 0; i < input.length; i++) {
            treeMap.remove(input[i]);
        }

        for (int i = 0; i < 1_000_000; i++) {
            concurrentSkipListMap.remove(random.nextInt());
        }

        for (int i = 0; i < input.length; i++) {
            concurrentSkipListMap.remove(input[i]);
        }

        for (int i = 0; i < 1_000_000; i++) {
            skipListMap.remove(random.nextInt());
        }

        for (int i = 0; i < input.length; i++) {
            skipListMap.remove(input[i]);
        }
    }
}