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

[Michal Vala]

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