RFR JDK-8022442: Fix unchecked warnings in HashMap

Rémi Forax forax at univ-mlv.fr
Wed Aug 7 17:31:17 UTC 2013

On 08/07/2013 10:57 AM, Peter Levart wrote:

On 08/07/2013 12:23 AM, Dan Smith wrote:

On Aug 6, 2013, at 2:43 PM, Remi Forax <forax at univ-mlv.fr>
<forax at univ-mlv.fr> wrote:

 On 08/06/2013 11:11 PM, Dan Smith wrote:

 Please review this warnings cleanup.

Bug: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=8022442 (not
yet visible)
Webrev: http://cr.openjdk.java.net/~dlsmith/8022442/webrev.00/


 Hi Dan,
I've seen that you have introduce a common super interface for entry
and tree node,
I suppose that  you check that there is no performance regression.
I wonder if an abstract class is not better than an interface because
as far as I know
CHA implemented in hotspot doesn't work on interface
(but I may be wrong, there is perhaps a special optimization for arrays).

 To make sure I understand: your concern is that an aastore will be
more expensive when assigning to a KeyValueData[] than to an Object[]
(or even to SomeOtherClass[])?

For what it's worth, all assignments to table[i] are statically known
to be safe.  E.g.:

Entry<K,V> next = (Entry<K,V>) e.next;
table[i] = next;

So surely a smart VM only does the check once?

Here are some other things that might be concerns, but don't apply here:
- interface method invocations: there are no methods in the interface to invoke
- checkcast to an interface: all the casts are to concrete classes
(Entry, TreeBin, TreeNode)

(There are some unchecked casts from KeyValueData to KeyValueData with
different type parameters, but I assume these don't cause any



Hi Peter,

FWIW, I compiled old and new HashMap.java and did a javap on the classes.

javap outputs: http://cr.openjdk.java.net/~plevart/misc/hm-8022442/

Besides unneeded introduction of local variable discussed already, there
seem to be 4 new checkcasts in the following locations (new HashMap.java):

  public java.util.HashMap(int, float);
       0: aload_0
       1: invokespecial #10                 // Method
       4: aload_0
       5: getstatic     #11                 // Field
*       8: checkcast     #12                 // class
      11: putfield      #13                 // Field
      14: aload_0
      15: aconst_null

  private void inflateTable(int);
      22: aload_0
      23: iload_2
      24: anewarray     #44                 // class
*      27: checkcast     #12                 // class
      30: putfield      #13                 // Field
      33: return

  void resize(int);
      20: return
      21: iload_1
      22: anewarray     #44                 // class
*      25: checkcast     #12                 // class
      28: astore        4
      30: aload_0
      31: aload         4

  private void readObject(java.io.ObjectInputStream) throws
java.io.IOException, java.lang.ClassNotFoundException;
      82: invokevirtual #141                // Method
      85: aload_0
      86: getstatic     #11                 // Field
*      89: checkcast     #12                 // class
      92: putfield      #13                 // Field
      95: aload_1
      96: invokevirtual #142                // Method

...but they are all in the infrequently called methods/constructor.

Regards, Peter

and all these 'checkcast' should be removed at runtime.

I've no problem with the current patch but I think it can be improved by
declaring KeyValueData
as an abstract class (static!) instead as an interface because the VM will
be able to remove
all the instanceof/checkcast that were introduced to deal with the
red/black tree implementation.

By example, when a user calls get, it calls in fact getEntry which is
starts with this code:
   final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        if (key == null) {
            return nullKeyEntry;
        int hash = hash(key);
        int bin = indexFor(hash, table.length);

        if (table[bin] instanceof Entry) {
            Entry<K,V> e = (Entry<K,V>) table[bin];
            for (; e != null; e = (Entry<K,V>)e.next) {
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || key.equals(k))) {
                    return e;

The interesting part is:
  if (table[bin] instanceof Entry) {
            Entry<K,V> e = (Entry<K,V>) table[bin];
(and e = (Entry<K,V>)e.next but it works in a similar way)

The idea is that most of the time, TreeBin and TreeNode are not loaded,
at least until someone tries to DDOS your HashMap,
so in that case the VM knows that the only implementation of KeyValueData
is Entry,
so no check are needed.

here is the generated code for the snippet above if KeyValueData is an
  0x00007f9a710646c1: test   %r8d,%r8d
  0x00007f9a710646c4: je     0x00007f9a7106471d
  0x00007f9a710646c6: mov    0x8(%r8),%r9d
  0x00007f9a710646ca: cmp    $0xc6861040,%r9d   ;
  0x00007f9a710646d1: jne    0x00007f9a71064791  ;*instanceof
                                                ; -
HashMap2::getEntry at 40(line 1047)
                                                ; - HashMap2::get at 2 (line

here is the one if KeyValueData is an abstract class:
  0x00007f2d6d06311d: test   %r11d,%r11d
  0x00007f2d6d063120: je     0x00007f2d6d063165  ;*instanceof
                                                ; -
HashMap2::getEntry at 40(line 1047)
                                                ; - HashMap2::get at 2 (line

as you can see the former code do a nullcheck and then a a quick class
the later only do a nullcheck.

BTW, in getTreeNode(), the local variable 'pl' is assigned but never read
initHashSeed should be static.


More information about the core-libs-dev mailing list