IndexListVsSkipListComparison.java

package fi.helsinki.cs.rodionef.msc;

import com.github.coderodde.util.IndexedLinkedList;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.ConcurrentSkipListMap;

public class IndexListVsSkipListComparison {

    private static long durationTm = 0L;
    private static long durationIll = 0L;
    private static long durationCslm = 0L;

    private static final IndexedLinkedList<Integer> ill = 
            new IndexedLinkedList<>();
    
    private static final Map<Integer, Boolean> cslm = 
            new ConcurrentSkipListMap<>();
    
    private static final Map<Integer, Boolean> tm = new TreeMap<>();
    
    public static void main(String[] args) {
        System.out.println("Warming up...");
        System.out.println();
        warmup();
        System.out.println();
        benchmark();
    }
    
    private static void warmup() {
        runBenchmark(false);
    }
    
    private static void benchmark() {
        runBenchmark(true);
    }
    
    private static void runBenchmark(boolean doPrint) {
        tm.clear();
        ill.clear();
        cslm.clear();
        
        durationCslm = benchmarkConcurrentSkipListMap(doPrint);
        durationTm = benchmarkTreeMap(doPrint);
        durationIll = benchmarkIndexedLinkedList(doPrint);
        
        if (doPrint) {
            System.out.println("--- TOTAL ---");
            System.out.printf(
                    "ConcurrentSkipListMap: %d milliseconds.\n",
                    durationCslm);
            
            System.out.printf(
                    "TreeMap: %d milliseconds.\n",
                    durationTm);
            
            System.out.printf(
                    "IndexedLinkedList: %d milliseconds.\n",
                    durationIll);
        }
    }
    
    /**
     * Runs all the four benchmarks on {@link java.util.concurrent.ConcurrentSkipListMap}.
     * 
     * @param doPrint the boolean flag. If set, prints the statistics.
     * 
     * @return the total duration of all the benchmarks.
     */
    private static long benchmarkConcurrentSkipListMap(boolean doPrint) {
        long dataStructureDuration = 0L;
        long operationDuration;
        
        dataStructureDuration += (operationDuration = benchmarkConcurrentSkipListAddAsc());
        
        if (doPrint) {
            System.out.printf("CSLM.Add-asc in %d milliseconds.\n", operationDuration);
        }
        
        dataStructureDuration += (operationDuration = benchmarkConcurrentSkipListRemoveAsc());
        
        if (doPrint) {
            System.out.printf("CSLM.Remove-asc in %d milliseconds.\n", operationDuration);
        }
        
        dataStructureDuration += (operationDuration = benchmarkConcurrentSkipListAddDesc());
        
        if (doPrint) {
            System.out.printf("CSLM.Add-desc in %d milliseconds.\n", operationDuration);
        }
        
        dataStructureDuration += (operationDuration = benchmarkConcurrentSkipListRemoveDesc());
        
        if (doPrint) {
            System.out.printf("CSLM.Remove-desc in %d milliseconds.\n", operationDuration);
        }
        
        return dataStructureDuration;
    }
    
    private static long benchmarkConcurrentSkipListAddAsc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 0; i < 1_000_000; i++) {
            cslm.put(i, Boolean.FALSE);
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    private static long benchmarkConcurrentSkipListAddDesc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 999_999; i >= 0; i--) {
            cslm.put(i, Boolean.FALSE);
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    private static long benchmarkConcurrentSkipListRemoveAsc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 0; i < 1_000_000; i++) {
            cslm.remove(i);
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    private static long benchmarkConcurrentSkipListRemoveDesc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 999_999; i >= 0; i--) {
            cslm.remove(i);
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    /**
     * Runs all the four benchmarks on {@link java.util.TreeMap}.
     * 
     * @param doPrint the boolean flag. If set, prints the statistics.
     * 
     * @return the total duration of all the benchmarks.
     */
    private static long benchmarkTreeMap(boolean doPrint) {
        long dataStructureDuration = 0L;
        long operationDuration;
        
        dataStructureDuration += (operationDuration = benchmarkTreeMapAddAsc());
        
        if (doPrint) {
            System.out.printf("TM.Add-asc in %d milliseconds.\n", operationDuration);
        }
        
        dataStructureDuration += (operationDuration = benchmarkTreeMapRemoveAsc());
        
        if (doPrint) {
            System.out.printf("TM.Remove-asc in %d milliseconds.\n", operationDuration);
        }
        
        dataStructureDuration += (operationDuration = benchmarkTreeMapAddDesc());
        
        if (doPrint) {
            System.out.printf("TM.Add-desc in %d milliseconds.\n", operationDuration);
        }
        
        dataStructureDuration += (operationDuration = benchmarkTreeMapRemoveDesc());
        
        if (doPrint) {
            System.out.printf("TM.Remove-desc in %d milliseconds.\n", operationDuration);
        }
        
        return dataStructureDuration;
    }
    
    private static long benchmarkTreeMapAddAsc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 0; i < 1_000_000; i++) {
            tm.put(i, Boolean.FALSE);
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    private static long benchmarkTreeMapAddDesc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 999_999; i >= 0; i--) {
            tm.put(i, Boolean.FALSE);
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    private static long benchmarkTreeMapRemoveAsc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 0; i < 1_000_000; i++) {
            tm.remove(i);
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    private static long benchmarkTreeMapRemoveDesc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 999_999; i >= 0; i--) {
            tm.remove(i);
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    /**
     * Runs all the four benchmarks on {@linkplain SkipList}.
     * 
     * @param doPrint the boolean flag. If set, prints the statistics.
     * 
     * @return the total duration of all the benchmarks.
     */
    private static long benchmarkIndexedLinkedList(boolean doPrint) {
        long dataStructureDuration = 0L;
        long operationDuration;
        
        dataStructureDuration += (operationDuration = benchmarkIndexedLinkedListAddAsc());
        
        if (doPrint) {
            System.out.printf("ILL.Add-asc in %d milliseconds.\n", operationDuration);
        }
        
        dataStructureDuration += (operationDuration = benchmarkIndexedLinkedListRemoveAsc());
        
        if (doPrint) {
            System.out.printf("ILL.Remove-asc in %d milliseconds.\n", operationDuration);
        }
        
        dataStructureDuration += (operationDuration = benchmarkIndexedLinkedListAddDesc());
        
        if (doPrint) {
            System.out.printf("ILL.Add-desc in %d milliseconds.\n", operationDuration);
        }
        
        dataStructureDuration += (operationDuration = benchmarkIndexedLinkedListRemoveDesc());
        
        if (doPrint) {
            System.out.printf("ILL.Remove-desc in %d milliseconds.\n", operationDuration);
        }
        
        return dataStructureDuration;
    }
    
    private static long benchmarkIndexedLinkedListAddAsc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 0; i < 1_000_000; i++) {
            ill.addLast(i);
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    private static long benchmarkIndexedLinkedListAddDesc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 999_999; i >= 0; i--) {
            ill.addFirst(i);
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    private static long benchmarkIndexedLinkedListRemoveAsc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 0; i < 1_000_000; i++) {
            ill.removeFirst();
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
    
    private static long benchmarkIndexedLinkedListRemoveDesc() {
        long ta = System.currentTimeMillis();
       
        for (int i = 999_999; i >= 0; i--) {
            ill.removeLast();
        }
        
        long tb = System.currentTimeMillis();
        
        return tb - ta;
    }
}