cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Piotr Jastrzebski (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
Date Tue, 24 Nov 2015 22:39:11 GMT

    [ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15025595#comment-15025595
] 

Piotr Jastrzebski commented on CASSANDRA-9991:
----------------------------------------------

Hi Branimir,

Thanks for the review.

I wasn't sure how important the performance is in this case. I somehow assumed it's quite
important. I was definitely trying to avoid array copying but I wasn't sure how expensive
is Comparator.compare on the keys. I can imagine keys with very expensive comparison.

If we don't mind some unnecessary compare calls then remove() can be reduced to:

public static <V> Object[] remove(final Object[] btree, final Comparator<? super
V> comparator, V elem)
    {
        if (BTree.isEmpty(btree))
            return btree;
        final Object[] node = BTree.findNode(btree, comparator, elem);
        if (node == null)
            return btree;
        if (BTree.size(btree) == 1)
            return BTree.empty();
        V valueToSwap = null;
        if (!BTree.isLeaf(node))
        {
            valueToSwap = elem;
            elem = BTree.lower(btree, comparator, elem);
        }
        Object[] result = removeFromLeaf(btree, comparator, elem);
        if (valueToSwap != null)
        {
            // we can modify result because the node containing elem is a copy
            swap(result, comparator, valueToSwap, elem);
        }
        return result;
    }

I tried different approaches and this was the cleanest. Bottom up was messier but a recursive
top down solution will probably be cleaner. Looking at BTree.java I assumed recursion is not
welcome since it has some performance penalty.

If you don't mind I would like to leave the checks around System.arraycopy - it does JNI call
which is much more expensive than a simple check and they are well encapsulated in copyKeys/Children
anyway.

I added the check to isWellFormed.

Two parameters in copyBranchWithKeyAndChildRemove were useful in different versions I had.
Now I changed it to copyWithKeyAndChildRemoved and used in rotateLeft/Right.

Calculation of newNextNode size was meant to be '((nextKeyEnd & 1) == 1 ? 2 : 1)'  thanks
for catching this. Fixed.

I reordered cases in removeFromLeaf.

I introduced copyWithKeyAndChildInserted.

About the random test - I don't think it's a good idea to create a random unit tests. The
fundamental attribute of unit test is its repeatability. Is there any convention in Cassandra
how to create a randomized fuzzy tests?

Please have another look.

> Implement efficient btree removal
> ---------------------------------
>
>                 Key: CASSANDRA-9991
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-9991
>             Project: Cassandra
>          Issue Type: Sub-task
>            Reporter: Benedict
>              Labels: patch
>             Fix For: 3.x
>
>         Attachments: trunk-9991.txt
>
>
> Currently removal is implemented as a reconstruction by filtering and iterator over the
original btree. This could be much more efficient, editing just the necessary nodes. 



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message