(coll) Optimize for Empty HashMaps

I am filing this on behalf of Misha Dmitriev.

There are two proposols for the optimization. The first proposal is to leave the table == null. Then add checks for null and respond appropriately. The second proposal is to create a static final zero-length array. When a HashMap is created, its table is set to use this empty array. Then, at the time of the first put(), the table will be resized.

Either way, we can avoid memory waste by empty HashMaps (not completely, but at least a considerable part of waste due to the empty internal array will be gone).

Oops, I realize that this bug needs to be updated. In particular, lazyinithashmap.zip that Nathan mentions in his request, does not exist anymore. So below is what I once wrote on this topic, with correct links and some numbers proving the feasibility of this change.

---------------------------------------------------

I took java.util.HashMap from the most current version of JDK8, modified it to initialize lazily and compared performance of the two implementations. They are on par, see below.

The jar containing all the classes (including Doug Lea's MapMicroBenchmark) and the sources for both the original HashMap (now called StandardHashMapJdk8.java to avoid possible clashes with changes to the standard HashMap in the future) and the modified HashMap (LazyInitHashMapJdk8.java) can be found at http://sunlabs.us.oracle.com/people/misha/mapbm.jar

In LazyInitHashMapJdk8.java, all modified/added code pieces are preceded with '// ***' so that they can be found easily. It is unpolished, and hopefully can be made more elegant if the whole idea is considered worthwhile.

Please let me know if I should do anything else to assist with this.

Here are the performance numbers, using Doug Lea's MapMicroBenchmark, for the standard and lazily-initializing HashMap implementations:

C:\count\mapbm>\java\jdk1.8.0\bin\java -server -Xbootclasspath/a:mapbm.jar java.
util.MapMicroBenchmark java.util.StandardHashMapJdk8
Class java.util.StandardHashMapJdk8 randomized searches
No word file. Using String.valueOf(i)
warm up.........................................................................
.................
warm up.........................................................................
.................
running.........................................................................
.................
Type/Size: 9 36 144 576 2304 9216 36864 147456 589824
Object 16 15 15 15 19 21 25 39 87
String 15 15 14 16 17 25 28 69 101
Integer 15 13 12 12 13 15 18 34 69
Long 16 15 14 14 15 17 22 38 77
Float 18 15 16 17 18 19 27 43 92
Double 17 17 16 15 20 21 23 45 87
BigInteger 19 19 17 18 19 22 26 63 97
BigDecimal 18 19 19 18 22 29 28 70 104
RandomInt 16 15 16 15 19 23 27 51 98
Mixed 23 24 25 29 34 38 48 90 121

average 17 16 16 16 19 23 27 54 93


C:\count\mapbm>\java\jdk1.8.0\bin\java -server -Xbootclasspath/a:mapbm.jar java.
util.MapMicroBenchmark java.util.LazyInitHashMapJdk8
Class java.util.LazyInitHashMapJdk8 randomized searches
No word file. Using String.valueOf(i)
warm up.........................................................................
.................
warm up.........................................................................
.................
running.........................................................................
.................
Type/Size: 9 36 144 576 2304 9216 36864 147456 589824
Object 15 15 15 15 18 21 25 39 89
String 15 16 14 16 17 25 28 68 102
Integer 15 13 13 12 13 14 18 34 70
Long 17 16 15 15 15 18 22 39 78
Float 17 15 16 17 18 19 27 42 92
Double 17 17 16 15 20 21 23 44 87
BigInteger 19 18 17 18 20 23 27 69 103
BigDecimal 18 19 19 18 22 29 28 70 104
RandomInt 17 16 16 16 19 22 27 48 93
Mixed 21 24 25 30 34 39 48 91 126

average 17 16 16 17 19 23 27 54 94
I have attached the zip file with implementations of lazy initialized HashMap and ArrayList. These classes have been tested with ADF Fusion Order Demo and ATG CRM Demo applications. The heap reduction has been 8% and 13% respectively. Average response times decreased 19% and 16%.