IdentityHashMap.[keySet|values|entrySet].toArray speed-up
Peter Levart
peter.levart at gmail.com
Thu Feb 14 13:24:28 UTC 2013
Hello Mike,
On 02/13/2013 09:21 PM, Mike Duigou wrote:
> 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.
It would if IdentityHashMap was used instead of HashMap for annotations
caching. But that's something that should be done on the global basis
(there are various places where Maps of annotations are constructed:
reflection classes, AnnotationParser, ...).
There's also opportunity to use IdentityHashMap instead of LinkedHashMap
(totally unnecessary, since it is never iterated !!??) for holding
member values of annotation instances (the Map is keyed by String
objects, but they could be interned at map creation time - the same
string values are interned already, since they are equal to names of
methods of the annotation interfaces and retrieval is already using the
interned Strings: Method.getName() - see AnnotationInvocationHandler)...
Let me know if testing finds anything or if there's anything I can do
(regarding coding style, etc).
Regards, Peter
>
> 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
>>
More information about the core-libs-dev
mailing list