> On 16 Nov 2016, at 16:03, Martin Buchholz <marti...@google.com> wrote:
>
> 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.
Ok, i will just go through all of it.
Collection-optimization
—
Perhaps consolidate the repeated mini bit set methods as package private static
methods on AbstractCollection? Unclear where the j.u.concurrent ones should go
though...
It’s purely a subjective thing but i would be inclined to change the variable
name “deathRow" to something more neutral such as “removedBitSet”.
The 2 layer nested loop is quite clever, certainly twists the mind when first
encountered. It’s arguably more readable if there are two separate,
(not-nested) loops, but that also requires two explicit invocations of the
action, which may perturb the performance characteristics.
ArrayDeque
—
188 public ArrayDeque(int numElements) {
189 elements = new Object[Math.max(1, numElements + 1)];
190 }
What if Integer.MAX_VALUE is passed?
202 public ArrayDeque(Collection<? extends E> c) {
203 elements = new Object[c.size() + 1];
204 addAll(c);
205 }
What if c.size() returns Integer.MAX_VALUE?
226 * Adds i and j, mod modulus.
227 * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
228 */
229 static final int add(int i, int j, int modulus) {
Is that upper bound correct for j? 0 <= j < modulus ?
317 c.forEach(e -> addLast(e));
this::addLast, up to you which you prefer
843 public boolean tryAdvance(Consumer<? super E> action) {
844 if (action == null)
845 throw new NullPointerException();
846 int t, i;
847 if ((t = fence) < 0) t = getFence();
Is that for optimisation purposes, since the same check is also performed in
getFence? If so that seems like overkill
848 if (t == (i = cursor))
849 return false;
850 final Object[] es;
851 action.accept(nonNullElementAt(es = elements, i));
852 cursor = inc(i, es.length);
Recommend updating cursor before the action
853 return true;
854 }
Collection8Test
—
429 public void testRemoveAfterForEachRemaining() {
Are tests run by default with testImplementationDetails == true? I am guessing
so.
Semaphore
—
633 /**
634 * Acquires and returns all permits that are immediately available.
635 * Upon return, zero permits are available.
636 *
637 * @return the number of permits acquired
638 */
639 public int drainPermits() {
640 return sync.drainPermits();
641 }
Arguably, if positive acquires all permits, otherwise releases all permits.
Perhaps:
Acquires and returns all permits that are immediately available, otherwise
releases all permits (if negative).
Upton return, zero permits are available.
@return the number of permits acquired, or the number of permits release (a
negative value)
Probably requires a CCC which i can manage.
SplittableRandom
—
533 /**
534 * Generates a pseudorandom number with the indicated number of
535 * low-order bits. Because this class has no subclasses, this
536 * method cannot be invoked or overridden.
537 *
538 * @param bits random bits
539 * @return the next pseudorandom value from this random number
540 * generator's sequence
541 */
542 protected int next(int bits) {
543 return nextInt() >>> (32 - bits);
544 }
545
Unless i am missing something really subtle, I don’t think this is required
since SplittableRandom does not extend from Random (unlike in
ThreadLocalRandom), and no associated reflective test is required.
ForkJoin
—
69 * tasks that are never joined. All worker threads are initialized
70 * with {@link Thread#isDaemon} set {@code true}.
CCC?
Thanks,
Paul.
>
>
> 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/
> >>
> >>
>
>
