On Tuesday, October 18, 2016, Martin Buchholz <marti...@google.com> wrote:
> On Tue, Oct 18, 2016 at 10:15 AM, Stuart Marks <stuart.ma...@oracle.com > <javascript:;>> > wrote: > > > > > > > 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. But it does add some new branches, doesn't it? Potentially branches that aren't taken prior to JIT compilation, but taken later = deopt. Curious if you ran some benchmarks on ArrayDeque. Also, some odd stylistic things, such as: while (s == (capacity = (elements = this.elements).length)) Is this an attempt to help the JIT or something? > 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) > Integer.MAX_VALUE. > 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 . > -- Sent from my phone
