[ https://issues.apache.org/jira/browse/CASSANDRA-15213?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17016070#comment-17016070 ]
Benedict Elliott Smith commented on CASSANDRA-15213: ---------------------------------------------------- Also fwiw, it looks like the primes 17 and 19 are sufficient, so we can literally just try either of those. Proof: {code} int[] primes = new int[] { 17, 19 }; BitSet sizeWithoutConflict = new BitSet(); for (int prime : primes) { for (int size = 1 ; size < 238 ; ++size) { BitSet conflict = new BitSet(); boolean hasConflict = false; for (int i = 0 ; i < size ; ++i) { if (conflict.get((i * prime) % size)) hasConflict = true; conflict.set((i * prime) % size); } if (!hasConflict) sizeWithoutConflict.set(size); } } for (int size = 1 ; size < 238 ; ++size) { if (!sizeWithoutConflict.get(size)) System.out.println(size); } {code} > 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