You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@groovy.apache.org by pa...@apache.org on 2015/06/09 20:26:40 UTC
incubator-groovy git commit: GROOVY-7448 fixed bug for permanent
rehashing of AbstractConcurrentMap (closes #33)
Repository: incubator-groovy
Updated Branches:
refs/heads/master d09fd5a76 -> f106964db
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/f106964d
Tree: http://git-wip-us.apache.org/repos/asf/incubator-groovy/tree/f106964d
Diff: http://git-wip-us.apache.org/repos/asf/incubator-groovy/diff/f106964d
Branch: refs/heads/master
Commit: f106964dba87fb9af0ca131b5f27c295b705fd6a
Parents: d09fd5a
Author: tomasbartalos <to...@gmail.com>
Authored: Thu Jun 4 15:10:29 2015 +0200
Committer: pascalschumacher <pa...@gmx.net>
Committed: Tue Jun 9 20:25:40 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/f106964d/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 aa295e9..6137efc 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/f106964d/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 ba57ae0..d60396b 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/f106964d/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 ee30396..0979491 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/f106964d/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