cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Branimir Lambov (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
Date Wed, 25 Nov 2015 14:02:11 GMT

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

Branimir Lambov commented on CASSANDRA-9991:
--------------------------------------------

Thanks, I think the code is much easier to understand now.

Performance-wise, I still think you can improve significantly on the number of costly comparisons
if you switch to working with indices. You are currently doing three passes over the tree
using binary searches with the provided comparator (and the second version increases that
number). That can be reduced that to just one {{findIndex}} pass, where the later stages of
the processing do integer searches (see {{BTree.findByIndex}}).

bq. 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?

The test can have a fixed seed, and just be something that's large enough, hopefully covering
scenarios that we did not think of. For example,
{code}
    @Test
    public void randomizedTest()
    {
        Random rand = new Random(2);
        SortedSet<Integer> data = new TreeSet<>();
        for (int i = 0; i < 1000; ++i)
            data.add(rand.nextInt());
        Object[] btree = BTree.build(data, UpdateFunction.<Integer>noOp());

        assertTrue(BTree.isWellFormed(btree, CMP));
        assertTrue(Iterables.elementsEqual(data, BTree.iterable(btree)));
        while (btree != BTree.empty())
        {
            int idx = rand.nextInt(BTree.size(btree));
            Integer val = BTree.findByIndex(btree, idx);
            assertTrue(data.remove(val));
            Object[] next = BTreeRemoval.remove(btree, CMP, val);
            assertTrue(next != btree);
            assertTrue(BTree.isWellFormed(next, CMP));
            assertTrue(Iterables.elementsEqual(data, BTree.iterable(next)));
            btree = next;
        }
    }
{code}
which currently fails an {{isWellFormed}} test.

bq. Bottom up was messier

Thank you, I thought you probably already tried it and wanted to hear why it didn't work out.


> 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, trunk-9991.txt-v2
>
>
> 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