Repository: incubator-groovy Updated Branches: refs/heads/GROOVY_2_4_X 07c02fa85 -> e6c47f566
GROOVY-7448 fixed bug for permanent rehashing of AbstractConcurrentMap (closes #33) Project: http://git-wip-us.apache.org/repos/asf/incubator-groovy/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-groovy/commit/e6c47f56 Tree: http://git-wip-us.apache.org/repos/asf/incubator-groovy/tree/e6c47f56 Diff: http://git-wip-us.apache.org/repos/asf/incubator-groovy/diff/e6c47f56 Branch: refs/heads/GROOVY_2_4_X Commit: e6c47f5662c5f173dd9022af7b17346ff15dfa3e Parents: 07c02fa Author: tomasbartalos <tomas.bartalos+git...@gmail.com> Authored: Thu Jun 4 15:10:29 2015 +0200 Committer: pascalschumacher <pascalschumac...@gmx.net> Committed: Tue Jun 9 20:27:18 2015 +0200 ---------------------------------------------------------------------- .../util/AbstractConcurrentDoubleKeyMap.java | 11 +- .../groovy/util/AbstractConcurrentMap.java | 13 +- .../groovy/util/AbstractConcurrentMapBase.java | 6 + .../AbstractConcurrentMapSegmentTest.groovy | 170 +++++++++++++++++++ 4 files changed, 185 insertions(+), 15 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-groovy/blob/e6c47f56/src/main/org/codehaus/groovy/util/AbstractConcurrentDoubleKeyMap.java ---------------------------------------------------------------------- diff --git a/src/main/org/codehaus/groovy/util/AbstractConcurrentDoubleKeyMap.java b/src/main/org/codehaus/groovy/util/AbstractConcurrentDoubleKeyMap.java index bda0660..e7d2dfb 100644 --- a/src/main/org/codehaus/groovy/util/AbstractConcurrentDoubleKeyMap.java +++ b/src/main/org/codehaus/groovy/util/AbstractConcurrentDoubleKeyMap.java @@ -111,10 +111,7 @@ public abstract class AbstractConcurrentDoubleKeyMap<K1,K2,V> extends AbstractCo Entry<K1,K2,V> put(K1 key1, K2 key2, int hash) { lock(); try { - int c = count; - if (c++ > threshold) { - rehash(); - } + rehashIfThresholdExceeded(); Object[] tab = table; final int index = hash & (tab.length - 1); @@ -130,7 +127,7 @@ public abstract class AbstractConcurrentDoubleKeyMap<K1,K2,V> extends AbstractCo arr [0] = res; arr [1] = e; tab[index] = arr; - count = c; // write-volatile + count++; // write-volatile return res; } else { @@ -146,14 +143,14 @@ public abstract class AbstractConcurrentDoubleKeyMap<K1,K2,V> extends AbstractCo arr [0] = res; System.arraycopy(arr, 0, newArr, 1, arr.length); tab[index] = arr; - count = c; // write-volatile + count++; // write-volatile return res; } } final Entry<K1,K2,V> res = createEntry(key1, key2, hash); tab[index] = res; - count = c; // write-volatile + count++; // write-volatile return res; } finally { http://git-wip-us.apache.org/repos/asf/incubator-groovy/blob/e6c47f56/src/main/org/codehaus/groovy/util/AbstractConcurrentMap.java ---------------------------------------------------------------------- diff --git a/src/main/org/codehaus/groovy/util/AbstractConcurrentMap.java b/src/main/org/codehaus/groovy/util/AbstractConcurrentMap.java index 399d1c1..b5679a8 100644 --- a/src/main/org/codehaus/groovy/util/AbstractConcurrentMap.java +++ b/src/main/org/codehaus/groovy/util/AbstractConcurrentMap.java @@ -103,10 +103,7 @@ public abstract class AbstractConcurrentMap<K, V> extends AbstractConcurrentMapB public final Entry put(K key, int hash, V value) { lock(); try { - int c = count; - if (c++ > threshold) { - rehash(); - } + rehashIfThresholdExceeded(); Object[] tab = table; int index = hash & (tab.length - 1); @@ -124,7 +121,7 @@ public abstract class AbstractConcurrentMap<K, V> extends AbstractConcurrentMapB arr [0] = ee; arr [1] = e; tab[index] = arr; - count = c; + count++; return ee; } } @@ -143,7 +140,7 @@ public abstract class AbstractConcurrentMap<K, V> extends AbstractConcurrentMapB Entry e = (Entry) arr[i]; if (e == null) { arr [i] = ee; - count = c; + count++; return ee; } } @@ -152,14 +149,14 @@ public abstract class AbstractConcurrentMap<K, V> extends AbstractConcurrentMapB newArr [0] = ee; System.arraycopy(arr, 0, newArr, 1, arr.length); tab [index] = newArr; - count = c; + count++; return ee; } } Entry e = createEntry(key, hash, value); tab[index] = e; - count = c; // write-volatile + count++; // write-volatile return e; } finally { unlock(); http://git-wip-us.apache.org/repos/asf/incubator-groovy/blob/e6c47f56/src/main/org/codehaus/groovy/util/AbstractConcurrentMapBase.java ---------------------------------------------------------------------- diff --git a/src/main/org/codehaus/groovy/util/AbstractConcurrentMapBase.java b/src/main/org/codehaus/groovy/util/AbstractConcurrentMapBase.java index 06c33db..dca2965 100644 --- a/src/main/org/codehaus/groovy/util/AbstractConcurrentMapBase.java +++ b/src/main/org/codehaus/groovy/util/AbstractConcurrentMapBase.java @@ -213,6 +213,12 @@ public abstract class AbstractConcurrentMapBase { } } + void rehashIfThresholdExceeded() { + if(count > threshold) { + rehash(); + } + } + void rehash() { Object[] oldTable = table; int oldCapacity = oldTable.length; http://git-wip-us.apache.org/repos/asf/incubator-groovy/blob/e6c47f56/src/test/org/codehaus/groovy/util/AbstractConcurrentMapSegmentTest.groovy ---------------------------------------------------------------------- diff --git a/src/test/org/codehaus/groovy/util/AbstractConcurrentMapSegmentTest.groovy b/src/test/org/codehaus/groovy/util/AbstractConcurrentMapSegmentTest.groovy new file mode 100644 index 0000000..7eb366f --- /dev/null +++ b/src/test/org/codehaus/groovy/util/AbstractConcurrentMapSegmentTest.groovy @@ -0,0 +1,170 @@ +package org.codehaus.groovy.util + +import org.junit.Before +import org.junit.Test + +class AbstractConcurrentMapSegmentTest { + private static final Integer INITIAL_SEGMENT_SIZE = 100 + private static final Integer SEGMENT_THRESHOLD = 0.75f * INITIAL_SEGMENT_SIZE + TestSegment segment + List<TestEntry> entries = [] + int rehashCount = 0 + + @Before + public void setUp() throws Exception { + segment = new TestSegment(INITIAL_SEGMENT_SIZE) + } + + @Test + public void testSegmentWillNotRehash() { + whenIAddElements(50) + thenRehashHappenedTimes(0) + thenSegmentExpands(false) + } + + @Test + public void testSegmentWillNotRehashEdgeCase() { + whenIAddElements(SEGMENT_THRESHOLD + 1) + thenRehashHappenedTimes(0) + thenSegmentExpands(false) + } + + @Test + public void testSegmentWillRehashAndExpand() { + whenIAddElements(SEGMENT_THRESHOLD + 2) + thenRehashHappenedTimes(1) + thenSegmentExpands(true) + } + + @Test + public void testSegmentWillRehashAndExpandManyTimes() { + int elementCount = (SEGMENT_THRESHOLD + 1 ) * 6 + whenIAddElements(elementCount) + //456 elements fit into segment of size 800, which is 100 * 2 * 2 * 2 + thenSegmentSizeIs(INITIAL_SEGMENT_SIZE * 2 * 2 * 2) + thenRehashHappenedTimes(3) + } + + @Test + public void testSegmentWillRehashWithNoExpansion() { + whenIAddElements(SEGMENT_THRESHOLD) + whenISetElementsAsInvalid(50) + whenIAddElements(50) + thenRehashHappenedTimes(1) + thenSegmentExpands(false) + } + + @Test + public void testSegmentWillRehashAndEventuallyExpand() { + whenIAddElements(SEGMENT_THRESHOLD) + + // 1-st rehash + whenISetElementsAsInvalid(50) + whenIAddElements(50) + thenSegmentExpands(false) + + // 2-nd rehash + whenISetElementsAsInvalid(30) + whenIAddElements(30) + thenSegmentExpands(false) + + // 3-nd rehash + whenISetElementsAsInvalid(20) + whenIAddElements(20) + thenSegmentExpands(false) + + // 4-th rehash with none invalid => expansion: segment * 2 + whenIAddElements(SEGMENT_THRESHOLD) + + thenRehashHappenedTimes(4) + thenSegmentSizeIs(INITIAL_SEGMENT_SIZE * 2) + } + + private void whenIAddElements(int count) { + count.times { + String key = "k:${System.currentTimeMillis()}-${it}" + segment.put(key, key.hashCode(), "v${it}") + } + } + + private void whenISetElementsAsInvalid(int count) { + List<TestEntry> validEntires = entries.findAll { it.isValid() } + count.times { + validEntires.get(it).setValid(false) + } + } + + private void thenRehashHappenedTimes(int expectedRehashCount) { + assert rehashCount == expectedRehashCount + } + + private void thenSegmentSizeIs(int expectedSize) { + assert segment.table.length == expectedSize + } + + private void thenSegmentExpands(boolean truth) { + assert segment.table.length > INITIAL_SEGMENT_SIZE == truth + } + + class TestSegment extends AbstractConcurrentMap.Segment { + + protected TestSegment(int initialCapacity) { + super(initialCapacity) + } + + @Override + protected AbstractConcurrentMap.Entry createEntry(Object key, int hash, Object value) { + TestEntry entry = new TestEntry(key, hash, value) + entries.add(entry) + return entry + } + + @Override + def void rehash() { + rehashCount++ + super.rehash() + } + } +} + +class TestEntry implements AbstractConcurrentMap.Entry { + Object key + Object value + int hash + boolean valid = true; + + public TestEntry(Object key, int hash, Object value) { + this.key = key + this.hash = hash + this.value = value + } + + @Override + boolean isEqual(Object key, int hash) { + return hash == this.hash && key.equals(this.key) + } + + @Override + Object getValue() { + return value + } + + @Override + void setValue(Object value) { + this.value = value + } + + @Override + int getHash() { + return hash + } + + @Override + boolean isValid() { + return valid + } + + public void setValid(boolean valid) { + this.valid = valid + } +} \ No newline at end of file
