cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject [1/2] replace SnapTreeMap/AtomicSortedColumns with BTree/AtomicBTreeColumns patch by Benedict Elliott Smith; reviewed by jbellis for CASSANDRA-6271
Date Sat, 04 Jan 2014 01:11:25 GMT
Updated Branches:
  refs/heads/trunk 9ce5e1ad1 -> 412b053ca


http://git-wip-us.apache.org/repos/asf/cassandra/blob/412b053c/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java b/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java
new file mode 100644
index 0000000..5dbe5df
--- /dev/null
+++ b/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java
@@ -0,0 +1,330 @@
+package org.apache.cassandra.utils.btree;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+import static org.apache.cassandra.utils.btree.BTree.EMPTY_BRANCH;
+import static org.apache.cassandra.utils.btree.BTree.FAN_FACTOR;
+import static org.apache.cassandra.utils.btree.BTree.POSITIVE_INFINITY;
+import static org.apache.cassandra.utils.btree.BTree.compare;
+import static org.apache.cassandra.utils.btree.BTree.find;
+import static org.apache.cassandra.utils.btree.BTree.getKeyEnd;
+import static org.apache.cassandra.utils.btree.BTree.isLeaf;
+
+/**
+ * Represents a level / stack item of in progress modifications to a BTree.
+ */
+final class NodeBuilder
+{
+    private static final int MAX_KEYS = 1 + (FAN_FACTOR * 2);
+
+    // parent stack
+    private NodeBuilder parent, child;
+
+    // buffer for building new nodes
+    private Object[] buildKeys = new Object[MAX_KEYS];  // buffers keys for branches and
leaves
+    private Object[] buildChildren = new Object[1 + MAX_KEYS]; // buffers children for branches
only
+    private int buildKeyPosition;
+    private int buildChildPosition;
+    // we null out the contents of buildKeys/buildChildren when clear()ing them for re-use;
this is where
+    // we track how much we actually have to null out
+    private int maxBuildKeyPosition;
+    private int maxBuildChildPosition;
+
+    // current node of the btree we're modifying/copying from
+    private Object[] copyFrom;
+    // the index of the first key in copyFrom that has not yet been copied into the build
arrays
+    private int copyFromKeyPosition;
+    // the index of the first child node in copyFrom that has not yet been copied into the
build arrays
+    private int copyFromChildPosition;
+
+    // upper bound of range owned by this level; lets us know if we need to ascend back up
the tree
+    // for the next key we update when bsearch gives an insertion point past the end of the
values
+    // in the current node
+    private Object upperBound;
+
+    // ensure we aren't referencing any garbage
+    void clear()
+    {
+        NodeBuilder current = this;
+        while (current != null)
+        {
+            if (current.upperBound != null)
+            {
+                current.reset(null, null);
+                Arrays.fill(current.buildKeys, 0, current.maxBuildKeyPosition, null);
+                Arrays.fill(current.buildChildren, 0, current.maxBuildChildPosition, null);
+                current.maxBuildChildPosition = current.maxBuildKeyPosition = 0;
+            }
+            current = current.child;
+        }
+    }
+
+    // reset counters/setup to copy from provided node
+    void reset(Object[] copyFrom, Object upperBound)
+    {
+        this.copyFrom = copyFrom;
+        this.upperBound = upperBound;
+        maxBuildKeyPosition = Math.max(maxBuildKeyPosition, buildKeyPosition);
+        maxBuildChildPosition = Math.max(maxBuildChildPosition, buildChildPosition);
+        buildKeyPosition = 0;
+        buildChildPosition = 0;
+        copyFromKeyPosition = 0;
+        copyFromChildPosition = 0;
+    }
+
+    /**
+     * Inserts or replaces the provided key, copying all not-yet-visited keys prior to it
into our buffer.
+     *
+     * @param key key we are inserting/replacing
+     * @return the NodeBuilder to retry the update against (a child if we own the range being
updated,
+     * a parent if we do not -- we got here from an earlier key -- and we need to ascend
back up),
+     * or null if we finished the update in this node.
+     */
+    <V> NodeBuilder update(Object key, Comparator<V> comparator, ReplaceFunction<V>
replaceF)
+    {
+        assert copyFrom != null;
+        int copyFromKeyEnd = getKeyEnd(copyFrom);
+
+        int i = find(comparator, (V) key, copyFrom, copyFromKeyPosition, copyFromKeyEnd);
+        boolean found = i >= 0; // exact key match?
+        boolean owns = true; // true iff this node (or a child) should contain the key
+        if (!found)
+        {
+            i = -i - 1;
+            if (i == copyFromKeyEnd && compare(comparator, upperBound, key) <=
0)
+                owns = false;
+        }
+
+        if (isLeaf(copyFrom))
+        {
+            // copy keys from the original node up to prior to the found index
+            copyKeys(i);
+
+            if (owns)
+            {
+                if (found)
+                    replaceNextKey(key, replaceF);
+                else
+                    addNewKey(key, replaceF); // handles splitting parent if necessary via
ensureRoom
+
+                // done, so return null
+                return null;
+            }
+
+            // if we don't own it, all we need to do is ensure we've copied everything in
this node
+            // (which we have done, since not owning means pos >= keyEnd), ascend, and
let Modifier.update
+            // retry against the parent node.  The if/ascend after the else branch takes
care of that.
+        }
+        else
+        {
+            // branch
+            if (found)
+            {
+                copyKeys(i);
+                replaceNextKey(key, replaceF);
+                copyChildren(i + 1);
+                return null;
+            }
+            else if (owns)
+            {
+                copyKeys(i);
+                copyChildren(i);
+
+                // belongs to the range owned by this node, but not equal to any key in the
node
+                // so descend into the owning child
+                Object newUpperBound = i < copyFromKeyEnd ? copyFrom[i] : upperBound;
+                Object[] descendInto = (Object[]) copyFrom[copyFromKeyEnd + i];
+                ensureChild().reset(descendInto, newUpperBound);
+                return child;
+            }
+            else
+            {
+                // ensure we've copied all keys and children
+                copyKeys(copyFromKeyEnd);
+                copyChildren(copyFromKeyEnd + 1); // since we know that there are exactly
1 more child nodes, than keys
+            }
+        }
+
+        if (key == POSITIVE_INFINITY && isRoot())
+            return null;
+
+        return ascend();
+    }
+
+
+    // UTILITY METHODS FOR IMPLEMENTATION OF UPDATE/BUILD/DELETE
+
+    boolean isRoot()
+    {
+        // if parent == null, or parent.upperBound == null, then we have not initialised
a parent builder,
+        // so we are the top level builder holding modifications; if we have more than FAN_FACTOR
items, though,
+        // we are not a valid root so we would need to spill-up to create a new root
+        return (parent == null || parent.upperBound == null) && buildKeyPosition
<= FAN_FACTOR;
+    }
+
+    // ascend to the root node, splitting into proper node sizes as we go; useful for building
+    // where we work only on the newest child node, which may construct many spill-over parents
as it goes
+    NodeBuilder ascendToRoot()
+    {
+        NodeBuilder current = this;
+        while (!current.isRoot())
+            current = current.ascend();
+        return current;
+    }
+
+    // builds a new root BTree node - must be called on root of operation
+    Object[] toNode()
+    {
+        assert buildKeyPosition <= FAN_FACTOR && buildKeyPosition > 0 : buildKeyPosition;
+        return buildFromRange(0, buildKeyPosition, isLeaf(copyFrom));
+    }
+
+    // finish up this level and pass any constructed children up to our parent, ensuring
a parent exists
+    private NodeBuilder ascend()
+    {
+        ensureParent();
+        boolean isLeaf = isLeaf(copyFrom);
+        if (buildKeyPosition > FAN_FACTOR)
+        {
+            // split current node and move the midpoint into parent, with the two halves
as children
+            int mid = buildKeyPosition / 2;
+            parent.addExtraChild(buildFromRange(0, mid, isLeaf), buildKeys[mid]);
+            parent.finishChild(buildFromRange(mid + 1, buildKeyPosition - (mid + 1), isLeaf));
+        }
+        else
+        {
+            parent.finishChild(buildFromRange(0, buildKeyPosition, isLeaf));
+        }
+        return parent;
+    }
+
+    // copy keys from copyf to the builder, up to the provided index in copyf (exclusive)
+    private void copyKeys(int upToKeyPosition)
+    {
+        if (copyFromKeyPosition >= upToKeyPosition)
+            return;
+
+        int len = upToKeyPosition - copyFromKeyPosition;
+        assert len <= FAN_FACTOR : upToKeyPosition + "," + copyFromKeyPosition;
+
+        ensureRoom(buildKeyPosition + len);
+        System.arraycopy(copyFrom, copyFromKeyPosition, buildKeys, buildKeyPosition, len);
+        copyFromKeyPosition = upToKeyPosition;
+        buildKeyPosition += len;
+    }
+
+    // skips the next key in copyf, and puts the provided key in the builder instead
+    private <V> void replaceNextKey(Object with, ReplaceFunction<V> replaceF)
+    {
+        // (this first part differs from addNewKey in that we pass the replaced object to
replaceF as well)
+        ensureRoom(buildKeyPosition + 1);
+        if (replaceF != null)
+            with = replaceF.apply((V) copyFrom[copyFromKeyPosition], (V) with);
+        buildKeys[buildKeyPosition++] = with;
+
+        copyFromKeyPosition++;
+    }
+
+    // puts the provided key in the builder, with no impact on treatment of data from copyf
+    <V> void addNewKey(Object key, ReplaceFunction<V> replaceF)
+    {
+        ensureRoom(buildKeyPosition + 1);
+        if (replaceF != null)
+            key = replaceF.apply(null, (V) key);
+        buildKeys[buildKeyPosition++] = key;
+    }
+
+    // copies children from copyf to the builder, up to the provided index in copyf (exclusive)
+    private void copyChildren(int upToChildPosition)
+    {
+        // (ensureRoom isn't called here, as we should always be at/behind key additions)
+        if (copyFromChildPosition >= upToChildPosition)
+            return;
+        int len = upToChildPosition - copyFromChildPosition;
+        System.arraycopy(copyFrom, getKeyEnd(copyFrom) + copyFromChildPosition, buildChildren,
buildChildPosition, len);
+        copyFromChildPosition = upToChildPosition;
+        buildChildPosition += len;
+    }
+
+    // adds a new and unexpected child to the builder - called by children that overflow
+    private void addExtraChild(Object[] child, Object upperBound)
+    {
+        ensureRoom(buildKeyPosition + 1);
+        buildKeys[buildKeyPosition++] = upperBound;
+        buildChildren[buildChildPosition++] = child;
+    }
+
+    // adds a replacement expected child to the builder - called by children prior to ascending
+    private void finishChild(Object[] child)
+    {
+        buildChildren[buildChildPosition++] = child;
+        copyFromChildPosition++;
+    }
+
+    // checks if we can add the requested keys+children to the builder, and if not we spill-over
into our parent
+    private void ensureRoom(int nextBuildKeyPosition)
+    {
+        if (nextBuildKeyPosition < MAX_KEYS)
+            return;
+
+        // flush even number of items so we don't waste leaf space repeatedly
+        Object[] flushUp = buildFromRange(0, FAN_FACTOR, isLeaf(copyFrom));
+        ensureParent().addExtraChild(flushUp, buildKeys[FAN_FACTOR]);
+        int size = FAN_FACTOR + 1;
+        assert size <= buildKeyPosition : buildKeyPosition + "," + nextBuildKeyPosition;
+        System.arraycopy(buildKeys, size, buildKeys, 0, buildKeyPosition - size);
+        buildKeyPosition -= size;
+        maxBuildKeyPosition = buildKeys.length;
+        if (buildChildPosition > 0)
+        {
+            System.arraycopy(buildChildren, size, buildChildren, 0, buildChildPosition -
size);
+            buildChildPosition -= size;
+            maxBuildChildPosition = buildChildren.length;
+        }
+    }
+
+    // builds and returns a node from the buffered objects in the given range
+    private Object[] buildFromRange(int offset, int keyLength, boolean isLeaf)
+    {
+        Object[] a;
+        if (isLeaf)
+        {
+            a = new Object[keyLength + (keyLength & 1)];
+            System.arraycopy(buildKeys, offset, a, 0, keyLength);
+        }
+        else
+        {
+            a = new Object[1 + (keyLength * 2)];
+            System.arraycopy(buildKeys, offset, a, 0, keyLength);
+            System.arraycopy(buildChildren, offset, a, keyLength, keyLength + 1);
+        }
+        return a;
+    }
+
+    // checks if there is an initialised parent, and if not creates/initialises one and returns
it.
+    // different to ensureChild, as we initialise here instead of caller, as parents in general
should
+    // already be initialised, and only aren't in the case where we are overflowing the original
root node
+    private NodeBuilder ensureParent()
+    {
+        if (parent == null)
+        {
+            parent = new NodeBuilder();
+            parent.child = this;
+        }
+        if (parent.upperBound == null)
+            parent.reset(EMPTY_BRANCH, upperBound);
+        return parent;
+    }
+
+    // ensures a child level exists and returns it
+    NodeBuilder ensureChild()
+    {
+        if (child == null)
+        {
+            child = new NodeBuilder();
+            child.parent = this;
+        }
+        return child;
+    }
+}

http://git-wip-us.apache.org/repos/asf/cassandra/blob/412b053c/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
new file mode 100644
index 0000000..500f615
--- /dev/null
+++ b/src/java/org/apache/cassandra/utils/btree/Path.java
@@ -0,0 +1,274 @@
+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;
+import static org.apache.cassandra.utils.btree.BTree.isLeaf;
+
+/**
+ * An internal class for searching and iterating through a tree.  As it traverses the tree,
+ * it adds the nodes visited to a stack.  This allows us to backtrack from a child node
+ * to its parent.
+ *
+ * As we navigate the tree, we destructively modify this stack.
+ *
+ * Path is only intended to be used via Cursor.
+ */
+class Path
+{
+    // operations corresponding to the ones in NavigableSet
+    static enum Op
+    {
+        CEIL,   // the least element greater than or equal to the given element
+        FLOOR,  // the greatest element less than or equal to the given element
+        HIGHER, // the least element strictly greater than the given element
+        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;
+    // the index within the node of our path at a given depth
+    final byte[] indexes;
+    // current depth.  nothing in path[i] for i > depth is valid.
+    byte depth;
+
+    Path(Object[][] path, byte[] indexes)
+    {
+        this.path = path;
+        this.indexes = indexes;
+    }
+
+    /**
+     * Find the provided key in the tree rooted at node, and store the root to it in the
path
+     *
+     * @param node       the tree to search in
+     * @param comparator the comparator defining the order on the tree
+     * @param target     the key to search for
+     * @param mode       the type of search to perform
+     * @param forwards   if the path should be setup for forward or backward iteration
+     * @param <V>
+     */
+    <V> void find(Object[] node, Comparator<V> comparator, Object target, Op
mode, boolean forwards)
+    {
+        // TODO : should not require parameter 'forwards' - consider modifying index to represent
both
+        // child and key position, as opposed to just key position (which necessitates a
different value depending
+        // on which direction you're moving in. Prerequisite for making Path public and using
to implement general
+        // search
+
+        depth = -1;
+        while (true)
+        {
+            int keyEnd = getKeyEnd(node);
+
+            // search for the target in the current node
+            int i = BTree.find(comparator, target, node, 0, keyEnd);
+            if (i >= 0)
+            {
+                // exact match. transform exclusive bounds into the correct index by moving
back or forwards one
+                push(node, i);
+                switch (mode)
+                {
+                    case HIGHER:
+                        successor();
+                        break;
+                    case LOWER:
+                        predecessor();
+                }
+                return;
+            }
+
+            // traverse into the appropriate child
+            if (!isLeaf(node))
+            {
+                i = -i - 1;
+                push(node, forwards ? i - 1 : i);
+                node = (Object[]) node[keyEnd + i];
+                continue;
+            }
+
+            // bottom of the tree and still not found.  pick the right index to satisfy Op
+            i = -i - 1;
+            switch (mode)
+            {
+                case FLOOR:
+                case LOWER:
+                    i--;
+            }
+
+            if (i < 0)
+            {
+                push(node, 0);
+                predecessor();
+            }
+            else if (i >= keyEnd)
+            {
+                push(node, keyEnd - 1);
+                successor();
+            }
+            else
+            {
+                push(node, i);
+            }
+
+            return;
+        }
+    }
+
+    private boolean isRoot()
+    {
+        return depth == 0;
+    }
+
+    private void pop()
+    {
+        depth--;
+    }
+
+    Object[] currentNode()
+    {
+        return path[depth];
+    }
+
+    byte currentIndex()
+    {
+        return indexes[depth];
+    }
+
+    private void push(Object[] node, int index)
+    {
+        path[++depth] = node;
+        indexes[depth] = (byte) index;
+    }
+
+    void setIndex(int index)
+    {
+        indexes[depth] = (byte) index;
+    }
+
+    // move to the next key in the tree
+    void successor()
+    {
+        Object[] node = currentNode();
+        int i = currentIndex();
+
+        if (!isLeaf(node))
+        {
+            // if we're on a key in a branch, we MUST have a descendant either side of us,
+            // so we always go down the left-most child until we hit a leaf
+            node = (Object[]) node[getBranchKeyEnd(node) + i + 1];
+            while (!isLeaf(node))
+            {
+                push(node, -1);
+                node = (Object[]) node[getBranchKeyEnd(node)];
+            }
+            push(node, 0);
+            return;
+        }
+
+        // if we haven't reached the end of this leaf, just increment our index and return
+        i += 1;
+        if (i < getLeafKeyEnd(node))
+        {
+            // moved to the next key in the same leaf
+            setIndex(i);
+            return;
+        }
+
+        // we've reached the end of this leaf,
+        // so go up until we reach something we've not finished visiting
+        while (!isRoot())
+        {
+            pop();
+            i = currentIndex() + 1;
+            node = currentNode();
+            if (i < getKeyEnd(node))
+            {
+                setIndex(i);
+                return;
+            }
+        }
+
+        // we've visited the last key in the root node, so we're done
+        setIndex(getKeyEnd(node));
+    }
+
+    // move to the previous key in the tree
+    void predecessor()
+    {
+        Object[] node = currentNode();
+        int i = currentIndex();
+
+        if (!isLeaf(node))
+        {
+            // if we're on a key in a branch, we MUST have a descendant either side of us
+            // so we always go down the right-most child until we hit a leaf
+            node = (Object[]) node[getBranchKeyEnd(node) + i];
+            while (!isLeaf(node))
+            {
+                i = getBranchKeyEnd(node);
+                push(node, i);
+                node = (Object[]) node[i * 2];
+            }
+            push(node, getLeafKeyEnd(node) - 1);
+            return;
+        }
+
+        // if we haven't reached the beginning of this leaf, just decrement our index and
return
+        i -= 1;
+        if (i >= 0)
+        {
+            setIndex(i);
+            return;
+        }
+
+        // we've reached the beginning of this leaf,
+        // so go up until we reach something we've not finished visiting
+        while (!isRoot())
+        {
+            pop();
+            i = currentIndex() - 1;
+            if (i >= 0)
+            {
+                setIndex(i);
+                return;
+            }
+        }
+
+        // we've visited the last key in the root node, so we're done
+        setIndex(-1);
+    }
+
+    Object currentKey()
+    {
+        return currentNode()[currentIndex()];
+    }
+
+    int compareTo(Path that, boolean forwards)
+    {
+        int d = Math.min(this.depth, that.depth);
+        for (int i = 0; i <= d; i++)
+        {
+            int c = this.indexes[i] - that.indexes[i];
+            if (c != 0)
+                return c;
+        }
+        // identical indices up to depth, so if somebody is lower depth they are on a later
item if iterating forwards
+        // and an earlier item if iterating backwards, as the node at max common depth must
be a branch if they are
+        // different depths, and branches that are currently descended into lag the child
index they are in when iterating forwards,
+        // i.e. if they are in child 0 they record an index of -1 forwards, or 0 when backwards
+        d = this.depth - that.depth;
+        return forwards ? d : -d;
+    }
+}
+

http://git-wip-us.apache.org/repos/asf/cassandra/blob/412b053c/src/java/org/apache/cassandra/utils/btree/ReplaceFunction.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/ReplaceFunction.java b/src/java/org/apache/cassandra/utils/btree/ReplaceFunction.java
new file mode 100644
index 0000000..bf783b0
--- /dev/null
+++ b/src/java/org/apache/cassandra/utils/btree/ReplaceFunction.java
@@ -0,0 +1,12 @@
+package org.apache.cassandra.utils.btree;
+
+/**
+ * An interface defining a function to be applied to both the object we are replacing in
a BTree and
+ * the object that is intended to replace it, returning the object to actually replace it.
+ *
+ * @param <V>
+ */
+public interface ReplaceFunction<V>
+{
+    V apply(V replaced, V update);
+}

http://git-wip-us.apache.org/repos/asf/cassandra/blob/412b053c/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
new file mode 100644
index 0000000..577977d
--- /dev/null
+++ b/test/long/org/apache/cassandra/utils/LongBTreeTest.java
@@ -0,0 +1,335 @@
+package org.apache.cassandra.utils;
+
+import com.google.common.util.concurrent.*;
+import com.yammer.metrics.Metrics;
+import com.yammer.metrics.core.Timer;
+import com.yammer.metrics.core.TimerContext;
+import com.yammer.metrics.stats.Snapshot;
+import edu.stanford.ppl.concurrent.SnapTreeMap;
+import org.apache.cassandra.concurrent.NamedThreadFactory;
+import org.apache.cassandra.utils.btree.BTree;
+import org.apache.cassandra.utils.btree.BTreeSet;
+import org.junit.*;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+import java.util.NavigableSet;
+import java.util.Random;
+import java.util.TreeMap;
+import java.util.TreeSet;
+import java.util.concurrent.Callable;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.TimeUnit;
+
+// TODO : should probably lower fan-factor for tests to make them more intensive
+public class LongBTreeTest
+{
+
+    private static final Timer BTREE_TIMER = Metrics.newTimer(BTree.class, "BTREE", TimeUnit.NANOSECONDS,
TimeUnit.NANOSECONDS);
+    private static final Timer TREE_TIMER = Metrics.newTimer(BTree.class, "TREE", TimeUnit.NANOSECONDS,
TimeUnit.NANOSECONDS);
+    private static final ExecutorService MODIFY = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors(),
new NamedThreadFactory("MODIFY"));
+    private static final ExecutorService COMPARE = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors(),
new NamedThreadFactory("COMPARE"));
+
+    static
+    {
+        System.setProperty("cassandra.btree.fanfactor", "4");
+    }
+
+    @Test
+    public void testOversizedMiddleInsert()
+    {
+        TreeSet<Integer> canon = new TreeSet<>();
+        for (int i = 0 ; i < 10000000 ; i++)
+            canon.add(i);
+        Object[] btree = BTree.build(Arrays.asList(Integer.MIN_VALUE, Integer.MAX_VALUE),
ICMP, true);
+        btree = BTree.update(btree, ICMP, canon, true);
+        canon.add(Integer.MIN_VALUE);
+        canon.add(Integer.MAX_VALUE);
+        Assert.assertTrue(BTree.isWellFormed(btree, ICMP));
+        testEqual("Oversize", BTree.<Integer>slice(btree, true), canon.iterator());
+    }
+
+    @Test
+    public void testIndividualInsertsSmallOverlappingRange() throws ExecutionException, InterruptedException
+    {
+        testInsertions(100000000, 50, 1, 1, true);
+    }
+
+    @Test
+    public void testBatchesSmallOverlappingRange() throws ExecutionException, InterruptedException
+    {
+        testInsertions(100000000, 50, 1, 5, true);
+    }
+
+    @Test
+    public void testIndividualInsertsMediumSparseRange() throws ExecutionException, InterruptedException
+    {
+        testInsertions(10000000, 500, 10, 1, true);
+    }
+
+    @Test
+    public void testBatchesMediumSparseRange() throws ExecutionException, InterruptedException
+    {
+        testInsertions(10000000, 500, 10, 10, true);
+    }
+
+    @Test
+    public void testLargeBatchesLargeRange() throws ExecutionException, InterruptedException
+    {
+        testInsertions(10000000, 5000, 3, 100, true);
+    }
+
+    @Test
+    public void testSlicingSmallRandomTrees() throws ExecutionException, InterruptedException
+    {
+        testInsertions(10000, 50, 10, 10, false);
+    }
+
+    private static void testInsertions(int totalCount, int perTestCount, int testKeyRatio,
int modificationBatchSize, boolean quickEquality) throws ExecutionException, InterruptedException
+    {
+        int batchesPerTest = perTestCount / modificationBatchSize;
+        int maximumRunLength = 100;
+        int testKeyRange = perTestCount * testKeyRatio;
+        int tests = totalCount / perTestCount;
+        System.out.println(String.format("Performing %d tests of %d operations, with %.2f
max size/key-range ratio in batches of ~%d ops",
+                tests, perTestCount, 1 / (float) testKeyRatio, modificationBatchSize));
+
+        // if we're not doing quick-equality, we can spam with garbage for all the checks
we perform, so we'll split the work into smaller chunks
+        int chunkSize = quickEquality ? tests : (int) (100000 / Math.pow(perTestCount, 2));
+        for (int chunk = 0 ; chunk < tests ; chunk += chunkSize)
+        {
+            final List<ListenableFutureTask<List<ListenableFuture<?>>>>
outer = new ArrayList<>();
+            for (int i = 0 ; i < chunkSize ; i++)
+            {
+                outer.add(doOneTestInsertions(testKeyRange, maximumRunLength, modificationBatchSize,
batchesPerTest, quickEquality));
+            }
+
+            final List<ListenableFuture<?>> inner = new ArrayList<>();
+            int complete = 0;
+            int reportInterval = totalCount / 100;
+            int lastReportAt = 0;
+            for (ListenableFutureTask<List<ListenableFuture<?>>> f : outer)
+            {
+                inner.addAll(f.get());
+                complete += perTestCount;
+                if (complete - lastReportAt >= reportInterval)
+                {
+                    System.out.println(String.format("Completed %d of %d operations", (chunk
* perTestCount) + complete, totalCount));
+                    lastReportAt = complete;
+                }
+            }
+            Futures.allAsList(inner).get();
+        }
+        Snapshot snap = BTREE_TIMER.getSnapshot();
+        System.out.println(String.format("btree   : %.2fns, %.2fns, %.2fns", snap.getMedian(),
snap.get95thPercentile(), snap.get999thPercentile()));
+        snap = TREE_TIMER.getSnapshot();
+        System.out.println(String.format("snaptree: %.2fns, %.2fns, %.2fns", snap.getMedian(),
snap.get95thPercentile(), snap.get999thPercentile()));
+        System.out.println("Done");
+    }
+
+    private static ListenableFutureTask<List<ListenableFuture<?>>> doOneTestInsertions(final
int upperBound, final int maxRunLength, final int averageModsPerIteration, final int iterations,
final boolean quickEquality)
+    {
+        ListenableFutureTask<List<ListenableFuture<?>>> f = ListenableFutureTask.create(new
Callable<List<ListenableFuture<?>>>()
+        {
+
+            @Override
+            public List<ListenableFuture<?>> call()
+            {
+                final List<ListenableFuture<?>> r = new ArrayList<>();
+                SnapTreeMap<Integer, Integer> canon = new SnapTreeMap<>();
+                Object[] btree = BTree.empty();
+                final TreeMap<Integer, Integer> buffer = new TreeMap<>();
+                final Random rnd = new Random();
+                for (int i = 0 ; i < iterations ; i++)
+                {
+                    buffer.clear();
+                    int mods = (averageModsPerIteration >> 1) + 1 + rnd.nextInt(averageModsPerIteration);
+                    while (mods > 0)
+                    {
+                        int v = rnd.nextInt(upperBound);
+                        int rc = Math.max(0, Math.min(mods, maxRunLength) - 1);
+                        int c = 1 + (rc <= 0 ? 0 : rnd.nextInt(rc));
+                        for (int j = 0 ; j < c ; j++)
+                        {
+                            buffer.put(v, v);
+                            v++;
+                        }
+                        mods -= c;
+                    }
+                    TimerContext ctxt;
+                    ctxt = TREE_TIMER.time();
+                    canon = canon.clone();
+                    canon.putAll(buffer);
+                    ctxt.stop();
+                    ctxt = BTREE_TIMER.time();
+                    btree = BTree.update(btree, ICMP, buffer.keySet(), true, null, null);
+                    ctxt.stop();
+
+                    if (quickEquality)
+                        testEqual("", BTree.<Integer>slice(btree, true), canon.keySet().iterator());
+                    else
+                        r.addAll(testAllSlices("RND", btree, canon.keySet()));
+
+                    if (!BTree.isWellFormed(btree))
+                        System.out.println("ERROR: Not well formed");
+                }
+                return r;
+            }
+        });
+        MODIFY.execute(f);
+        return f;
+    }
+
+    @Test
+    public void testSlicingAllSmallTrees() throws ExecutionException, InterruptedException
+    {
+        Object[] cur = BTree.empty();
+        TreeSet<Integer> canon = new TreeSet<>();
+        // we set FAN_FACTOR to 4, so 128 items is four levels deep, three fully populated
+        for (int i = 0 ; i < 128 ; i++)
+        {
+            String id = String.format("[0..%d)", canon.size());
+            System.out.println("Testing " + id);
+            Futures.allAsList(testAllSlices(id, cur, canon)).get();
+            cur = BTree.update(cur, ICMP, Arrays.asList(i), true, null, null);
+            canon.add(i);
+        }
+    }
+
+    static final Comparator<Integer> ICMP = new Comparator<Integer>()
+    {
+        @Override
+        public int compare(Integer o1, Integer o2)
+        {
+            return Integer.compare(o1, o2);
+        }
+    };
+
+    private static List<ListenableFuture<?>> testAllSlices(String id, Object[]
btree, NavigableSet<Integer> canon)
+    {
+        List<ListenableFuture<?>> waitFor = new ArrayList<>();
+        testAllSlices(id + " ASC", new BTreeSet<>(btree, ICMP), canon, true, waitFor);
+        testAllSlices(id + " DSC", new BTreeSet<>(btree, ICMP).descendingSet(), canon.descendingSet(),
false, waitFor);
+        return waitFor;
+    }
+
+    private static void testAllSlices(String id, NavigableSet<Integer> btree, NavigableSet<Integer>
canon, boolean ascending, List<ListenableFuture<?>> results)
+    {
+        testOneSlice(id, btree, canon, results);
+        for (Integer lb : range(canon.size(), Integer.MIN_VALUE, ascending))
+        {
+            // test head/tail sets
+            testOneSlice(String.format("%s->[%d..)", id, lb), btree.headSet(lb, true),
canon.headSet(lb, true), results);
+            testOneSlice(String.format("%s->(%d..)", id, lb), btree.headSet(lb, false),
canon.headSet(lb, false), results);
+            testOneSlice(String.format("%s->(..%d]", id, lb), btree.tailSet(lb, true),
canon.tailSet(lb, true), results);
+            testOneSlice(String.format("%s->(..%d]", id, lb), btree.tailSet(lb, false),
canon.tailSet(lb, false), results);
+            for (Integer ub : range(canon.size(), lb, ascending))
+            {
+                // test subsets
+                testOneSlice(String.format("%s->[%d..%d]", id, lb, ub), btree.subSet(lb,
true, ub, true), canon.subSet(lb, true, ub, true), results);
+                testOneSlice(String.format("%s->(%d..%d]", id, lb, ub), btree.subSet(lb,
false, ub, true), canon.subSet(lb, false, ub, true), results);
+                testOneSlice(String.format("%s->[%d..%d)", id, lb, ub), btree.subSet(lb,
true, ub, false), canon.subSet(lb, true, ub, false), results);
+                testOneSlice(String.format("%s->(%d..%d)", id, lb, ub), btree.subSet(lb,
false, ub, false), canon.subSet(lb, false, ub, false), results);
+            }
+        }
+    }
+
+    private static void testOneSlice(final String id, final NavigableSet<Integer> test,
final NavigableSet<Integer> canon, List<ListenableFuture<?>> results)
+    {
+        ListenableFutureTask<?> f = ListenableFutureTask.create(new Runnable()
+        {
+
+            @Override
+            public void run()
+            {
+                test(id + " Count", test.size(), canon.size());
+                testEqual(id, test.iterator(), canon.iterator());
+                testEqual(id + "->DSCI", test.descendingIterator(), canon.descendingIterator());
+                testEqual(id + "->DSCS", test.descendingSet().iterator(), canon.descendingSet().iterator());
+                testEqual(id + "->DSCS->DSCI", test.descendingSet().descendingIterator(),
canon.descendingSet().descendingIterator());
+            }
+        }, null);
+        results.add(f);
+        COMPARE.execute(f);
+    }
+
+    private static void test(String id, int test, int expect)
+    {
+        if (test != expect)
+        {
+            System.out.println(String.format("%s: Expected %d, Got %d", id, expect, test));
+        }
+    }
+
+    private static <V> void testEqual(String id, Iterator<V> btree, Iterator<V>
canon)
+    {
+        while (btree.hasNext() && canon.hasNext())
+        {
+            Object i = btree.next();
+            Object j = canon.next();
+            if (!i.equals(j))
+                System.out.println(String.format("%s: Expected %d, Got %d", id, j, i));
+        }
+        while (btree.hasNext())
+            System.out.println(String.format("%s: Expected <Nil>, Got %d", id, btree.next()));
+        while (canon.hasNext())
+            System.out.println(String.format("%s: Expected %d, Got Nil", id, canon.next()));
+    }
+
+    // should only be called on sets that range from 0->N or N->0
+    private static final Iterable<Integer> range(final int size, final int from, final
boolean ascending)
+    {
+        return new Iterable<Integer>()
+        {
+            int cur;
+            int delta;
+            int end;
+            {
+                if (ascending)
+                {
+                    end = size + 1;
+                    cur = from == Integer.MIN_VALUE ? -1 : from;
+                    delta = 1;
+                }
+                else
+                {
+                    end = -2;
+                    cur = from == Integer.MIN_VALUE ? size : from;
+                    delta = -1;
+                }
+            }
+            @Override
+            public Iterator<Integer> iterator()
+            {
+                return new Iterator<Integer>()
+                {
+                    @Override
+                    public boolean hasNext()
+                    {
+                        return cur != end;
+                    }
+
+                    @Override
+                    public Integer next()
+                    {
+                        Integer r = cur;
+                        cur += delta;
+                        return r;
+                    }
+
+                    @Override
+                    public void remove()
+                    {
+                        throw new UnsupportedOperationException();
+                    }
+                };
+            }
+        };
+    }
+
+}


Mime
View raw message