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

[Martin Buchholz]

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));
    }