You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@geode.apache.org by wi...@apache.org on 2018/08/13 18:41:33 UTC
[geode] branch develop updated: GEODE-5559: Improve runtime of
RegionVersionHolder.canonicalExceptions (#2298)
This is an automated email from the ASF dual-hosted git repository.
wirebaron pushed a commit to branch develop
in repository https://gitbox.apache.org/repos/asf/geode.git
The following commit(s) were added to refs/heads/develop by this push:
new a5840fa GEODE-5559: Improve runtime of RegionVersionHolder.canonicalExceptions (#2298)
a5840fa is described below
commit a5840fa3866d2f5de3f989f9a5feb34c20ab2af9
Author: Brian Rowe <br...@pivotal.io>
AuthorDate: Mon Aug 13 11:41:27 2018 -0700
GEODE-5559: Improve runtime of RegionVersionHolder.canonicalExceptions (#2298)
This modifies the RVVException to iterate over the received version newest to
oldest, which makes generating the canonical exceptions much more
straightforward.
---
.../internal/cache/versions/RVVException.java | 5 +-
.../internal/cache/versions/RVVExceptionB.java | 74 +++++++---------------
.../internal/cache/versions/RVVExceptionT.java | 26 +++-----
.../cache/versions/RegionVersionHolder.java | 23 +++----
.../versions/RegionVersionHolderJUnitTest.java | 34 +++++++++-
5 files changed, 77 insertions(+), 85 deletions(-)
diff --git a/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVException.java b/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVException.java
index 82ab0c1..4fa1ed7 100644
--- a/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVException.java
+++ b/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVException.java
@@ -176,12 +176,11 @@ abstract class RVVException
protected abstract void writeReceived(DataOutput out) throws IOException;
- public abstract ReceivedVersionsIterator receivedVersionsIterator();
+ public abstract ReceivedVersionsReverseIterator receivedVersionsReverseIterator();
public abstract long getHighestReceivedVersion();
- /** it's a shame that BitSet has no iterator */
- public abstract class ReceivedVersionsIterator {
+ public abstract class ReceivedVersionsReverseIterator {
abstract boolean hasNext();
diff --git a/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVExceptionB.java b/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVExceptionB.java
index 7bcc8d1..9825af6 100644
--- a/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVExceptionB.java
+++ b/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVExceptionB.java
@@ -126,32 +126,26 @@ public class RVVExceptionB extends RVVException {
}
protected void writeReceived(DataOutput out) throws IOException {
- int size = 0;
- long[] deltas = null;
- long last = this.previousVersion;
+ final int size = received == null ? 1 : received.length() + 1;
+
+ int deltaIndex = size - 1;
+ long[] deltas = new long[size];
+ long last = this.nextVersion;
// TODO - it would be better just to serialize the longs[] in the BitSet
// as is, rather than go through this delta encoding.
- for (ReceivedVersionsIterator it = receivedVersionsIterator(); it.hasNext();) {
+ for (ReceivedVersionsReverseIterator it = receivedVersionsReverseIterator(); it.hasNext();) {
Long version = it.next();
- long delta = version.longValue() - last;
- if (deltas == null) {
- deltas = new long[this.received.length()];
- }
- deltas[size++] = delta;
+ long delta = last - version.longValue();
+ deltas[--deltaIndex] = delta;
last = version.longValue();
}
- InternalDataSerializer.writeUnsignedVL(size, out);
+ deltas[0] = last - this.previousVersion;
+ InternalDataSerializer.writeUnsignedVL(size - 1, out);
- for (int i = 0; i < size; i++) {
- InternalDataSerializer.writeUnsignedVL(deltas[i], out);
+ for (long value : deltas) {
+ InternalDataSerializer.writeUnsignedVL(value, out);
}
-
- // Write each version in the exception as a delta from the previous version
- // this will likely be smaller than the absolute value, so it will
- // be more likely to fit into a byte or a short.
- long delta = this.nextVersion - last;
- InternalDataSerializer.writeUnsignedVL(delta, out);
}
@Override
@@ -178,17 +172,6 @@ public class RVVExceptionB extends RVVException {
return "e(n=" + this.nextVersion + " p=" + this.previousVersion + "; rb=[])";
}
- // @Override
- // public int hashCode() {
- // final int prime = 31;
- // int result = 1;
- // result = prime * result + (int) (nextVersion ^ (nextVersion >>> 32));
- // result = prime * result
- // + (int) (previousVersion ^ (previousVersion >>> 32));
- // result = prime * result + ((this.received == null) ? 0 : this.received.hashCode());
- // return result;
- // }
-
/**
* For test purposes only. This isn't quite accurate, because I think two RVVs that have
* effectively same exceptions may represent the exceptions differently. This method is testing
@@ -225,10 +208,8 @@ public class RVVExceptionB extends RVVException {
return (this.received == null) || (this.received.isEmpty());
}
- public ReceivedVersionsIterator receivedVersionsIterator() {
- ReceivedVersionsIteratorB result = new ReceivedVersionsIteratorB();
- result.initForForwardIteration();
- return result;
+ public ReceivedVersionsReverseIterator receivedVersionsReverseIterator() {
+ return new ReceivedVersionsReverseIteratorB();
}
@Override
@@ -244,21 +225,19 @@ public class RVVExceptionB extends RVVException {
}
-
-
/** it's a shame that BitSet has no iterator */
- protected class ReceivedVersionsIteratorB extends ReceivedVersionsIterator {
+ protected class ReceivedVersionsReverseIteratorB extends ReceivedVersionsReverseIterator {
int index;
int nextIndex;
- void initForForwardIteration() {
+ ReceivedVersionsReverseIteratorB() {
this.index = -1;
if (received == null) {
- this.nextIndex = -1;
+ nextIndex = -1;
} else {
- this.nextIndex = received.nextSetBit((int) (previousVersion - receivedBaseVersion + 1));
- if (this.nextIndex + receivedBaseVersion >= nextVersion) {
- this.nextIndex = -1;
+ this.nextIndex = received.previousSetBit((int) (nextVersion - receivedBaseVersion - 1));
+ if (nextIndex + receivedBaseVersion <= previousVersion) {
+ nextIndex = -1;
}
}
}
@@ -272,7 +251,10 @@ public class RVVExceptionB extends RVVException {
if (this.index < 0) {
throw new NoSuchElementException("no more elements available");
}
- advance();
+ this.nextIndex = received.previousSetBit(this.index - 1);
+ if (nextIndex + receivedBaseVersion <= previousVersion) {
+ nextIndex = -1;
+ }
return this.index + receivedBaseVersion;
}
@@ -282,13 +264,5 @@ public class RVVExceptionB extends RVVException {
}
received.clear(this.index);
}
-
- private void advance() {
- this.nextIndex = received.nextSetBit(this.index + 1);
- if ((this.nextIndex + receivedBaseVersion) >= nextVersion) {
- this.nextIndex = -1;
- }
- }
-
}
}
diff --git a/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVExceptionT.java b/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVExceptionT.java
index 4a003af..6151456 100644
--- a/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVExceptionT.java
+++ b/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RVVExceptionT.java
@@ -21,7 +21,6 @@ import java.util.NoSuchElementException;
import java.util.TreeSet;
import org.apache.geode.internal.InternalDataSerializer;
-import org.apache.geode.internal.cache.versions.RVVException.ReceivedVersionsIterator;
/**
* This subclass of RVVException is the original class that uses TreeSets to hold received versions.
@@ -175,12 +174,12 @@ public class RVVExceptionT extends RVVException {
if (!super.sameAs(ex)) {
return false;
}
- for (ReceivedVersionsIterator it = receivedVersionsIterator(); it.hasNext();) {
+ for (ReceivedVersionsReverseIterator it = receivedVersionsReverseIterator(); it.hasNext();) {
if (!ex.contains(it.next())) {
return false;
}
}
- for (ReceivedVersionsIterator it = ex.receivedVersionsIterator(); it.hasNext();) {
+ for (ReceivedVersionsReverseIterator it = ex.receivedVersionsReverseIterator(); it.hasNext();) {
if (!contains(it.next())) {
return false;
}
@@ -201,14 +200,10 @@ public class RVVExceptionT extends RVVException {
return (this.received == null || this.received.isEmpty());
}
- public ReceivedVersionsIterator receivedVersionsIterator() {
- ReceivedVersionsIteratorT result = new ReceivedVersionsIteratorT();
- result.initForForwardIteration();
- return result;
+ public ReceivedVersionsReverseIterator receivedVersionsReverseIterator() {
+ return new ReceivedVersionsReverseIteratorT();
}
-
-
public long getHighestReceivedVersion() {
if (received == null || received.isEmpty()) {
return previousVersion;
@@ -231,25 +226,23 @@ public class RVVExceptionT extends RVVException {
public RVVException changeForm() {
// Convert the exception to a bitset exception
RVVExceptionB ex = new RVVExceptionB(previousVersion, nextVersion);
- for (ReceivedVersionsIterator it = this.receivedVersionsIterator(); it.hasNext();) {
+ for (ReceivedVersionsReverseIterator it = this.receivedVersionsReverseIterator(); it
+ .hasNext();) {
long next = it.next();
ex.add(next);
}
return ex;
}
-
-
- /** it's a shame that BitSet has no iterator */
- protected class ReceivedVersionsIteratorT extends ReceivedVersionsIterator {
+ protected class ReceivedVersionsReverseIteratorT extends ReceivedVersionsReverseIterator {
boolean noIterator;
Iterator<Long> treeSetIterator;
- void initForForwardIteration() {
+ ReceivedVersionsReverseIteratorT() {
if (received == null) {
this.noIterator = true;
} else {
- this.treeSetIterator = received.iterator();
+ this.treeSetIterator = received.descendingIterator();
}
}
@@ -269,6 +262,5 @@ public class RVVExceptionT extends RVVException {
this.treeSetIterator.remove();
}
}
-
}
}
diff --git a/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RegionVersionHolder.java b/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RegionVersionHolder.java
index 4a39486..1a71a32 100755
--- a/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RegionVersionHolder.java
+++ b/geode-core/src/main/java/org/apache/geode/internal/cache/versions/RegionVersionHolder.java
@@ -28,7 +28,6 @@ import org.apache.logging.log4j.Logger;
import org.apache.geode.DataSerializable;
import org.apache.geode.internal.InternalDataSerializer;
-import org.apache.geode.internal.cache.versions.RVVException.ReceivedVersionsIterator;
import org.apache.geode.internal.logging.LogService;
import org.apache.geode.internal.logging.log4j.LogMarker;
@@ -751,7 +750,7 @@ public class RegionVersionHolder<T> implements Cloneable, DataSerializable {
*
* @return The canonicalized set of exceptions.
*/
- protected List<RVVException> canonicalExceptions(List<RVVException> exceptions) {
+ protected static List<RVVException> canonicalExceptions(List<RVVException> exceptions) {
LinkedList<RVVException> canon = new LinkedList<RVVException>();
if (exceptions != null) {
// Iterate through the set of exceptions
@@ -759,26 +758,26 @@ public class RegionVersionHolder<T> implements Cloneable, DataSerializable {
if (exception.isEmpty()) {
canon.add(exception);
} else {
- long previous = exception.previousVersion;
+ long previous = exception.nextVersion;
// Iterate through the set of received versions for this exception
- int insertAt = canon.size();
- for (ReceivedVersionsIterator it = exception.receivedVersionsIterator(); it.hasNext();) {
+ for (RVVException.ReceivedVersionsReverseIterator it =
+ exception.receivedVersionsReverseIterator(); it.hasNext();) {
Long received = it.next();
// If we find a gap between the previous received version and the
// next received version, add an exception.
- if (received != previous + 1) {
- canon.add(insertAt, RVVException.createException(previous, received));
+ if (received != previous - 1) {
+ canon.add(RVVException.createException(received, previous));
}
// move the previous reference
previous = received;
}
- // if there is a gap between the last received version and the next
+ // if there is a gap between the first received version and the previous
// version, add an exception
// this also handles the case where the RVV has no received versions,
- // because previous==exception.previousVersion in that case.
- if (exception.nextVersion != previous + 1) {
- canon.add(insertAt, RVVException.createException(previous, exception.nextVersion));
+ // because previous==exception.nextVersion in that case.
+ if (exception.previousVersion != previous - 1) {
+ canon.add(RVVException.createException(exception.previousVersion, previous));
}
}
}
@@ -786,6 +785,4 @@ public class RegionVersionHolder<T> implements Cloneable, DataSerializable {
return canon;
}
-
-
}
diff --git a/geode-core/src/test/java/org/apache/geode/internal/cache/versions/RegionVersionHolderJUnitTest.java b/geode-core/src/test/java/org/apache/geode/internal/cache/versions/RegionVersionHolderJUnitTest.java
index 38f1397..d40398b 100644
--- a/geode-core/src/test/java/org/apache/geode/internal/cache/versions/RegionVersionHolderJUnitTest.java
+++ b/geode-core/src/test/java/org/apache/geode/internal/cache/versions/RegionVersionHolderJUnitTest.java
@@ -19,7 +19,9 @@ import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import java.net.InetAddress;
+import java.util.ArrayList;
import java.util.BitSet;
+import java.util.List;
import org.junit.After;
import org.junit.Before;
@@ -27,7 +29,6 @@ import org.junit.Test;
import org.apache.geode.distributed.internal.membership.InternalDistributedMember;
import org.apache.geode.internal.Assert;
-import org.apache.geode.internal.cache.versions.RVVException.ReceivedVersionsIterator;
public class RegionVersionHolderJUnitTest {
@@ -1481,6 +1482,34 @@ public class RegionVersionHolderJUnitTest {
}
+ // Using huge values here to ensure we're efficiently creating canonicalExceptions
+ private static final int NUM_TEST_EXCEPTIONS = 10;
+ private static final int TEST_EXCEPTION_SIZE = 200000;
+
+ @Test
+ public void testCanonicalExceptions() {
+ List<RVVException> exceptionList = new ArrayList<>();
+ for (int i = NUM_TEST_EXCEPTIONS; i > 0; --i) {
+ long start = i * TEST_EXCEPTION_SIZE;
+ long end = start + TEST_EXCEPTION_SIZE;
+ RVVException testException = RVVException.createException(start, end);
+ for (long j = start + 2; j < end; j += 2) {
+ testException.add(j);
+ }
+ exceptionList.add(testException);
+ }
+
+ List<RVVException> canonicalExceptions = RegionVersionHolder.canonicalExceptions(exceptionList);
+
+ long expectedStart = NUM_TEST_EXCEPTIONS * TEST_EXCEPTION_SIZE + TEST_EXCEPTION_SIZE - 2;
+ for (RVVException exception : canonicalExceptions) {
+ assertEquals(expectedStart, exception.previousVersion);
+ assertEquals(expectedStart + 2, exception.nextVersion);
+ assertTrue(exception.isEmpty());
+ expectedStart -= 2;
+ }
+ }
+
/**
* Test merging two version holders
*/
@@ -1887,7 +1916,8 @@ public class RegionVersionHolderJUnitTest {
"bad next and previous next=" + ex.nextVersion + ", previous=" + ex.previousVersion);
}
- for (ReceivedVersionsIterator it = ex.receivedVersionsIterator(); it.hasNext();) {
+ for (RVVException.ReceivedVersionsReverseIterator it =
+ ex.receivedVersionsReverseIterator(); it.hasNext();) {
Long received = it.next();
if (received >= ex.nextVersion) {
Assert.assertTrue(false, "received greater than next next=" + ex.nextVersion