Last active
June 1, 2024 11:25
-
-
Save coderodde/57ed08551cbea8b812f8740c9a3ddb74 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment