RFR: jsr166 jdk9 integration wave 12

Martin Buchholz martinrb at google.com
Tue Oct 18 18:00:33 UTC 2016

On Tue, Oct 18, 2016 at 10:15 AM, Stuart Marks <stuart.marks at oracle.com>

> On 10/17/16 6:34 PM, Martin Buchholz wrote:
>> Most of this is for Stuart - very collection-y.
>> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/jsr166-
>> jdk9-integration/
>> This includes a rewrite of ArrayDeque to bring it to parity with ArrayList
>> (except for List features).
>> The patch includes public methods ensureCapacity, trimToSize, replaceAll
>> as in
>> ArrayList, but we can defer making them public to a later change (or a
>> later
>> release), since new public methods are always controversial.  But I'd
>> really
>> like to get the performance/scalability changes in for jdk 9.
>> It also includes a redo of ArrayList#removeIf to make it more efficient
>> and
>> consistent with behavior of other implementations, including ArrayDeque.
>> The patches are a little tangled because they step on each other's toes.
>> File
>> CollectionTest is in "miscellaneous", but it tests both the ArrayDeque and
>> ArrayList changes.
> Hi Martin,
> ArrayList.removeIf() is nice. I like the way it recovers from the
> predicate having thrown an exception. I note that it uselessly copies the
> tail of the array to itself, if the predicate throws an exception and
> nothing has been deleted yet. You could add a r != w check, or possibly
> deleted > 0 if you prefer, or maybe we don't care because this is a rare
> (we hope) error recovery case.
I had the same thoughts... I added checks for deleted > 0

> ***
> I have some comments on ArrayDeque:
> * 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.

It was the horror of user discovering that ArrayDeque(2^n) allocated
2^(n+1) that persuaded me to go down this road.
It's also very useful to allocate exactly the requested size on
ArrayDeque(m) or be precise with trimToSize or allow growth up to (almost)
A circular buffer is a very simple data structure - our implementation
should be a model!

> (Potential future enhancement: allocate the array lazily, like ArrayList)
> Note, I haven't digested all the changes yet.
> * API additions
> I'm somewhat undecided about these.
> I've always felt that the ensureCapacity() and trimToSize() methods were a
> sop added to ArrayList aimed at people converting from Vector. The
> ArrayList.ensureCapacity() method seems to be used a lot, but probably not
> to great effect, since addAll() gives exact sizing anyway. The trimToSize()
> method could be useful in some cases, but should we hold out for a
> generalized one, as requested by JDK-4619094?

ensureCapacity is the least useful - just saving less than a factor of 2
allocation on growth.  trimToSize seems more important, since it saves
memory "permanently".

> On the other hand, ArrayDeque is modeling an array, so providing some size
> control seems mostly harmless.
> The replaceAll() method is a bit oddly placed here. It's a default method
> on List (which ArrayDeque doesn't, and can't implement) so it's a bit
> strange to have a special method here with the same name and semantics as
> the one on List, but with a "fork" of the specification.
yeah, it's adding a List method even though the mega-feature of List view
is deferred.

> Maybe if JDK-8143850 is implemented to give a list view of an ArrayDeque,
> the replaceAll() method could be implemented on that:
>     arrayDeque.asList().replaceAll(clazz::method);

yeah, the idea might be that we add List methods like get(i) and replaceAll
directly on ArrayDeque, but only when you call asList do you get something
that implements List ... which is ... odd.

> I'm not sure what to think of the arrangement of the tests. The "core"
> collections, that is, collections in java.util, exclusive of
> java.util.concurrent, are mostly tested by tests in jdk/test/java/util.
> This patch adds tests for ArrayList and ArrayDeque inside of
> jdk/test/java/util/concurrent/tck. There's a test group
> jdk_collections_core that's intended to test the core collections, so it'll
> miss the new tests being added here.
> I'm not sure what to suggest. The new tests use the JSR166TestCase
> framework, which is probably useful, and probably can't be used if the
> tests are moved elsewhere. I don't know what it would take to convert this
> to jtreg or testng. Or, the core test group could be modified to run
> selected JSR166 test cases, which doesn't seem quite right either.
> Suggestions?
There's already a certain amount of mixing, e.g. stream tests sometimes
test j.u.c. and Queue tests sometimes test all the Queue implementations.
Unlike non-test code, some redundancy and divergence of testing frameworks
and styles is fine.  I still haven't found a way of writing shared tests
for implementations of an interface that I really like.

> ***
> I haven't looked at the other j.u.c changes. I haven't done so
> historically, but I can if you need a reviewer.

Look at CollectionTest in misc .

More information about the core-libs-dev mailing list