IdentityHashMap.[keySet|values|entrySet].toArray speed-up

[Peter Levart]

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