StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>At first I suspected it was because HashMap case creates an object on every lookup. </p> <p>However after testing (see below) I believe the problem is that it becomes increasing difficult to get efficient access to the caches.</p> <pre><code>import gnu.trove.TLongLongHashMap; import java.util.HashMap; import java.util.concurrent.Callable; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.TimeUnit; /** * @author peter.lawrey */ public class HashMapPerfMain { public static final int REPEATS = 10000; public static void main(String... args) throws InterruptedException { int runLength = 10 * 1000; HashMap<Long, Long> hashMap = new HashMap<Long, Long>(); TLongLongHashMap troveMap = new TLongLongHashMap(); long[] array = new long[runLength]; for (long i = 0; i < runLength; i++) { long now = System.nanoTime(); hashMap.put(i, now); troveMap.put(i, now); array[((int) i)] = now; } for (int i = 0; i < 3; i++) { timeHashMap(hashMap); timeTroveMap(troveMap); timeArray(array); } } private static void timeHashMap(final HashMap<Long, Long> map) throws InterruptedException { System.out.printf("%-16s ", map.getClass().getSimpleName()); for (int t = 1; t <= Runtime.getRuntime().availableProcessors(); t *= 2) { long start = System.nanoTime(); ExecutorService es = Executors.newFixedThreadPool(t); for (int i = 0; i < t * REPEATS; i++) es.submit(new Callable<Long>() { @Override public Long call() throws Exception { long sum = 20; for (long key = 0; key < map.size(); key++) sum = sum * 19 + map.get(key); return sum; } }); es.shutdown(); es.awaitTermination(10, TimeUnit.MINUTES); long time = System.nanoTime() - start; System.out.printf("%d | %.3f ", t, time / 1e9); } System.out.println(); } private static void timeTroveMap(final TLongLongHashMap map) throws InterruptedException { System.out.printf("%-16s ", map.getClass().getSimpleName()); for (int t = 1; t <= Runtime.getRuntime().availableProcessors(); t *= 2) { long start = System.nanoTime(); ExecutorService es = Executors.newFixedThreadPool(t); for (int i = 0; i < t * REPEATS; i++) es.submit(new Callable<Long>() { @Override public Long call() throws Exception { long sum = 20; for (long key = 0; key < map.size(); key++) sum = sum * 19 + map.get(key); return sum; } }); es.shutdown(); es.awaitTermination(10, TimeUnit.MINUTES); long time = System.nanoTime() - start; System.out.printf("%d | %.3f ", t, time / 1e9); } System.out.println(); } private static void timeArray(final long [] array) throws InterruptedException { System.out.printf("%-16s ", array.getClass().getSimpleName()); for (int t = 1; t <= Runtime.getRuntime().availableProcessors(); t *= 2) { long start = System.nanoTime(); ExecutorService es = Executors.newFixedThreadPool(t); for (int i = 0; i < t * REPEATS; i++) es.submit(new Callable<Long>() { @Override public Long call() throws Exception { long sum = 20; for (int key = 0; key < array.length; key++) sum = sum * 19 + array[key]; return sum; } }); es.shutdown(); es.awaitTermination(10, TimeUnit.MINUTES); long time = System.nanoTime() - start; System.out.printf("%d | %.3f ", t, time / 1e9); } System.out.println(); } } </code></pre> <p>prints</p> <pre><code>HashMap 1 | 0.904 2 | 0.863 4 | 0.913 8 | 1.832 TLongLongHashMap 1 | 0.568 2 | 0.566 4 | 0.572 8 | 1.048 long[] 1 | 0.092 2 | 0.091 4 | 0.090 8 | 0.093 HashMap 1 | 0.767 2 | 0.773 4 | 0.912 8 | 1.833 TLongLongHashMap 1 | 0.560 2 | 0.563 4 | 0.570 8 | 1.057 long[] 1 | 0.088 2 | 0.089 4 | 0.090 8 | 0.096 HashMap 1 | 0.758 2 | 0.774 4 | 0.911 8 | 1.828 TLongLongHashMap 1 | 0.565 2 | 0.564 4 | 0.568 8 | 1.056 long[] 1 | 0.088 2 | 0.089 4 | 0.090 8 | 0.093 </code></pre> <p>array access is very efficient as it linearly scans the memory. HashMaps tend to have the data pseudo randomly arranged in memory, putting a greater burden on the caches.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload