JDK-8210280 - Unnecessary reallocation when invoking HashMap.putAll()
Michal Vala
mvala at redhat.com
Fri Dec 14 17:00:09 UTC 2018
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
More information about the core-libs-dev
mailing list