[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17015387#comment-17015387 ] Benedict Elliott Smith commented on CASSANDRA-15389: Great! A couple of really minor things: * I still see the Long.MIN_VALUE sentinel, maybe you forgot to push latest commit? * I don't think any caller of {{apply}} uses {{stopCondition}} anymore? * In both {{apply}} and {{accumulate}}: ** We could test {{<= childOffset}} to avoid the slightly confusing maths to calculate {{limit}} ** I have a very mild preference for keeping it to {{< childOffset}} and just repeating the child logic, particularly since it's only a single line in each case, as I find it makes it clearer we're visiting one more child, and it gives the branch predictor less to do (though there's a good chance the compiler will do it anyway, if we use {{<= childOffset}} in the guard) Otherwise looks ready to me > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17015237#comment-17015237 ] Blake Eggleston commented on CASSANDRA-15389: - Yes that's much better. I pulled in your commit, did the same with apply, split up apply, and removed the Long.MIN_VALUE stop sentinel > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17013314#comment-17013314 ] Benedict Elliott Smith commented on CASSANDRA-15389: Sure, it's probably easier to show, so take a look at [this branch|https://github.com/belliottsmith/cassandra/commits/15389-suggest]. It's late and my OCD got the better of me, so I also tweaked the method parameter order so that types of parameter are grouped together, separated by the recipient type, i.e. they go {{accumulator, accumulatorArg, Comparator, comparatorArg, initialValue}}. Debatably initialValue should go after {{accumulatorArg}}, but it felt right to be consistently at the end. Feel free to use/discard what you feel inclined towards. > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17013307#comment-17013307 ] Blake Eggleston commented on CASSANDRA-15389: - {quote}Looking at your implementation I realise it’s possible to simply define accept(Consumer c, V v) in terms of accept(BiConsumer c, V1 v1, V2 v2) by simply invoking accept(Consumer::accept, c, v), which should be more than clear enough. {quote} I don’t follow. Could you provide some more detail about what you’re thinking? > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17013294#comment-17013294 ] Benedict Elliott Smith commented on CASSANDRA-15389: very nice! If we change the order of parameter provision to the BiLongAccumulator, we can (if we want) do the same trick of just supplying {{accumulate(LongAccumulator::apply, accumulator, initialValue)}} to keep only one implementation without the extra (admittedly minor) obfuscation. I still need to double check the fine details of a couple of the methods, but I think we're pretty much close to done here. > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17013293#comment-17013293 ] Blake Eggleston commented on CASSANDRA-15389: - yep, forgot to commit it, it should be there now > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17013292#comment-17013292 ] Benedict Elliott Smith commented on CASSANDRA-15389: bq. Good idea about complex data accumulation in collect stats. I ended up adding and using BiLongAccumulator to make all cases garbage free. Sounds great! Though looking at the code currently posted, I think it’s still capturing a reference to the {{collector}}? I think you may have simply not posted your latest changes. bq. This seems like it makes sense, but everything may just be looking like a nail to me, so let me know if you have a better idea My personal view is it's absolutely fine to duplicate code somewhere like this, and I’ve done that in some patches I'll be posting soon. I think clarity for the reader is also valuable, and if the methods are maintained next to each other and clearly marked as copy/paste variants because we don't have a macro language, I think that's fine and probably preferable. However, I think in this case it's fine either way. Looking at your implementation I realise it’s possible to simply define {{accept(Consumer c, V v)}} in terms of {{accept(BiConsumer c, V1 v1, V2 v2)}} by simply invoking {{accept(Consumer::accept, c, v)}}, which should be more than clear enough. It’s a shame this is a recursive function so we won’t be able to benefit from inlining, and will probably incur an extra virtual invocation cost. It might be that we anyway win by splitting implementations, but it may not be worth overthinking. FWIW, I think it might be helpful to treat {{apply}} to the same restructure you’ve done to {{accumulate}} - which helped me a great deal in reading that. {{isStopSentinel}}: do we use {{Long.MIN_VALUE}} anymore? Should we also consider optionally permitting a stop sentinel to be provided, so we can make {{minDeletionTime}} more efficient? I don’t think we have anywhere that needs more than one stop sentinel anymore, so I think it’s probably an acceptable complication. nit: {{ComplexColumnData.accumulate}} should we call the parameter e.g. {{initialValue}} to distinguish it from those {{accumulate}} methods that take a value to start from in the tree? > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17013279#comment-17013279 ] Blake Eggleston commented on CASSANDRA-15389: - ok I think I’ve addressed everything here, a few notes: * I’ve added BiFunction / BiLongAccumulator support, making AbstractRow#digest and Rows#collectStats garbage free. Again, using the accessor pattern here to avoid duplicated code. This seems like it makes sense, but everything may just be looking like a nail to me, so let me know if you have a better idea. * In addition to removing the null check from hasInvalidDeletions, we now also stop accumulating as soon as we find an invalid deletion * Good idea about complex data accumulation in collect stats. I ended up adding and using BiLongAccumulator to make all cases garbage free. > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17010900#comment-17010900 ] Benedict Elliott Smith commented on CASSANDRA-15389: Thanks, the patch is looking really good. Just some minor suggestions to consider. AbstractRow * If we introduce a {{BiFunction}} variant of {{apply}}, in which we can supply the second argument, then we can go garbage-free for e.g. {{digest}} by calling {{apply(ColumnData::digest, hasher)}} BTreeRow * {{hasComplexDeletion}} does not need the {{if (isSimple)}} branch anymore, I think? * {{hasComplexDeletion}} seems to be testing the wrong sentinel return value from {{accumulate}}? * Does {{HAS_INVALID_DELETIONS}} need to test {{cd != null}}? Row * {{collectStats}} could delegate to a new {{ComplexColumnData.accumulate}}, and pass itself as the parameter (though we would need to test {{!(cd instanceof ComplexColumnData)}} instead of {{cd.column.isSimple()}} * This might mean we can remove the {{hasCells()}} test, as we will be garbage-free and can let {{accumulate}} make the right decision for us BTree * Having been playing with a lot of BTree methods recently, I personally find it aids clarity to have totally separate bits of code implementing behavior for leaves and branches, with a guard at-or-near the start of the method switching behaviour. It could invoke a {{methodLeaf}} variant, or do it inline, but I think it could make it somewhat easier to follow the logic in {{accumulate}}. It’s only a small amount of code to duplicate, but the reader doesn’t have to try and play out the switches while following the flow. * I also find that when iterating branches, it is most clear to simply do one key/child pair per loop, and a final (or initial) unrolled copy of a child visit. Again, a small amount of duplication but I think easier for a reader to digest (at least, I found this helped when reading my own methods). This _should_ also lead to fewer executed instructions, and perhaps better branch predictor behaviour (hard to say, many of them might be well predicted anyway). nits: * {{AbstractRow.validateData}} should probably use method reference for clarity, i.e. {{apply(ColumnData::validate)}} * {{BTreeRow.HAS_INVALID_DELETIONS}} can be declared using lambda syntax * {{BTreeRow}} unused imports * {{BTreeRow:345}} unused {{ALWAYS_TRUE}} * {{Row}} unused imports * {{Rows}} unused {{addColumn}} * {{UnfilteredSerializer}} unused import * {{SerializationHeader}} unused imports * {{BTree}} unused import > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16988352#comment-16988352 ] Blake Eggleston commented on CASSANDRA-15389: - Ok pushed up some changes removing reverse accumulation and using an optional 'start from' value. The reverse direction for BTree#apply was only being used for these 2 methods, so I've converted that to forwards only as well. This is definitely a net improvement for code clarity. > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16988124#comment-16988124 ] Blake Eggleston commented on CASSANDRA-15389: - {quote}I don’t want to belabour the point though {quote} No, I think these are good discussions to have, helps arrive at the best solution, not just the first to accomplish a goal. I'll play around with it a bit. > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16988103#comment-16988103 ] Benedict Elliott Smith commented on CASSANDRA-15389: {quote}Implementing slice (or findAndAccumulate) would avoid reverse iteration, but I don’t think that would make the api or implementation easier to understand. {quote} Yes, this is what I was proposing. I think it _might_ be easier to understand, though I haven’t tried to implement it for comparison. My reasoning goes like this: * I find it hard to reason about different directions of iteration ** I just do, and perhaps others do too? ** It’s easy to misread something like direction, so I prefer to use it only when it is explicitly relevant, rather than expedient ** Making sure we get two methods correct may be harder than getting one correct, even if that one is slightly more complicated. Particularly when reverse iteration is less commonly reasoned about. * Implementation details that are not implied by the method's definition can be confusing ** {{accumulate}} is logically commutative, so a direction of iteration is a surprising implementation detail, which can increase the cognitive load for a reader as they may need to puzzle out why ** This implementation detail might easily be missed, given assumptions about the contract, and the ease with which the parameter switch might be glossed over * I find that minimising the bleeding of logic between callers helps clarity ** The reverse iteration approach requires overloading the accumulated value with a sentinel that means “we’ve gone too far” as well as our result. We supply a lambda that’s invoked on this value, and may ask to terminate iteration. We finally have to mask out that sentinel when returning, which gives three different methods these sentinels are being passed around. ** With an upper/lower bound, we decide the total range to look at, i.e. all the ColumnData, and simply iterate over it - control flow is unidirectional With regards to the stop condition, we might want to implement something similar to terminate early, but I think it would be fine to supply a terminal value to the accumulate method - {{Long.MAX_VALUE}} would be fine for all other callers I think? - which would seem conceptually more straightforward to me, since it would not be leaking extraneous details like the iteration order into sentinel values that need to be unwrapped later. It would only be terminating the accumulation because we’ve saturated the output value. I also don’t think it should be particularly complicating to add range operation to the function, and I’m happy to give it a whirl if you like for comparison? I don’t want to belabour the point though, which I may have already done. I think this might be cleaner, but it’s not a given and certainly not something I would demand be changed. > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16988054#comment-16988054 ] Blake Eggleston commented on CASSANDRA-15389: - I can see how that applies to hasComplex, no problem. What I’m having trouble seeing is how this would apply to hasComplexDeletion. Given a set of ComplexColumnData instances, I don’t think there’s any ordering criteria we can use to search for complex deletion is there? That would prevent a direct adaptation of `firstComplexIdx` since it's just looking for the first index of something, and I don’t think we can avoid iteration. That would also preclude removing the stop condition since there’s no point continuing once we’ve found a complex deletion. Knowing the first complex index doesn’t help us without 1) implementing slice functionality in accumulate, 2) iterating through the complex cells with BTree#findByIndex, which would be much slower than just walking the tree. Implementing slice (or findAndAccumulate) would avoid reverse iteration, but I don’t think that would make the api or implementation easier to understand. > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16987402#comment-16987402 ] Benedict Elliott Smith commented on CASSANDRA-15389: Thanks. I'll try to find some time in the near future to undertake a full review. bq. BTreeRow I had a bug in my hasComplexDeletion re-implementation that made reverse iteration / stop condition seem unnecessary. We actually do need both for hasComplexDeletion to work properly. Otherwise we’d only detect complex deletion if it’s on the final complex column. So, I confess to not having looked closely enough to notice your bug, but (I think) nor to have been mislead by it. I may have been unclear in my suggestion, since it was very terse. The {{firstComplexIdx}} calculation is used in other places to avoid having to perform reverse iteration, since it gives the _lowest_ index in the btree in which any complex column data occurs. Since complex data sorts after simple, this gives the whole range of indices on which complex data occurss. We would need to implement a {{Row}}/{{ColumnData}} variant of the feature we have previously only used in {{Columns}}, but it should map directly, and might permit us to avoid implementing this extra functionality. Does that make sense, or am I still missing something? > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16987244#comment-16987244 ] Blake Eggleston commented on CASSANDRA-15389: - Just pushed up some changes addressing most of your comments. *Rows#collectStats:* the overflow checks aren't actually doing anything, since the longs are being shifted/masked to 32 bits. Force of habit when casing longs to ints :). Addressed the other comments *SerializationHeader:* fixed. Now using a single rewindable iterator, and added a check to LeafBTreeSearchIterator to check the current position before doing a binary search. *BTreeRow* I had a bug in my {{hasComplexDeletion}} re-implementation that made reverse iteration / stop condition seem unnecessary. We actually do need both for hasComplexDeletion to work properly. Otherwise we’d only detect complex deletion if it’s on the final complex column. > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16967627#comment-16967627 ] Benedict Elliott Smith commented on CASSANDRA-15389: Just collecting here some comments I made on GitHub: h3. Rows.collectStats * Could simply increment the long directly by 0x and 1, respectively, without unpacking * The saturation checks seem to be of limited value after the loop terminates, and should perhaps be done on each increment? It would throw if we had an overflow of 2B to 4B, but not 4B to 6B. Not sure how likely either of these things are. * The right-shift to extract should probably be unsigned (though unimportant if we haven't overflowed) h3. SerializationHeader Not sure if this would be an improvement or not, but {{FullBTreeSearchIterator}} has a rewind method, and this could be hoisted into {{SearchIterator}} to make it reusable. It's not clear if this would be faster than consulting a {{HashMap}}, particularly with the new {{LeafBTreeSearchIterator}} that uses {{binarySearch}} without any optimisation for the case where we are looking up the same set of values in sequence, however {{FullBTreeSearchIterator}} would have no indirect memory accesses for the common case of all (or most) columns being visited, and this could also be propagated to {{LeafBTreeSearchIterator}}. It would mean fewer indirect memory accesses. h3. BTreeRow * {{hasComplex}} doesn't need to use an iterator at all - we can simply search for the first complex cell using {{BTree.find}} and the {{Cell}} equivalent of {{Columns.findFirstComplexIdx}} - however it looks like this method isn't even used, so we could simply remove it entirely. * {{hasComplexDeletion}} could use the same logic to determine the {{firstComplexIdx}}, and instead of providing a {{StopCondition}} we could provide {{(firstComplexIdx, size)}} as the bounds to accumulate over. These two would remove the need for a direction to the accumulate function, and the {{StopCondition}}, which I think would be an easier to understand API (and easier to parse implementation). > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org
[jira] [Commented] (CASSANDRA-15389) Minimize BTree iterator allocations
[ https://issues.apache.org/jira/browse/CASSANDRA-15389?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16963914#comment-16963914 ] Benedict Elliott Smith commented on CASSANDRA-15389: I haven't fully reviewed this change, just wanted to say that I really like the shape of it. > Minimize BTree iterator allocations > --- > > Key: CASSANDRA-15389 > URL: https://issues.apache.org/jira/browse/CASSANDRA-15389 > Project: Cassandra > Issue Type: Sub-task > Components: Local/Compaction >Reporter: Blake Eggleston >Assignee: Blake Eggleston >Priority: Normal > Fix For: 4.0 > > > Allocations of BTree iterators contribute a lot amount of garbage to the > compaction and read paths. > This patch removes most btree iterator allocations on hot paths by: > • using Row#apply where appropriate on frequently called methods > (Row#digest, Row#validateData > • adding BTree accumulate method. Like the apply method, this method walks > the btree with a function that takes and returns a long argument, this > eliminates iterator allocations without adding helper object allocations > (BTreeRow#hasComplex, BTreeRow#hasInvalidDeletions, BTreeRow#dataSize, > BTreeRow#unsharedHeapSizeExcludingData, Rows#collectStats, > UnfilteredSerializer#serializedRowBodySize) as well as eliminating the > allocation of helper objects in places where apply was used previously^[1]^. > • Create map of columns in SerializationHeader, this lets us avoid > allocating a btree search iterator for each row we serialize. > These optimizations reduce garbage created during compaction by up to 13.5% > > [1] the memory test does measure memory allocated by lambdas capturing objects -- This message was sent by Atlassian Jira (v8.3.4#803005) - To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org For additional commands, e-mail: commits-h...@cassandra.apache.org