RFR: jsr166 jdk9 integration wave 12

[Paul Sandoz]

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/
>> 
>>