groovy-notifications mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From pascalschumac...@apache.org
Subject incubator-groovy git commit: GROOVY-7448 fixed bug for permanent rehashing of AbstractConcurrentMap (closes #33)
Date Tue, 09 Jun 2015 18:26:40 GMT
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 <tomas.bartalos+github@gmail.com>
Authored: Thu Jun 4 15:10:29 2015 +0200
Committer: pascalschumacher <pascalschumacher@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


Mime
View raw message