Revision: 9858
Author: [email protected]
Date: Wed Mar 16 09:22:21 2011
Log: Fix the worst concurrent modification problems in compiler
memory-light set/map.
Due to a bug in com.google.gwt.dev.util.collect.HashMap.put(), we were
eagerly growing the underlying table even when the key was already mapped.
This causes an iterators to be invalidated on a non-structural change. Of
course, we weren't actually tracking structural changes, which would cause
the iterator to quietly continue, returning a 'null' keyed entry when it
should not have, and possibly duplicating / skipping other entries.
1) I fixed the bug in HashMap.put() and HashSet.add() to defer growth until
we're sure the key doesn't exist already.
2) Added basic concurrent modification tracking to the associated
iterators, in a way that doesn't add additional memory to the collections
themselves.
3) Other various and sundry cleanups.
http://gwt-code-reviews.appspot.com/1384804
Review by: [email protected]
http://code.google.com/p/google-web-toolkit/source/detail?r=9858
Modified:
/trunk/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java
/trunk/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java
/trunk/dev/core/src/com/google/gwt/dev/util/collect/IdentityHashSet.java
/trunk/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java
/trunk/dev/core/src/com/google/gwt/dev/util/collect/Sets.java
=======================================
--- /trunk/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java Wed
Oct 28 09:10:53 2009
+++ /trunk/dev/core/src/com/google/gwt/dev/util/collect/HashMap.java Wed
Mar 16 09:22:21 2011
@@ -22,6 +22,7 @@
import java.util.AbstractCollection;
import java.util.AbstractSet;
import java.util.Collection;
+import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
@@ -43,38 +44,43 @@
*/
private static final int INITIAL_TABLE_SIZE = 4;
- private class EntryIterator implements Iterator<Entry<K, V>> {
+ private abstract class BaseIterator<E> implements Iterator<E> {
+ private Object[] coModCheckKeys = keys;
private int index = 0;
private int last = -1;
- {
- advanceToItem();
- }
-
public boolean hasNext() {
+ if (coModCheckKeys != keys) {
+ throw new ConcurrentModificationException();
+ }
+ advanceToItem();
return index < keys.length;
}
- public Entry<K, V> next() {
+ public E next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
last = index;
- Entry<K, V> toReturn = new HashEntry(index++);
- advanceToItem();
- return toReturn;
+ return iteratorItem(index++);
}
public void remove() {
if (last < 0) {
throw new IllegalStateException();
}
+ if (coModCheckKeys != keys) {
+ throw new ConcurrentModificationException();
+ }
internalRemove(last);
if (keys[last] != null) {
+ // Hole was plugged.
index = last;
}
last = -1;
}
+
+ protected abstract E iteratorItem(int index);
private void advanceToItem() {
for (; index < keys.length; ++index) {
@@ -84,6 +90,13 @@
}
}
}
+
+ private class EntryIterator extends BaseIterator<Entry<K, V>> {
+ @Override
+ protected Entry<K, V> iteratorItem(int index) {
+ return new HashEntry(index);
+ }
+ }
private class EntrySet extends AbstractSet<Entry<K, V>> {
@Override
@@ -95,7 +108,7 @@
@Override
public boolean addAll(Collection<? extends Entry<K, V>> c) {
- HashMap.this.ensureSizeFor(size() + c.size());
+ HashMap.this.resizeForJoin(c.size());
return super.addAll(c);
}
@@ -201,46 +214,11 @@
}
}
- private class KeyIterator implements Iterator<K> {
- private int index = 0;
- private int last = -1;
-
- {
- advanceToItem();
- }
-
- public boolean hasNext() {
- return index < keys.length;
- }
-
+ private class KeyIterator extends BaseIterator<K> {
@SuppressWarnings("unchecked")
- public K next() {
- if (!hasNext()) {
- throw new NoSuchElementException();
- }
- last = index;
- Object toReturn = unmaskNullKey(keys[index++]);
- advanceToItem();
- return (K) toReturn;
- }
-
- public void remove() {
- if (last < 0) {
- throw new IllegalStateException();
- }
- internalRemove(last);
- if (keys[last] != null) {
- index = last;
- }
- last = -1;
- }
-
- private void advanceToItem() {
- for (; index < keys.length; ++index) {
- if (keys[index] != null) {
- return;
- }
- }
+ @Override
+ protected K iteratorItem(int index) {
+ return (K) unmaskNullKey(keys[index]);
}
}
@@ -297,46 +275,11 @@
}
}
- private class ValueIterator implements Iterator<V> {
- private int index = 0;
- private int last = -1;
-
- {
- advanceToItem();
- }
-
- public boolean hasNext() {
- return index < keys.length;
- }
-
+ private class ValueIterator extends BaseIterator<V> {
@SuppressWarnings("unchecked")
- public V next() {
- if (!hasNext()) {
- throw new NoSuchElementException();
- }
- last = index;
- Object toReturn = values[index++];
- advanceToItem();
- return (V) toReturn;
- }
-
- public void remove() {
- if (last < 0) {
- throw new IllegalStateException();
- }
- internalRemove(last);
- if (keys[last] != null) {
- index = last;
- }
- last = -1;
- }
-
- private void advanceToItem() {
- for (; index < keys.length; ++index) {
- if (keys[index] != null) {
- return;
- }
- }
+ @Override
+ protected V iteratorItem(int index) {
+ return (V) values[index];
}
}
@@ -446,7 +389,7 @@
}
initTable(newCapacity);
- internalPutAll(m);
+ putAll(m);
}
public void clear() {
@@ -517,14 +460,18 @@
@SuppressWarnings("unchecked")
public V put(K key, V value) {
- ensureSizeFor(size + 1);
int index = findKeyOrEmpty(key);
if (keys[index] == null) {
- ++size;
+ // Not in the map, may need to grow.
+ if (ensureSizeFor(++size)) {
+ // If we had to grow the table, must recompute the index.
+ index = findKeyOrEmpty(key);
+ }
keys[index] = maskNullKey(key);
values[index] = value;
return null;
} else {
+ // In the map, set a new value;
Object previousValue = values[index];
values[index] = value;
return (V) previousValue;
@@ -532,8 +479,10 @@
}
public void putAll(Map<? extends K, ? extends V> m) {
- ensureSizeFor(size + m.size());
- internalPutAll(m);
+ resizeForJoin(m.size());
+ for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
+ put(entry.getKey(), entry.getValue());
+ }
}
@SuppressWarnings("unchecked")
@@ -644,9 +593,9 @@
* Ensures the map is large enough to contain the specified number of
entries.
* Default access to avoid synthetic accessors from inner classes.
*/
- void ensureSizeFor(int expectedSize) {
+ boolean ensureSizeFor(int expectedSize) {
if (keys.length * 3 >= expectedSize * 4) {
- return;
+ return false;
}
int newCapacity = keys.length << 1;
@@ -670,6 +619,7 @@
values[newIndex] = oldValues[i];
}
}
+ return true;
}
/**
@@ -726,6 +676,27 @@
--size;
plugHole(index);
}
+
+ /**
+ * Resizes this map to accommodate the minimum size required to join
this map
+ * with another map. This is an optimization to prevent multiple resizes
+ * during the join operation. Naively, it would seem like we should
resize to
+ * hold {@code (size + otherSize)}. However, the incoming map might have
+ * duplicates with this map; it might even be all duplicates. The correct
+ * behavior when the incoming map is all duplicates is NOT to resize, and
+ * therefore not to invalidate any iterators.
+ * <p>
+ * In practice, this strategy results in a worst-case of two resizes. In
the
+ * worst case, where {@code size} and {@code otherSize} are roughly
equal and
+ * the sets are completely disjoint, we might do 1 initial rehash and
then 1
+ * additional rehash down the road. But this is an edge case that
requires
+ * getting unlucky on both boundaries. Most of the time, we do either 1
+ * initial rehash or 1 down the road, because doubling the capacity
generally
+ * allows this map to absorb an equally-sized disjoint map.
+ */
+ boolean resizeForJoin(int sizeOther) {
+ return ensureSizeFor(Math.max(size, sizeOther));
+ }
private int getKeyIndex(Object k) {
int h = keyHashCode(k);
@@ -742,21 +713,6 @@
keys = new Object[capacity];
values = new Object[capacity];
}
-
- private void internalPutAll(Map<? extends K, ? extends V> m) {
- for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
- K key = entry.getKey();
- V value = entry.getValue();
- int index = findKeyOrEmpty(key);
- if (keys[index] == null) {
- ++size;
- keys[index] = maskNullKey(key);
- values[index] = value;
- } else {
- values[index] = value;
- }
- }
- }
/**
* Tricky, we left a hole in the map, which we have to fill. The only
way to
=======================================
--- /trunk/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java Wed
Oct 28 09:10:53 2009
+++ /trunk/dev/core/src/com/google/gwt/dev/util/collect/HashSet.java Wed
Mar 16 09:22:21 2011
@@ -22,6 +22,7 @@
import java.lang.reflect.Array;
import java.util.AbstractSet;
import java.util.Collection;
+import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
@@ -33,14 +34,15 @@
public class HashSet<E> extends AbstractSet<E> implements Serializable {
private class SetIterator implements Iterator<E> {
+ private Object[] coModCheckTable = table;
private int index = 0;
private int last = -1;
- public SetIterator() {
- advanceToItem();
- }
-
public boolean hasNext() {
+ if (coModCheckTable != table) {
+ throw new ConcurrentModificationException();
+ }
+ advanceToItem();
return index < table.length;
}
@@ -50,17 +52,19 @@
throw new NoSuchElementException();
}
last = index;
- E toReturn = (E) unmaskNull(table[index++]);
- advanceToItem();
- return toReturn;
+ return (E) unmaskNull(table[index++]);
}
public void remove() {
if (last < 0) {
throw new IllegalStateException();
}
+ if (coModCheckTable != table) {
+ throw new ConcurrentModificationException();
+ }
internalRemove(last);
if (table[last] != null) {
+ // Hole was plugged.
index = last;
}
last = -1;
@@ -123,13 +127,33 @@
table = new Object[newCapacity];
super.addAll(c);
}
+
+ /**
+ * Works just like {@link #HashSet(Collection)}, but for arrays. Used to
avoid
+ * having to synthesize a collection in {@link Sets}.
+ */
+ HashSet(E[] c) {
+ int newCapacity = INITIAL_TABLE_SIZE;
+ int expectedSize = c.length;
+ while (newCapacity * 3 < expectedSize * 4) {
+ newCapacity <<= 1;
+ }
+
+ table = new Object[newCapacity];
+ for (E e : c) {
+ add(e);
+ }
+ }
@Override
public boolean add(E e) {
- ensureSizeFor(size + 1);
int index = findOrEmpty(e);
if (table[index] == null) {
- ++size;
+ // Not in the map, may need to grow.
+ if (ensureSizeFor(++size)) {
+ // If we had to grow the table, must recompute the index.
+ index = findOrEmpty(e);
+ }
table[index] = maskNull(e);
return true;
}
@@ -138,7 +162,7 @@
@Override
public boolean addAll(Collection<? extends E> c) {
- ensureSizeFor(size + c.size());
+ resizeForJoin(c.size());
return super.addAll(c);
}
@@ -237,21 +261,6 @@
protected int itemHashCode(Object o) {
return (o == null) ? 0 : o.hashCode();
}
-
- /**
- * Works just like {@link #addAll(Collection)}, but for arrays. Used to
avoid
- * having to synthesize a collection in {@link Sets}.
- */
- void addAll(E[] elements) {
- ensureSizeFor(size + elements.length);
- for (E e : elements) {
- int index = findOrEmpty(e);
- if (table[index] == null) {
- ++size;
- table[index] = maskNull(e);
- }
- }
- }
/**
* Removes the item at the specified index, and performs internal
management
@@ -267,9 +276,9 @@
/**
* Ensures the set is large enough to contain the specified number of
entries.
*/
- private void ensureSizeFor(int expectedSize) {
+ private boolean ensureSizeFor(int expectedSize) {
if (table.length * 3 >= expectedSize * 4) {
- return;
+ return false;
}
int newCapacity = table.length << 1;
@@ -290,6 +299,7 @@
table[newIndex] = o;
}
}
+ return true;
}
/**
@@ -390,6 +400,27 @@
in.defaultReadObject();
doReadObject(in);
}
+
+ /**
+ * Resizes this set to accommodate the minimum size required to join
this set
+ * with another set. This is an optimization to prevent multiple resizes
+ * during the join operation. Naively, it would seem like we should
resize to
+ * hold {@code (size + otherSize)}. However, the incoming set might have
+ * duplicates with this set; it might even be all duplicates. The correct
+ * behavior when the incoming set is all duplicates is NOT to resize, and
+ * therefore not to invalidate any iterators.
+ * <p>
+ * In practice, this strategy results in a worst-case of two resizes. In
the
+ * worst case, where {@code size} and {@code otherSize} are roughly
equal and
+ * the sets are completely disjoint, we might do 1 initial rehash and
then 1
+ * additional rehash down the road. But this is an edge case that
requires
+ * getting unlucky on both boundaries. Most of the time, we do either 1
+ * initial rehash or 1 down the road, because doubling the capacity
generally
+ * allows this set to absorb an equally-sized disjoint set.
+ */
+ private void resizeForJoin(int sizeOther) {
+ ensureSizeFor(Math.max(size, sizeOther));
+ }
private void writeObject(ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
=======================================
---
/trunk/dev/core/src/com/google/gwt/dev/util/collect/IdentityHashSet.java
Wed Oct 28 09:10:53 2009
+++
/trunk/dev/core/src/com/google/gwt/dev/util/collect/IdentityHashSet.java
Wed Mar 16 09:22:21 2011
@@ -32,6 +32,14 @@
public IdentityHashSet(Collection<? extends E> c) {
super(c);
}
+
+ /**
+ * Works just like {@link #HashSet(Collection)}, but for arrays. Used to
avoid
+ * having to synthesize a collection in {@link IdentitySets}.
+ */
+ IdentityHashSet(E[] c) {
+ super(c);
+ }
@Override
protected boolean itemEquals(Object a, Object b) {
=======================================
--- /trunk/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java
Wed Aug 11 09:22:23 2010
+++ /trunk/dev/core/src/com/google/gwt/dev/util/collect/IdentitySets.java
Wed Mar 16 09:22:21 2011
@@ -146,9 +146,7 @@
case 1:
return create(items[0]);
default:
- IdentityHashSet<T> result = new IdentityHashSet<T>();
- result.addAll(items);
- return result;
+ return new IdentityHashSet<T>(items);
}
}
=======================================
--- /trunk/dev/core/src/com/google/gwt/dev/util/collect/Sets.java Wed Oct
28 09:10:53 2009
+++ /trunk/dev/core/src/com/google/gwt/dev/util/collect/Sets.java Wed Mar
16 09:22:21 2011
@@ -93,9 +93,7 @@
case 1:
return create(items[0]);
default:
- HashSet<T> result = new HashSet<T>();
- result.addAll(items);
- return result;
+ return new HashSet<T>(items);
}
}
--
http://groups.google.com/group/Google-Web-Toolkit-Contributors
