Repository: activemq Updated Branches: refs/heads/activemq-5.15.x 77784061c -> d2572ceae
AMQ-7055 - Optimization on SequenceSet to prevent iterating through the whole set when a value bigger than the last value is added Signed-off-by: gtully <gary.tu...@gmail.com> (cherry picked from commit 8f88dcda09760df3aba3306f49a3311fb22a654f) Project: http://git-wip-us.apache.org/repos/asf/activemq/repo Commit: http://git-wip-us.apache.org/repos/asf/activemq/commit/d2572cea Tree: http://git-wip-us.apache.org/repos/asf/activemq/tree/d2572cea Diff: http://git-wip-us.apache.org/repos/asf/activemq/diff/d2572cea Branch: refs/heads/activemq-5.15.x Commit: d2572ceaee84a14d383c05c73d4c7ce2b4e5487b Parents: 7778406 Author: Alan Protasio <alanp...@gmail.com> Authored: Wed Sep 19 12:20:59 2018 -0700 Committer: Christopher L. Shannon (cshannon) <christopher.l.shan...@gmail.com> Committed: Thu Sep 20 06:28:53 2018 -0400 ---------------------------------------------------------------------- .../store/kahadb/disk/util/Sequence.java | 4 +++ .../store/kahadb/disk/util/SequenceSet.java | 7 +++++ .../store/kahadb/disk/util/SequenceSetTest.java | 31 ++++++++++++++++++++ 3 files changed, 42 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/activemq/blob/d2572cea/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/Sequence.java ---------------------------------------------------------------------- diff --git a/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/Sequence.java b/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/Sequence.java index f52931b..25e594b 100644 --- a/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/Sequence.java +++ b/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/Sequence.java @@ -38,6 +38,10 @@ public class Sequence extends LinkedNode<Sequence> { return last + 1 == value; } + public boolean isBiggerButNotAdjacentToLast(long value) { + return last + 1 < value; + } + public boolean isAdjacentToFirst(long value) { return first - 1 == value; } http://git-wip-us.apache.org/repos/asf/activemq/blob/d2572cea/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java ---------------------------------------------------------------------- diff --git a/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java b/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java index 2946a22..fac831b 100644 --- a/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java +++ b/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java @@ -114,6 +114,13 @@ public class SequenceSet extends LinkedNodeList<Sequence> implements Iterable<Lo return true; } + // check if the value is greater than the bigger sequence value and if it's not adjacent to it + // in this case, we are sure that the value should be add to the tail of the sequence. + if (sequence.isBiggerButNotAdjacentToLast(value)) { + addLast(new Sequence(value)); + return true; + } + sequence = getHead(); while (sequence != null) { http://git-wip-us.apache.org/repos/asf/activemq/blob/d2572cea/activemq-kahadb-store/src/test/java/org/apache/activemq/store/kahadb/disk/util/SequenceSetTest.java ---------------------------------------------------------------------- diff --git a/activemq-kahadb-store/src/test/java/org/apache/activemq/store/kahadb/disk/util/SequenceSetTest.java b/activemq-kahadb-store/src/test/java/org/apache/activemq/store/kahadb/disk/util/SequenceSetTest.java index 272077a..a25b4e7 100644 --- a/activemq-kahadb-store/src/test/java/org/apache/activemq/store/kahadb/disk/util/SequenceSetTest.java +++ b/activemq-kahadb-store/src/test/java/org/apache/activemq/store/kahadb/disk/util/SequenceSetTest.java @@ -86,6 +86,37 @@ public class SequenceSetTest { } @Test + public void testAddValuesToTail() { + SequenceSet set = new SequenceSet(); + set.add(new Sequence(0, 10)); + set.add(new Sequence(21, 42)); + set.add(new Sequence(142, 512)); + + set.add(513); + + for (int i = 600; i < 650; i++) { + set.add(i); + } + + for (int i = 0; i < 10; i++) { + set.add(i * 100); + } + + assertTrue(set.contains(0)); + assertTrue(set.contains(25)); + + assertTrue(set.contains(513)); + assertTrue(!set.contains(514)); + assertFalse(set.contains(599)); + assertTrue(set.contains(625)); + assertFalse(set.contains(651)); + + for (int i = 0; i < 10; i++) { + assertTrue(set.contains(i * 100)); + } + } + + @Test public void testRemove() { SequenceSet set = new SequenceSet(); set.add(new Sequence(0, 100));