cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject [2/3] git commit: clean up Path and Cursor now that we know stack allocation doesn't work as expected patch by Benedict Elliott Smith; reviewed by jbellis for CASSANDRA-6692
Date Wed, 12 Mar 2014 23:40:26 GMT
clean up Path and Cursor now that we know stack allocation doesn't work as expected
patch by Benedict Elliott Smith; reviewed by jbellis for CASSANDRA-6692


Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/948964b5
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/948964b5
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/948964b5

Branch: refs/heads/trunk
Commit: 948964b52fc58d6aa08f369be9e2d3a058cfea95
Parents: 0cb1e3d
Author: Jonathan Ellis <jbellis@apache.org>
Authored: Wed Mar 12 18:40:06 2014 -0500
Committer: Jonathan Ellis <jbellis@apache.org>
Committed: Wed Mar 12 18:40:06 2014 -0500

----------------------------------------------------------------------
 .../org/apache/cassandra/utils/btree/BTree.java | 23 ++++++++------
 .../apache/cassandra/utils/btree/Cursor.java    | 23 ++------------
 .../org/apache/cassandra/utils/btree/Path.java  | 32 +++++++++++---------
 .../apache/cassandra/utils/LongBTreeTest.java   |  2 +-
 4 files changed, 34 insertions(+), 46 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/948964b5/src/java/org/apache/cassandra/utils/btree/BTree.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/BTree.java b/src/java/org/apache/cassandra/utils/btree/BTree.java
index ad5065e..5ca5006 100644
--- a/src/java/org/apache/cassandra/utils/btree/BTree.java
+++ b/src/java/org/apache/cassandra/utils/btree/BTree.java
@@ -60,12 +60,6 @@ public class BTree
     }
     // NB we encode Path indexes as Bytes, so this needs to be less than Byte.MAX_VALUE /
2
     static final int FAN_FACTOR = 1 << FAN_SHIFT;
-    static final int QUICK_MERGE_LIMIT = Math.min(FAN_FACTOR, 16) * 2;
-
-    // Maximum depth of any B-Tree. In reality this is just an arbitrary limit, and is currently
imposed on iterators only,
-    // but a maximum depth sufficient to store at worst Integer.MAX_VALUE items seems reasonable
-    // 2^n = (2^k).(2^(n/k)) => 2^31 <= 2^(FAN_SHIFT-1) . 2^ceil(31 / (FAN_SHIFT -
1))
-    static final int MAX_DEPTH = (int) Math.ceil(31d / (FAN_SHIFT - 1));
 
     // An empty BTree Leaf - which is the same as an empty BTree
     static final Object[] EMPTY_LEAF = new Object[0];
@@ -202,7 +196,7 @@ public class BTree
      */
     public static <V> Cursor<V> slice(Object[] btree, boolean forwards)
     {
-        Cursor<V> r = Cursor.newCursor();
+        Cursor<V> r = new Cursor<>();
         r.reset(btree, forwards);
         return r;
     }
@@ -220,7 +214,7 @@ public class BTree
      */
     public static <V> Cursor<V> slice(Object[] btree, Comparator<V> comparator,
V start, V end, boolean forwards)
     {
-        Cursor<V> r = Cursor.newCursor();
+        Cursor<V> r = new Cursor<>();
         r.reset(btree, comparator, start, end, forwards);
         return r;
     }
@@ -238,7 +232,7 @@ public class BTree
      */
     public static <V> Cursor<V> slice(Object[] btree, Comparator<V> comparator,
V start, boolean startInclusive, V end, boolean endInclusive, boolean forwards)
     {
-        Cursor<V> r = Cursor.newCursor();
+        Cursor<V> r = new Cursor<>();
         r.reset(btree, comparator, start, startInclusive, end, endInclusive, forwards);
         return r;
     }
@@ -342,6 +336,17 @@ public class BTree
         return tree.length == 0;
     }
 
+    public static int depth(Object[] tree)
+    {
+        int depth = 1;
+        while (!isLeaf(tree))
+        {
+            depth++;
+            tree = (Object[]) tree[getKeyEnd(tree)];
+        }
+        return depth;
+    }
+
     // Special class for making certain operations easier, so we can define a +/- Inf
     private static interface Special extends Comparable<Object> { }
     static final Special POSITIVE_INFINITY = new Special()

http://git-wip-us.apache.org/repos/asf/cassandra/blob/948964b5/src/java/org/apache/cassandra/utils/btree/Cursor.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/Cursor.java b/src/java/org/apache/cassandra/utils/btree/Cursor.java
index fba5eec..bc88442 100644
--- a/src/java/org/apache/cassandra/utils/btree/Cursor.java
+++ b/src/java/org/apache/cassandra/utils/btree/Cursor.java
@@ -21,7 +21,6 @@ package org.apache.cassandra.utils.btree;
 import java.util.Comparator;
 import java.util.Iterator;
 
-import static org.apache.cassandra.utils.btree.BTree.MAX_DEPTH;
 import static org.apache.cassandra.utils.btree.BTree.NEGATIVE_INFINITY;
 import static org.apache.cassandra.utils.btree.BTree.POSITIVE_INFINITY;
 import static org.apache.cassandra.utils.btree.BTree.getLeafKeyEnd;
@@ -44,20 +43,6 @@ public final class Cursor<V> extends Path implements Iterator<V>
      * the first one.
      */
 
-    /**
-     * Returns a cursor that can be reused to iterate over trees
-     *
-     * @param <V>
-     * @return
-     */
-    static <V> Cursor<V> newCursor()
-    {
-        // try to encourage stack allocation - may be misguided. but no harm
-        Object[][] stack = new Object[MAX_DEPTH][];
-        byte[] index = new byte[MAX_DEPTH];
-        return new Cursor(stack, index);
-    }
-
     // the last node covered by the requested range
     private Object[] endNode;
     // the index within endNode that signals we're finished -- that is, endNode[endIndex]
is NOT part of the Cursor
@@ -65,11 +50,6 @@ public final class Cursor<V> extends Path implements Iterator<V>
 
     private boolean forwards;
 
-    private Cursor(Object[][] stack, byte[] index)
-    {
-        super(stack, index);
-    }
-
     /**
      * Reset this cursor for the provided tree, to iterate over its entire range
      *
@@ -113,6 +93,7 @@ public final class Cursor<V> extends Path implements Iterator<V>
 
     private void _reset(Object[] btree, Comparator<V> comparator, Object lowerBound,
boolean inclusiveLowerBound, Object upperBound, boolean inclusiveUpperBound, boolean forwards)
     {
+        ensureDepth(btree);
         if (lowerBound == null)
             lowerBound = NEGATIVE_INFINITY;
         if (upperBound == null)
@@ -120,7 +101,7 @@ public final class Cursor<V> extends Path implements Iterator<V>
 
         this.forwards = forwards;
 
-        Path findLast = Path.newPath();
+        Path findLast = new Path(this.path.length);
         if (forwards)
         {
             findLast.find(btree, comparator, upperBound, inclusiveUpperBound ? Op.HIGHER
: Op.CEIL, true);

http://git-wip-us.apache.org/repos/asf/cassandra/blob/948964b5/src/java/org/apache/cassandra/utils/btree/Path.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/Path.java b/src/java/org/apache/cassandra/utils/btree/Path.java
index cbdb160..148c713 100644
--- a/src/java/org/apache/cassandra/utils/btree/Path.java
+++ b/src/java/org/apache/cassandra/utils/btree/Path.java
@@ -20,7 +20,6 @@ package org.apache.cassandra.utils.btree;
 
 import java.util.Comparator;
 
-import static org.apache.cassandra.utils.btree.BTree.MAX_DEPTH;
 import static org.apache.cassandra.utils.btree.BTree.getBranchKeyEnd;
 import static org.apache.cassandra.utils.btree.BTree.getKeyEnd;
 import static org.apache.cassandra.utils.btree.BTree.getLeafKeyEnd;
@@ -46,25 +45,28 @@ class Path
         LOWER   // the greatest element strictly less than the given element
     }
 
-    static Path newPath()
-    {
-        // try to encourage stack allocation - probably misguided/unnecessary. but no harm
-        Object[][] path = new Object[MAX_DEPTH][];
-        byte[] index = new byte[MAX_DEPTH];
-        return new Path(path, index);
-    }
-
     // the path to the searched-for key
-    final Object[][] path;
+    Object[][] path;
     // the index within the node of our path at a given depth
-    final byte[] indexes;
+    byte[] indexes;
     // current depth.  nothing in path[i] for i > depth is valid.
-    byte depth;
+    byte depth = -1;
+
+    Path() { }
+    Path(int depth)
+    {
+        this.path = new Object[depth][];
+        this.indexes = new byte[depth];
+    }
 
-    Path(Object[][] path, byte[] indexes)
+    void ensureDepth(Object[] btree)
     {
-        this.path = path;
-        this.indexes = indexes;
+        int depth = BTree.depth(btree);
+        if (path == null || path.length < depth)
+        {
+            path = new Object[depth][];
+            indexes = new byte[depth];
+        }
     }
 
     /**

http://git-wip-us.apache.org/repos/asf/cassandra/blob/948964b5/test/long/org/apache/cassandra/utils/LongBTreeTest.java
----------------------------------------------------------------------
diff --git a/test/long/org/apache/cassandra/utils/LongBTreeTest.java b/test/long/org/apache/cassandra/utils/LongBTreeTest.java
index d3673fa..514d166 100644
--- a/test/long/org/apache/cassandra/utils/LongBTreeTest.java
+++ b/test/long/org/apache/cassandra/utils/LongBTreeTest.java
@@ -184,7 +184,7 @@ public class LongBTreeTest
                     if (quickEquality)
                         testEqual("", BTree.<Integer>slice(btree, true), canon.keySet().iterator());
                     else
-                        r.addAll(testAllSlices("RND", btree, canon.navigableKeySet()));
+                        r.addAll(testAllSlices("RND", btree, new TreeSet<>(canon.keySet())));
 
                     if (!BTree.isWellFormed(btree))
                         System.out.println("ERROR: Not well formed");


Mime
View raw message