RFR: jsr166 jdk9 integration wave 12 (original) (raw)

Paul Sandoz paul.sandoz at oracle.com
Wed Nov 16 23:34:07 UTC 2016

Hi Martin,

Glad you looked more closely at the perf aspects of ArrayDeque.

I am struggling to determine what has changed since the last revision. Apart from ArrayDeque what files should i be looking at?

Thanks, Paul.

On 16 Nov 2016, at 12:14, Martin Buchholz <martinrb at google.com> wrote:

Thanks to Vitaly and Doug for being more concerned about offer/poll performance than I was initially. ArrayDeque is now back to using the head + tail + spare slot strategy, which keeps optimal performance for non-bulk operations, while everything else gets faster. We have new tests and new benchmarks, as a result of which new bugs were found and fixed, and this integration wave has grown rather larger than originally intended. The JIT-friendly nested loop strategy was successful for making bulk operations on circular arrays faster, and this is used for both ArrayDeque and ArrayBlockingQueue. + /* + * VMs excel at optimizing simple array loops where indices are + * incrementing or decrementing over a valid slice, e.g. + * + * for (int i = start; i < end; i++) ... elements[i] + * + * Because in a circular array, elements are in general stored in + * two disjoint such slices, we help the VM by writing unusual + * nested loops for all traversals over the elements. + */

Bulk removal operations on array-based collections retreat to a two-pass algorithm, which is slightly slower (but still O(n)), but continues to support (questionable) predicates that reentrantly access the collection in read mode. http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-jdk9-integration/ On Fri, Oct 21, 2016 at 12:32 PM, Martin Buchholz <martinrb at google.com> wrote:

On Tue, Oct 18, 2016 at 4:18 PM, Martin Buchholz <martinrb at google.com> wrote:

On Tue, Oct 18, 2016 at 4:00 PM, Vitaly Davidovich <vitalyd at gmail.com> wrote:

* Change in allocation/capacity policy. The removal of the power-of-two restriction, and applying a 1.5x growth factor (same as ArrayList) seems sensible. Does this mean that the ability to compute the proper array index by using x & (length-1) wasn't worth it? Or at least not worth the extra tail wastage?

There's no integer division to optimize, as with hash tables. But it does add some new branches, doesn't it? Potentially branches that aren't taken prior to JIT compilation, but taken later = deopt. If it's a smidgeon slower, I don't care that much; improvement in flexibility and scalability are more important. Of course, I do care about algorithmic improvements to e.g. removeIf Curious if you ran some benchmarks on ArrayDeque. Not yet. Who would like to show how slow the code is? I revived my ancient IteratorMicroBenchmark for the latest webrev, made it a proper jtreg test, added ArrayDeque Jobs, and verified that the new code is measurably faster than the old code, at least for the mundane job of iterating. http://cr.openjdk.java.net/~martin/webrevs/openjdk9/ jsr166-jdk9-integration/ArrayList/

More information about the core-libs-dev mailing list