[
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)
