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
