This looks like excellent contribution Peter! I will proceed with the testing needed to integrate your improved toArray()/toArray(T[]) implementations. I have created an issue, JDK-8008167, for this patch.
I am surprised that this didn't get more attention back in December as it does seem to offer significant benefits for size and performance. Thanks, Mike On Dec 12 2012, at 01:07 , Peter Levart wrote: > 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 >
