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

Jordan West edited comment on CASSANDRA-15213 at 1/9/20 7:13 AM:
-----------------------------------------------------------------

Thanks for the clarification. I will take a stab at something to replace the 
usage of {{LongAdder[]}} along the lines of what you suggested and share when 
ready. I agree re: benchmarking and will try and come up with a more complete 
set -- clearly we used the existing benchmarks before without finding this 
issue. 

Regarding the binary search, I am still a bit confused. If you run: 
https://github.com/jrwest/cassandra/blob/jwest/15213/test/unit/org/apache/cassandra/metrics/DecayingEstimatedHistogramReservoirTest.java#L58
 you will see that the proposed estimation (using the code provided) would 
result in several cases where a linear search would lead to over 10-50 accesses 
(as value grows the approximation gets more inaccurate) and 
{{Arrays.binarySearch(offsets, value) <= fastLog12(value)}} always (even when 
correctly adjusting the return value of the binary search for negative values). 

Fwiw, the proposed fast log code does improve performance of my local 
modifications when benchmarked but basically brings it back inline w/ the 
existing implementation (caveat: benchmarking issues already mentioned). 


was (Author: jrwest):
Thanks for the clarification. I will take a stab at something to replace the 
usage of {{LongAdder[]}} along the lines of what you suggested and share when 
ready. I agree re: benchmarking and will try and come up with a more complete 
set -- clearly we used the existing benchmarks before without finding this 
issue. 

Regarding the binary search, I am still a bit confused. If you run: 
https://github.com/jrwest/cassandra/blob/jwest/15213/test/unit/org/apache/cassandra/metrics/DecayingEstimatedHistogramReservoirTest.java#L58
 you will see that the proposed estimation (using the code provided) would 
result in several cases where a linear search would lead to over 10-50 accesses 
(as value grows the approximation gets more inaccurate) and 
{{Arrays.binarySearch(offsets, value) <= fastLog12(value)}} always. 

Fwiw, the proposed fast log code does improve performance of my local 
modifications when benchmarked but basically brings it back inline w/ the 
existing implementation (caveat: benchmarking issues already mentioned). 

> DecayingEstimatedHistogramReservoir Inefficiencies
> --------------------------------------------------
>
>                 Key: CASSANDRA-15213
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-15213
>             Project: Cassandra
>          Issue Type: Bug
>          Components: Observability/Metrics
>            Reporter: Benedict Elliott Smith
>            Assignee: Jordan West
>            Priority: Normal
>             Fix For: 4.0-beta
>
>
> * {{LongAdder}} introduced to trunk consumes 9MiB of heap without user 
> schemas, and this will grow significantly under contention and user schemas 
> with many tables.  This is because {{LongAdder}} is a very heavy class 
> designed for single contended values.  
>  ** This can likely be improved significantly, without significant loss of 
> performance in the contended case, by simply increasing the size of our 
> primitive backing array and providing multiple buckets, with each thread 
> picking a bucket to increment, or simply multiple backing arrays.  Probably a 
> better way still to do this would be to introduce some competition detection 
> to the update, much like {{LongAdder}} utilises, that increases the number of 
> backing arrays under competition.
>  ** To save memory this approach could partition the space into chunks that 
> are likely to be updated together, so that we do not need to duplicate the 
> entire array under competition.
>  * Similarly, binary search is costly and a measurable cost as a share of the 
> new networking work (without filtering it was > 10% of the CPU used overall). 
>  We can compute an approximation floor(log2 n / log2 1.2) extremely cheaply, 
> to save the random memory access costs.



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

Reply via email to