cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jay Zhuang (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-9989) Optimise BTree.Buider
Date Fri, 24 Aug 2018 00:32:00 GMT

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

Jay Zhuang commented on CASSANDRA-9989:
---------------------------------------

[~benedict], thank you very much for the review.

I updated the branch based on your comments: [{{branch: 9989}}|https://github.com/cooldoger/cassandra/commits/9989].
{quote}1. How did you arrive at your childrenNum calculation, and are we certain it is correct?
This is pretty critical for correctness, and hard to test fully, so it would be nice to have
some comments justifying it.
 4. It would be nice if we removed MAX_DEPTH, and just truncated TREE_SIZE to the correct
maximum in our static block
{quote}
Fixed. Now it auto calculates the max height of the tree that we could build.
{quote}2. Why decrement left instead of just counting up the number of values written?
{quote}
It's used to update [{{indexOffsets\[i\]}}|https://github.com/cooldoger/cassandra/commit/0c1a9d11d6540ac7b233c400e0d8b1a56e647d5f#diff-4b911b7d0959c6219175e2349968f3cdR179].
{quote}3. Why is TREE_SIZE indexed from 1, not 0?
{quote}
Just to make the initial calculation easier: [{{TREE_SIZE\[i-1\]}}|https://github.com/cooldoger/cassandra/commit/0c1a9d11d6540ac7b233c400e0d8b1a56e647d5f#diff-4b911b7d0959c6219175e2349968f3cdR84].
With the new patch, it's also used here: to get [{{grandchildSize}}|https://github.com/cooldoger/cassandra/commit/8369dc8b7be3ccf8d1972e9c8cff95adb3493005#diff-4b911b7d0959c6219175e2349968f3cdR196].
{quote}I'm also torn on the splitting of the last two nodes - this is consistent with the
current NodeBuilder logic, but it does complicate the code a little versus evenly splitting
the remaining size amongst all the children.
{quote}
I was thinking to make the tree a little bit more balanced by splitting it equally to the
last 2 nodes. But yes, it also makes sense to make it the same as before. I updated the code
and added an unittest to make sure the BTree is [exactly the same|https://github.com/cooldoger/cassandra/commit/8369dc8b7be3ccf8d1972e9c8cff95adb3493005#diff-cb7b127243f861292899bad7305217dbR592]
as before (with {{[NodeBuilder()|https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java]}}).

> Optimise BTree.Buider
> ---------------------
>
>                 Key: CASSANDRA-9989
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-9989
>             Project: Cassandra
>          Issue Type: Sub-task
>            Reporter: Benedict
>            Assignee: Jay Zhuang
>            Priority: Minor
>             Fix For: 4.x
>
>         Attachments: 9989-trunk.txt
>
>
> BTree.Builder could reduce its copying, and exploit toArray more efficiently, with some
work. It's not very important right now because we don't make as much use of its bulk-add
methods as we otherwise might, however over time this work will become more useful.



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org


Mime
View raw message