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