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 <fo...@univ-mlv.fr> <fo...@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@40(line 1047) ; - HashMap2::get@2 (line 1008) here is the one if KeyValueData is an abstract class: 0x00007f2d6d06311d: test %r11d,%r11d 0x00007f2d6d063120: je 0x00007f2d6d063165 ;*instanceof ; - HashMap2::getEntry@40(line 1047) ; - HashMap2::get@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
