JDK-8210280 - Unnecessary reallocation when invoking HashMap.putAll()

[Michal Vala]

Hi,

here's the new webrev: 
http://cr.openjdk.java.net/~mvala/jdk/jdk/JDK-8210280/webrev.02/

I solved the issue by incrementally doubling the new table, before adding new 
elements. This solution has no such performance boost as first buggy one, it's 
still measurable for case when adding big map to another, small non-empty map. 
This is faster because doubling happens with a lot less elements than it would 
happen while adding new elements.

one of benchmark runs
clean upstream:
HashMapBench.putAllWithBigMapToNonEmptyMap  avgt   10  189.055 ± 12.911  ms/op

with patch:
HashMapBench.putAllWithBigMapToNonEmptyMap  avgt   10  211.921 ± 23.793  ms/op



I've also tried generic approach without holding head and tail pointers to the 
bucket. However, need of preserve the order kills this solution. Tail pointer 
boost is too good.
Another generic approach would be to hold tail pointers just where needed, but I 
couldn't find effective solution for now (without e.g. having second table of 
the same size, which is killer).


I'm still looking into removeEldestEntry with LinkedHashMap.


On 12/14/18 7:37 AM, Michal Vala wrote:
> Thanks Martin for finding this serious issue and the testcase.
> 
> I understand the issue, but so far I've been unable to find effective enough 
> solution that beats high/low head/tail bucket splitting. I'll keep looking into 
> it and I'll propose a new patch or write some summary and results of my 
> experiments. Probably next week.
> 
> On 12/12/18 9:16 PM, Martin Buchholz wrote:
>> Software is hard.
>>
>> I found myself removing the remaining style changes to be able to review
>> the changes.
>> (We're going to have to disagree about the value of curlies).
>> Here's my reduction:
>>
>> --- src/main/java/util/HashMap.java 11 Nov 2018 16:27:28 -0000 1.9
>> +++ src/main/java/util/HashMap.java 12 Dec 2018 20:10:03 -0000
>> @@ -503,7 +503,7 @@
>>                       threshold = tableSizeFor(t);
>>               }
>>               else if (s > threshold)
>> -                resize();
>> +                resize(s);
>>               for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
>>                   K key = e.getKey();
>>                   V value = e.getValue();
>> @@ -661,6 +661,30 @@
>>       }
>>
>>       /**
>> +     * Resizes the table to the nearest power of two to {@code size}.
>> +     * Moves all items to the new table.
>> +     *
>> +     * @param size expected number of elements in the new table
>> +     * @return the table
>> +     */
>> +    final Node<K,V>[] resize(int size) {
>> +        if (size < 0) {
>> +            throw new IllegalArgumentException("Negative number of
>> elements does not make sense.");
>> +        }
>> +        Node<K,V>[] oldTable = table;
>> +        int oldCapacity = (oldTable == null) ? 0 : oldTable.length;
>> +        int newCapacity = tableSizeFor(size);
>> +
>> +        // need to resize?
>> +        if (newCapacity > oldCapacity) {
>> +            threshold = (int) ((float) newCapacity * loadFactor);
>> +            return createTableAndMoveElements(newCapacity, oldCapacity,
>> oldTable);
>> +        } else {
>> +            return oldTable;
>> +        }
>> +    }
>> +
>> +    /**
>>        * Initializes or doubles table size.  If null, allocates in
>>        * accord with initial capacity target held in field threshold.
>>        * Otherwise, because we are using power-of-two expansion, the
>> @@ -695,6 +719,11 @@
>>                         (int)ft : Integer.MAX_VALUE);
>>           }
>>           threshold = newThr;
>> +
>> +        return createTableAndMoveElements(newCap, oldCap, oldTab);
>> +    }
>> +
>> +    private Node<K,V>[] createTableAndMoveElements(int newCap, int oldCap,
>> Node<K,V>[] oldTab) {
>>           @SuppressWarnings({"rawtypes","unchecked"})
>>           Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
>>           table = newTab;
>>
>>
>> Here's a test that fails with the proposed patch:
>>
>> https://cr.openjdk.java.net/~martin/webrevs/jdk/jsr166-integration/miscellaneous/index.html 
>>
>>
>>      /**
>>       * "Missing" test found while investigating JDK-8210280.
>>       * See discussion on mailing list.
>>       * TODO: randomize
>>       */
>>      public void testBug8210280() {
>>          Map m = impl.emptyMap();
>>          for (int i = 0; i < 4; i++) m.put(7 + i * 16, 0);
>>          Map more = impl.emptyMap();
>>          for (int i = 0; i < 128; i++) more.put(-i, 42);
>>          m.putAll(more);
>>          for (int i = 0; i < 4; i++) assertEquals(0, m.get(7 + i * 16));
>>      }
>>
> 

-- 
Michal Vala
OpenJDK QE
Red Hat Czech