[jira] [Commented] (CASSANDRA-9988) Introduce leaf-only iterator
[ https://issues.apache.org/jira/browse/CASSANDRA-9988?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15118944#comment-15118944 ] Piotr Jastrzebski commented on CASSANDRA-9988: -- That's very interesting. Thanks for the article :). > Introduce leaf-only iterator > > > Key: CASSANDRA-9988 > URL: https://issues.apache.org/jira/browse/CASSANDRA-9988 > Project: Cassandra > Issue Type: Sub-task >Reporter: Benedict >Priority: Minor > Labels: patch > Fix For: 3.x > > Attachments: trunk-9988.txt > > > In many cases we have small btrees, small enough to fit in a single leaf > page. In this case it _may_ be more efficient to specialise our iterator. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (CASSANDRA-9988) Introduce leaf-only iterator
[ https://issues.apache.org/jira/browse/CASSANDRA-9988?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15117922#comment-15117922 ] Piotr Jastrzebski commented on CASSANDRA-9988: -- What do you mean by efficient method dispatch? Could you please explain me why having two implementations of an interface will result in faster method invocations (if that's what you have in mind) than when having three implementations? I know that implementing too many interfaces can have negative impact on performance due to collisions in method offsets but I never heard that number of implementations has any performance impact. > Introduce leaf-only iterator > > > Key: CASSANDRA-9988 > URL: https://issues.apache.org/jira/browse/CASSANDRA-9988 > Project: Cassandra > Issue Type: Sub-task >Reporter: Benedict >Priority: Minor > Labels: patch > Fix For: 3.x > > Attachments: trunk-9988.txt > > > In many cases we have small btrees, small enough to fit in a single leaf > page. In this case it _may_ be more efficient to specialise our iterator. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Comment Edited] (CASSANDRA-9991) Implement efficient btree removal
[ 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 1 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 1 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)
[jira] [Comment Edited] (CASSANDRA-9991) Implement efficient btree removal
[ 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:48 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 1 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 equals to 32 and both solution 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 1 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? > 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)
[jira] [Comment Edited] (CASSANDRA-9991) Implement efficient btree removal
[ 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:48 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 1 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. 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 1 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 equals 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)
[jira] [Comment Edited] (CASSANDRA-9991) Implement efficient btree removal
[ 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:44 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 1 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? 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 1 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. Any thoughts? > 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)
[jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15042357#comment-15042357 ] Piotr Jastrzebski commented on CASSANDRA-9991: -- 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 1 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. Any thoughts? > 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)
[jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15041987#comment-15041987 ] Piotr Jastrzebski commented on CASSANDRA-9991: -- I will try to create a benchmark this weekend and let you know what the results are. > 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)
[jira] [Comment Edited] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15032145#comment-15032145 ] Piotr Jastrzebski edited comment on CASSANDRA-9991 at 11/30/15 5:39 PM: Sorry - I missed the comment about the swap. I fixed all three things. Please have another look. Thanks was (Author: haaawk): Sorry - I missed the comment about the swap. I fixed both things. Please have another look. Thanks > 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)
[jira] [Updated] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Piotr Jastrzebski updated CASSANDRA-9991: - Attachment: trunk-9991-v5.txt Sorry - I missed the comment about the swap. I fixed both things. Please have another look. Thanks > 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)
[jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15030553#comment-15030553 ] Piotr Jastrzebski commented on CASSANDRA-9991: -- I made the code more efficient. 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-v3.txt, trunk-9991-v4.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)
[jira] [Updated] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Piotr Jastrzebski updated CASSANDRA-9991: - Attachment: trunk-9991-v4.txt > 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.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)
[jira] [Updated] (CASSANDRA-9988) Introduce leaf-only iterator
[ https://issues.apache.org/jira/browse/CASSANDRA-9988?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Piotr Jastrzebski updated CASSANDRA-9988: - Attachment: trunk-9988.txt > Introduce leaf-only iterator > > > Key: CASSANDRA-9988 > URL: https://issues.apache.org/jira/browse/CASSANDRA-9988 > Project: Cassandra > Issue Type: Sub-task >Reporter: Benedict >Priority: Minor > Labels: patch > Fix For: 3.x > > Attachments: trunk-9988.txt > > > In many cases we have small btrees, small enough to fit in a single leaf > page. In this case it _may_ be more efficient to specialise our iterator. -- This message was sent by Atlassian JIRA (v6.3.4#6332)
[jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15028899#comment-15028899 ] Piotr Jastrzebski commented on CASSANDRA-9991: -- Ok thanks. I will try to make it more efficient. > 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.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)
[jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15028688#comment-15028688 ] Piotr Jastrzebski commented on CASSANDRA-9991: -- We can. It's just gonna make removeFromLeaf even more complex. I thought you wanted to simplify the code? Aren't index operation on btree cheap? > 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.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)
[jira] [Updated] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Piotr Jastrzebski updated CASSANDRA-9991: - Attachment: trunk-9991-v3.txt > 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.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)
[jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15027756#comment-15027756 ] Piotr Jastrzebski commented on CASSANDRA-9991: -- I added the test, fixed the isWellFormed and used index BTree operations to avoid Comparator.compare calls. Please have another look. Thanks > 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)
[jira] [Updated] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Piotr Jastrzebski updated CASSANDRA-9991: - Attachment: trunk-9991.txt-v2 > 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)
[jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
[
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 Object[] remove(final Object[] btree, final Comparator 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)
[jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15021008#comment-15021008 ] Piotr Jastrzebski commented on CASSANDRA-9991: -- Cheers. Next time I will run dtests as well and for any help I will go to irc. > 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)
[jira] [Commented] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15021006#comment-15021006 ] Piotr Jastrzebski commented on CASSANDRA-9991: -- That's great! Thank you very much Robert. I did run ant run and didn't find any regression in number of tests failing but I guess CI server probably does many more checks. Is there a way I could perform a check equivalent to CI on my laptop? > 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)
[jira] [Updated] (CASSANDRA-9991) Implement efficient btree removal
[ https://issues.apache.org/jira/browse/CASSANDRA-9991?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Piotr Jastrzebski updated CASSANDRA-9991: - Attachment: trunk-9991.txt > 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)
