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 <marti...@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 <marti...@google.com> > wrote: > >> >> >> On Tue, Oct 18, 2016 at 4:18 PM, Martin Buchholz <marti...@google.com> >> wrote: >> >>> >>> >>> On Tue, Oct 18, 2016 at 4:00 PM, Vitaly Davidovich <vita...@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/ >> >>
