Return-Path: X-Original-To: apmail-groovy-notifications-archive@minotaur.apache.org Delivered-To: apmail-groovy-notifications-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id ECB6618A0B for ; Tue, 9 Jun 2015 18:26:44 +0000 (UTC) Received: (qmail 74213 invoked by uid 500); 9 Jun 2015 18:26:44 -0000 Delivered-To: apmail-groovy-notifications-archive@groovy.apache.org Received: (qmail 74187 invoked by uid 500); 9 Jun 2015 18:26:44 -0000 Mailing-List: contact notifications-help@groovy.incubator.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@groovy.incubator.apache.org Delivered-To: mailing list notifications@groovy.incubator.apache.org Received: (qmail 74178 invoked by uid 99); 9 Jun 2015 18:26:44 -0000 Received: from Unknown (HELO spamd4-us-west.apache.org) (209.188.14.142) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 09 Jun 2015 18:26:44 +0000 Received: from localhost (localhost [127.0.0.1]) by spamd4-us-west.apache.org (ASF Mail Server at spamd4-us-west.apache.org) with ESMTP id 6B50DC0518 for ; Tue, 9 Jun 2015 18:26:44 +0000 (UTC) X-Virus-Scanned: Debian amavisd-new at spamd4-us-west.apache.org X-Spam-Flag: NO X-Spam-Score: 1.77 X-Spam-Level: * X-Spam-Status: No, score=1.77 tagged_above=-999 required=6.31 tests=[KAM_ASCII_DIVIDERS=0.8, KAM_LAZY_DOMAIN_SECURITY=1, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, T_RP_MATCHES_RCVD=-0.01] autolearn=disabled Received: from mx1-eu-west.apache.org ([10.40.0.8]) by localhost (spamd4-us-west.apache.org [10.40.0.11]) (amavisd-new, port 10024) with ESMTP id GAKxwV9UqOQ4 for ; Tue, 9 Jun 2015 18:26:42 +0000 (UTC) Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by mx1-eu-west.apache.org (ASF Mail Server at mx1-eu-west.apache.org) with SMTP id 6ABB121544 for ; Tue, 9 Jun 2015 18:26:41 +0000 (UTC) Received: (qmail 74146 invoked by uid 99); 9 Jun 2015 18:26:40 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 09 Jun 2015 18:26:40 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id 72F8BDFF84; Tue, 9 Jun 2015 18:26:40 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: pascalschumacher@apache.org To: notifications@groovy.incubator.apache.org Message-Id: X-Mailer: ASF-Git Admin Mailer Subject: incubator-groovy git commit: GROOVY-7448 fixed bug for permanent rehashing of AbstractConcurrentMap (closes #33) Date: Tue, 9 Jun 2015 18:26:40 +0000 (UTC) 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 Authored: Thu Jun 4 15:10:29 2015 +0200 Committer: pascalschumacher 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 extends AbstractCo Entry 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 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 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 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 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 extends AbstractConcurrentMapB arr [0] = ee; arr [1] = e; tab[index] = arr; - count = c; + count++; return ee; } } @@ -143,7 +140,7 @@ public abstract class AbstractConcurrentMap 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 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 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 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