IdentityHashMap.[keySet|values|entrySet].toArray speed-up (original) (raw)

Peter Levart peter.levart at gmail.com
Wed Dec 12 09:07:26 UTC 2012

Hi all,

I propose a patch to java.util.IdentityHashMap to speed-up toArray methods of it's keySet, values and entrySet views:

http://dl.dropbox.com/u/101777488/jdk8-tl/IdentityHashMap/webrev.01/index.html

I toyed with the possibility to replace HashMap-s, that are used in java.lang.Class and java.lang.reflect.[Field|Method|Constructor] to hold cached annotations, with IdentityHashMap-s. They are a perfect replacement, since keys in these maps are java.lang.Class objects.

They are more compact then HashMap-s. This is the comparison of allocated heap bytes between HashMap and IdentityHashMap for various sizes and corresponding capacities which takes into account the size of the Map object, the size of allocated array and the size of Map.Entry-s in case of HM (IHM doesn't have them) and the size of associated values Collection view (allocated when dumping annotations to array). HM-s for annotations are currently allocated with default initial capacity (16). I propose to allocate IHM-s with initial capacity 8 that fits to hold 5 entries which is enough for typical annotation use cases on one hand and still makes improvement for any case on the other:

32 bit JVM:

     |     HashMap     | IdentityHashMap |
 size|capacity    bytes|capacity    bytes|IHM.bytes-HM.bytes

--------+-----------------+-----------------+------------------ 0| 16 144| 8 136| -8 1| 16 168| 8 136| -32 2| 16 192| 8 136| -56 3| 16 216| 8 136| -80 4| 16 240| 8 136| -104 5| 16 264| 8 136| -128 6| 16 288| 16 200| -88 7| 16 312| 16 200| -112 8| 16 336| 16 200| -136 9| 16 360| 16 200| -160 10| 16 384| 16 200| -184 11| 16 408| 16 200| -208 12| 16 432| 32 328| -104 13| 32 520| 32 328| -192 14| 32 544| 32 328| -216 15| 32 568| 32 328| -240 16| 32 592| 32 328| -264 17| 32 616| 32 328| -288 18| 32 640| 32 328| -312 19| 32 664| 32 328| -336 20| 32 688| 32 328| -360 40| 64 1296| 64 584| -712 60| 128 2032| 128 1096| -936 80| 128 2512| 128 1096| -1416 100| 256 3504| 256 2120| -1384 120| 256 3984| 256 2120| -1864 140| 256 4464| 256 2120| -2344 160| 256 4944| 256 2120| -2824 180| 256 5424| 512 4168| -1256

64 bit JVM:

     |     HashMap     | IdentityHashMap |
 size|capacity    bytes|capacity    bytes|IHM.bytes-HM.bytes

--------+-----------------+-----------------+------------------ 0| 16 248| 8 240| -8 1| 16 296| 8 240| -56 2| 16 344| 8 240| -104 3| 16 392| 8 240| -152 4| 16 440| 8 240| -200 5| 16 488| 8 240| -248 6| 16 536| 16 368| -168 7| 16 584| 16 368| -216 8| 16 632| 16 368| -264 9| 16 680| 16 368| -312 10| 16 728| 16 368| -360 11| 16 776| 16 368| -408 12| 16 824| 32 624| -200 13| 32 1000| 32 624| -376 14| 32 1048| 32 624| -424 15| 32 1096| 32 624| -472 16| 32 1144| 32 624| -520 17| 32 1192| 32 624| -568 18| 32 1240| 32 624| -616 19| 32 1288| 32 624| -664 20| 32 1336| 32 624| -712 40| 64 2552| 64 1136| -1416 60| 128 4024| 128 2160| -1864 80| 128 4984| 128 2160| -2824 100| 256 6968| 256 4208| -2760 120| 256 7928| 256 4208| -3720 140| 256 8888| 256 4208| -4680 160| 256 9848| 256 4208| -5640 180| 256 10808| 512 8304| -2504

I hope I've got that tables right. This is the program to compute them:

https://raw.github.com/plevart/jdk8-tl/JEP-149.2/test/src/test/IHMvsHMsizes.java

IHM is also more performant when retrieving the values by keys. The only area in which it lags behind HashMap and is important for accessing annotations in bulk is the toArray method of the values view. In particular for small sizes. The above patch speeds-up those methods by using index iteration instead of Iterator.

Here are some speed-up comparisons:

https://raw.github.com/plevart/jdk8-tl/JEP-149.2/test/IHM_benchmark_results_i7-2600K.txt

They are obtained by running the following micro benchmark:

https://raw.github.com/plevart/jdk8-tl/JEP-149.2/test/src/test/IdentityHashMapTest.java

Even if IHM doesn't replace HM for holding annotations, a speed-up improvement is an improvement.

Regards, Peter

More information about the core-libs-dev mailing list