On 10/17/16 6:34 PM, Martin Buchholz wrote:
Most of this is for Stuart - very collection-y.


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

(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?

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.

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



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?


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.


Reply via email to