Apologies for having this wave turn into a tsunami. CopyOnWriteArrayList was rewritten due to finding https://bugs.openjdk.java.net/browse/JDK-8169738 ArrayDeque and ArrayBlockingQueue now both use efficient nested loop idiom for all traversals. Most bulk remove methods in all collection classes were rewritten for efficiency, using similar code. Lots of tests and benchmarks added.
On Wed, Nov 16, 2016 at 3:34 PM, Paul Sandoz <paul.san...@oracle.com> wrote: > 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/ > >> > >> > >
