{"id":2548,"date":"2017-01-21T13:45:03","date_gmt":"2017-01-21T12:45:03","guid":{"rendered":"http:\/\/sahits.ch\/blog\/?p=2548"},"modified":"2017-01-22T07:36:36","modified_gmt":"2017-01-22T06:36:36","slug":"alternative-approaches-for-maps-with-primitive-values","status":"publish","type":"post","link":"http:\/\/sahits.ch\/blog\/blog\/2017\/01\/21\/alternative-approaches-for-maps-with-primitive-values\/","title":{"rendered":"Alternative approaches for Maps with primitive values"},"content":{"rendered":"

While profiling the current state of OpenPatrician<\/a> I noted that there are maps that are quite memory intensive and they have primitive values. As the map cannot hold primitive values they need to be boxed into their corresponding object, which adds overhead. Therefore I asked about alternative approaches<\/a>. To figure out what meets my requirement best I did a small benchmark of my own comparing some of the available collection libraries.<\/p>\n

<\/p>\n

The contestants<\/h2>\n

The contestants were the HashMap and ConcurrentHashMap from the JDK mainly for the baseline to compare to. Then there is the MutableObjectDoubleMap<\/a> from the Eclipse Collection<\/a> framework (formerly Goldman Sachs (GS)), then the TObjectDoubleHashMap<\/a> from the Trove<\/a> library. Further the ObjectDoubleScatterMap<\/a> of the High Performance Primitive Collections<\/a> by Carrotsearch and finally from FastUtil<\/a> the Object2DoubleLinkedOpenHashMap<\/a>.<\/p>\n

The setup and meassure requirements<\/h2>\n

Into each map like structure 300’000 key-value pairs are inserted. The keys are the index of the insertion into the map to ensure uniqueness of the keys. Values are random numbers in the range [0,1).<\/p>\n

Measured is the total time it takes to insert all the 300’000 entries into the map, which includes the generation of the random numbers. Insertion of new value does not have a high importance as the bulk is inserted during initialisation and very few new entries are added later on. More important is the lookup which happens quite often and should therefore be performant. The timing here happend by doing 1’000 lookups of keys that are present in the map and then averaging the time it took.<\/p>\n

Finally the memory consumption is looked at using VisualVM by doing a heap dump and taking a look at the retained memory for the maps.<\/p>\n

The Code<\/h2>\n
public class CollectionComparison {\r\n\r\n    private static final int MAX_ENTRIES = 300000;\r\n    private Random rnd = new Random();\r\n\r\n    private Map<String, Double> baseJDKHashMap = new HashMap<>();\r\n    private Map<String, Double> concurrentJDKHashMap = new ConcurrentHashMap<>();\r\n    private MutableObjectDoubleMap<String> mutableEclipseMap = ObjectDoubleMaps.mutable.empty();\r\n    private TObjectDoubleMap<String> troveMap = new TObjectDoubleHashMap<>();\r\n    private ObjectDoubleMap<String> hppcMap = new ObjectDoubleScatterMap<>();\r\n    private Object2DoubleMap<String> fastUtilMap = new Object2DoubleLinkedOpenHashMap();\r\n\r\n    public static void main(String[] args) {\r\n        CollectionComparison comparison = new CollectionComparison();\r\n\r\n        comparison.fillJDKHashMap();\r\n        comparison.fillJDKConcurrentHashMap();\r\n        comparison.fillEclipseMap();\r\n        comparison.fillTroveMap();\r\n        comparison.fillHPPCMap();\r\n        comparison.fillFastUtilMap();\r\n\r\n        comparison.lookupBenchmark();\r\n\r\n        System.out.println(\"Please take heap dump\");\r\n\r\n        try {\r\n            Thread.sleep(5 * 60 * 1000l);   \/\/ Wait so a heap dump can be taken\r\n        } catch (InterruptedException e) {\r\n            e.printStackTrace();\r\n        }\r\n    }\r\n\r\n\r\n\r\n    private void fillJDKHashMap() {\r\n        long start = System.currentTimeMillis();\r\n        for (int i = 0; i < MAX_ENTRIES; i++) {\r\n            double next = rnd.nextDouble();\r\n            String key = String.valueOf(i); \/\/ ensure unique keys\r\n            baseJDKHashMap.put(key, next);\r\n        }\r\n        long took = System.currentTimeMillis() - start;\r\n        System.out.println(\"Filling in \"+MAX_ENTRIES+\" into the JDK HashMap took \"+took+\"ms\");\r\n    }\r\n\r\n    private void fillJDKConcurrentHashMap() {\r\n        long start = System.currentTimeMillis();\r\n        for (int i = 0; i < MAX_ENTRIES; i++) {\r\n            double next = rnd.nextDouble();\r\n            String key = String.valueOf(i); \/\/ ensure unique keys\r\n            concurrentJDKHashMap.put(key, next);\r\n        }\r\n        long took = System.currentTimeMillis() - start;\r\n        System.out.println(\"Filling in \"+MAX_ENTRIES+\" into the JDK ConcurrentHashMap took \"+took+\"ms\");\r\n    }\r\n    private void fillEclipseMap() {\r\n        long start = System.currentTimeMillis();\r\n        for (int i = 0; i < MAX_ENTRIES; i++) {\r\n            double next = rnd.nextDouble();\r\n            String key = String.valueOf(i); \/\/ ensure unique keys\r\n            mutableEclipseMap.addToValue(key, next);\r\n        }\r\n        long took = System.currentTimeMillis() - start;\r\n        System.out.println(\"Filling in \"+MAX_ENTRIES+\" into the Eclipse map took \"+took+\"ms\");\r\n    }\r\n    private void fillTroveMap() {\r\n        long start = System.currentTimeMillis();\r\n        for (int i = 0; i < MAX_ENTRIES; i++) {\r\n            double next = rnd.nextDouble();\r\n            String key = String.valueOf(i); \/\/ ensure unique keys\r\n            troveMap.put(key, next);\r\n        }\r\n        long took = System.currentTimeMillis() - start;\r\n        System.out.println(\"Filling in \"+MAX_ENTRIES+\" into the Trove map took \"+took+\"ms\");\r\n    }\r\n\r\n    private void fillHPPCMap() {\r\n        long start = System.currentTimeMillis();\r\n        for (int i = 0; i < MAX_ENTRIES; i++) {\r\n            double next = rnd.nextDouble();\r\n            String key = String.valueOf(i); \/\/ ensure unique keys\r\n            hppcMap.addTo(key, next);\r\n        }\r\n        long took = System.currentTimeMillis() - start;\r\n        System.out.println(\"Filling in \"+MAX_ENTRIES+\" into the HPPC map took \"+took+\"ms\");\r\n    }\r\n\r\n    private void fillFastUtilMap() {\r\n        long start = System.currentTimeMillis();\r\n        for (int i = 0; i < MAX_ENTRIES; i++) {\r\n            double next = rnd.nextDouble();\r\n            String key = String.valueOf(i); \/\/ ensure unique keys\r\n            fastUtilMap.put(key, next);\r\n        }\r\n        long took = System.currentTimeMillis() - start;\r\n        System.out.println(\"Filling in \"+MAX_ENTRIES+\" into the FastUtil map took \"+took+\"ms\");\r\n    }\r\n\r\n    private void lookupBenchmark() {\r\n        long jdkHashMapTime = 0;\r\n        long jdkConcurrentMapTime = 0;\r\n        long eclipseMapTime = 0;\r\n        long troveMapTime = 0;\r\n        long hppcMapTime = 0;\r\n        long fastUtilMapTime = 0;\r\n        final int nbLookups = 1000;\r\n        for (int i = 0; i < nbLookups; i++) {\r\n            int nextIndex = rnd.nextInt(MAX_ENTRIES);\r\n            String key = String.valueOf(nextIndex);\r\n            long start = System.nanoTime();\r\n            boolean contained = baseJDKHashMap.containsKey(key);\r\n            long took = System.nanoTime() - start;\r\n            jdkHashMapTime += took;\r\n            assertTrue(contained);\r\n\r\n            start = System.nanoTime();\r\n            contained = concurrentJDKHashMap.containsKey(key);\r\n            took = System.nanoTime() - start;\r\n            jdkConcurrentMapTime += took;\r\n            assertTrue(contained);\r\n\r\n            start = System.nanoTime();\r\n            contained = mutableEclipseMap.containsKey(key);\r\n            took = System.nanoTime() - start;\r\n            eclipseMapTime += took;\r\n            assertTrue(contained);\r\n\r\n            start = System.nanoTime();\r\n            contained = troveMap.containsKey(key);\r\n            took = System.nanoTime() - start;\r\n            troveMapTime += took;\r\n            assertTrue(contained);\r\n\r\n            start = System.nanoTime();\r\n            contained = hppcMap.containsKey(key);\r\n            took = System.nanoTime() - start;\r\n            hppcMapTime += took;\r\n            assertTrue(contained);\r\n\r\n            start = System.nanoTime();\r\n            contained = fastUtilMap.containsKey(key);\r\n            took = System.nanoTime() - start;\r\n            fastUtilMapTime += took;\r\n            assertTrue(contained);\r\n        }\r\n        System.out.println(nbLookups+\" lookups average in JDK HashMap took: \"+ (jdkHashMapTime\/nbLookups)+\"ns\");\r\n        System.out.println(nbLookups+\" lookups average in JDK Concurrent HashMap took: \"+ (jdkConcurrentMapTime\/nbLookups)+\"ns\");\r\n        System.out.println(nbLookups+\" lookups average in Eclipse Map took: \"+ (eclipseMapTime\/nbLookups)+\"ns\");\r\n        System.out.println(nbLookups+\" lookups average in Trove Map took: \"+ (troveMapTime\/nbLookups)+\"ns\");\r\n        System.out.println(nbLookups+\" lookups average in HPPC Map took: \"+ (hppcMapTime\/nbLookups)+\"ns\");\r\n        System.out.println(nbLookups+\" lookups average in FastUtil Map took: \"+ (fastUtilMapTime\/nbLookups)+\"ns\");\r\n    }\r\n}<\/pre>\n
The Results<\/h2>\n
Comparison of the various maps delivered the following results:<\/p>\n
Filling in 300000 into the JDK HashMap took 107ms\r\nFilling in 300000 into the JDK ConcurrentHashMap took 152ms\r\nFilling in 300000 into the Eclipse map took 107ms\r\nFilling in 300000 into the Trove map took 855ms\r\nFilling in 300000 into the HPPC map took 93ms\r\nFilling in 300000 into the FastUtil map took 163ms\r\n1000 lookups average in JDK HashMap took: 550ns\r\n1000 lookups average in JDK Concurrent HashMap took: 748ns\r\n1000 lookups average in Eclipse Map took: 894ns\r\n1000 lookups average in Trove Map took: 1033ns\r\n1000 lookups average in HPPC Map took: 523ns\r\n1000 lookups average in FastUtil Map took: 680ns\r\nJDK HashMap:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 43'809'895B\r\nJDK Concurrent HashMap: 43'653'740B => save\u00a0 0.36%\r\nEclipse Map:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 35'755'084B => save 18.39%\r\nTrove Map:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 32'147'798B => save 26.62%\r\nHPPC Map:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 27'366'533B => save 37.53%\r\nFastUtil Map:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 31'560'889B => save 27.96%\r\n\r\n<\/pre>\n
Conclusion<\/h2>\n
Surprisingly the ConcurrentHashMap requires slightly less memory than the HashMap. While the Trove library is memory wise in the middle it’s performance is abominable: On insertions it’s 8x slower than the HashMap and on the lookup it still requires the double time. Here the tradeof for memory versus performance just does not hold up especially when comparing with other libraries that range similarly.<\/p>\n
The one Map implementation that clearly swings out above the others is the ObjectDoubleScatterMap<\/a> of HPPC: Insertion seems to be at least as good as with a HashMap. The performance on insertion is very dependent on the inserted keys, because when there are a lot of collisions during insertion, this has a negative effect. The lookup time is also comparable to the one of the HashMap, which no other framework can claim. And finally the saved memory for a map with primitive double values for types is about 1\/3.<\/p>\n
If you are interested in a closer look at the performance, I can suggest this comparison<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
While profiling the current state of OpenPatrician I noted that there are maps that are quite memory intensive and they have primitive values. As the map cannot hold primitive values they need to be boxed into their corresponding object, which adds overhead. Therefore I asked about alternative approaches. To figure out what meets my requirement … \u201eAlternative approaches for Maps with primitive values\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[138,7,6],"tags":[301,311,312,313],"class_list":["post-2548","post","type-post","status-publish","format-standard","hentry","category-it","category-java","category-programmieren","tag-java","tag-map","tag-memory","tag-performance"],"_links":{"self":[{"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/posts\/2548","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/comments?post=2548"}],"version-history":[{"count":5,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/posts\/2548\/revisions"}],"predecessor-version":[{"id":2554,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/posts\/2548\/revisions\/2554"}],"wp:attachment":[{"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/media?parent=2548"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/categories?post=2548"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/sahits.ch\/blog\/wp-json\/wp\/v2\/tags?post=2548"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}