JDK-8003586 : HashMap arrays should be lazily allocated
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Priority: P4
  • Status: Open
  • Resolution: Unresolved
  • Submitted: 2012-11-17
  • Updated: 2014-09-15
Related Reports
Blocks :  
JDK-8003585 - strength reduce or eliminate range checks for power-of-two sized arrays
Relates :  
JDK-7143928 - (coll) Optimize for Empty HashMaps
Description
According to JDK-8003585, we can strength-reduce the array range check in HashMap.getEntry to a simple check whether table.length is zero or not.

A side effect of this is that an explicit zero check in this place has no additional cost, since it is done implicitly.  Therefore code to lazily create tables has little or no downside, if the "lazy" state is a zero-length table.

This is better than using a null pointer as a sentinel for an unallocated table, because it does not force the compiler to deal with the null case.

(The compiler prefers to use "implicit" null checks, which are a side effect of taking a SEGV trap when loading through an address that is assumed to be non-null.)
Comments
The code changes proposed to HashMap are not needed until the JIT can do the optimizations in JDK-8003585. Also, the modified HashMap should be tested against the JIT to make sure the optimizations kick in as expected.
25-04-2013
An implementation of hash map with lazily created tables is now in JDK8 under JDK-7143928: http://hg.openjdk.java.net/jdk8/jdk8/jdk/diff/0cccdb9a9a4c/src/share/classes/java/util/HashMap.java The pre-inflated state of the hash map is represented with a zero-length table, of which there is only one: static final Entry<?,?>[] EMPTY_TABLE = {}; This change set uses an "acmp" (reference ==) to detect zero-length arrays: + if (table == EMPTY_TABLE) { + inflateTable(threshold); + } An equivalent predicate would be: + if (table.length == 0) { + inflateTable(threshold); + } This check for zero would be preferable in the presence of range check elimination (optimization JDK-8003585), since the table.length value will be needed anyway in the inlined code. The class is designed with an invariant that ensures the two predicates are logically identical. (The only zero-length array that can be found in HashMap.table is the EMPTY_TABLE.) But the optimizing JIT does not know this invariant, and so it cannot assume that, when table != EMPTY_TABLE, that the length field will necessary be non-zero. (BTW, it appears that roundUpToPowerOf2 can return zero or a negative number, if given a sufficiently strange input. This might cause odd bugs in deserialization. It appears that the constructors ensure that table length is never unintentionally zero.) I suggest using table.length == 0 for the inflation check, and ensuring that the JIT can see a non-zero length on succeeding paths. The easy way to ensure this is to have a separate call to put after inflation: public V put(K key, V value) { if (table.length == 0) return inflateAndPut(key, value); if (key == null) return putForNullKey(value);
25-04-2013