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] [Comment Edited] (CASSANDRA-9991) Implement efficient btree removal
Date Fri, 04 Dec 2015 22:49:11 GMT

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

Piotr Jastrzebski edited comment on CASSANDRA-9991 at 12/4/15 10:49 PM:
------------------------------------------------------------------------

I used the tree from randomizedTest and counted how long it takes to remove all elements in
a random order. BTreeRemoval.remove took 1ms but BTree.transformAndFilter took over 70ms.
This is for the tree of 1000 elements. For 10000 elements BTreeRemoval.remove took 20ms and
BTree.transformAndFilter took 1646ms. It seems to me that the new version is rather faster
than the old way. What we're really comparing here is O(log N) vs O(N). With a pretty big
base of the logarithm. In the test tree has fanfactor of 8 but normally it's probably much
bigger so the difference in speed should be even bigger. Any thoughts?

Edited: I tried the test with fanfactor equal to 32 and both solutions are faster but the
difference is even bigger. BTreeRemoval.remove takes 7ms and BTree.transformAndFilter takes
1436ms.


was (Author: haaawk):
I used the tree from randomizedTest and counted how long it takes to remove all elements in
a random order. BTreeRemoval.remove took 1ms but BTree.transformAndFilter took over 70ms.
This is for the tree of 1000 elements. For 10000 elements BTreeRemoval.remove took 20ms and
BTree.transformAndFilter took 1646ms. It seems to me that the new version is rather faster
than the old way. What we're really comparing here is O(log N) vs O(N). With a pretty big
base of the logarithm. In the test tree has fanfactor of 8 but normally it's probably much
bigger so the difference in speed should be even bigger. Any thoughts?

Edited: I tried the test with fanfactor equal to 32 and both solution are faster but the difference
is even bigger. BTreeRemoval.remove takes 7ms and BTree.transformAndFilter takes 1436ms.

> 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-v3.txt, trunk-9991-v4.txt, trunk-9991-v5.txt, 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