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/
—Dan
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
checkcasts.)
—Dan
Hi,
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/
differences:
http://cr.openjdk.java.net/~plevart/misc/hm-8022442/hm.javap.stripped.diff
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);
Code:
0: aload_0
1: invokespecial #10 // Method
java/util/AbstractMap."<init>":()V
4: aload_0
5: getstatic #11 // Field
EMPTY_TABLE:[Ljava/util/HashMap$KeyValueData;
* 8: checkcast #12 // class
"[Ljava/util/HashMap$KeyValueData;"*
11: putfield #13 // Field
table:[Ljava/util/HashMap$KeyValueData;
14: aload_0
15: aconst_null
...
private void inflateTable(int);
Code:
...
22: aload_0
23: iload_2
24: anewarray #44 // class
java/util/HashMap$KeyValueData
* 27: checkcast #12 // class
"[Ljava/util/HashMap$KeyValueData;"*
30: putfield #13 // Field
table:[Ljava/util/HashMap$KeyValueData;
33: return
...
void resize(int);
Code:
...
20: return
21: iload_1
22: anewarray #44 // class
java/util/HashMap$KeyValueData
* 25: checkcast #12 // class
"[Ljava/util/HashMap$KeyValueData;"*
28: astore 4
30: aload_0
31: aload 4
...
private void readObject(java.io.ObjectInputStream) throws
java.io.IOException, java.lang.ClassNotFoundException;
Code:
...
82: invokevirtual #141 // Method
sun/misc/Unsafe.putIntVolatile:(Ljava/lang/Object;JI)V
85: aload_0
86: getstatic #11 // Field
EMPTY_TABLE:[Ljava/util/HashMap$KeyValueData;
* 89: checkcast #12 // class
"[Ljava/util/HashMap$KeyValueData;"*
92: putfield #13 // Field
table:[Ljava/util/HashMap$KeyValueData;
95: aload_1
96: invokevirtual #142 // Method
java/io/ObjectInputStream.readInt:()I
...
...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
interface:
0x00007f9a710646c1: test %r8d,%r8d
0x00007f9a710646c4: je 0x00007f9a7106471d
0x00007f9a710646c6: mov 0x8(%r8),%r9d
0x00007f9a710646ca: cmp $0xc6861040,%r9d ;
{metadata('HashMap2$Entry')}
0x00007f9a710646d1: jne 0x00007f9a71064791 ;*instanceof
; -
HashMap2::getEntry at 40(line 1047)
; - HashMap2::get at 2 (line
1008)
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
1008)
as you can see the former code do a nullcheck and then a a quick class
check,
the later only do a nullcheck.
BTW, in getTreeNode(), the local variable 'pl' is assigned but never read
and
initHashSeed should be static.
cheers,
Rémi
More information about the core-libs-dev
mailing list