Hi Hiroshi, I created an issue and made some edits:
http://cr.openjdk.java.net/~psandoz/jdk9/JDK-8158365-list-spliterator-rnd-access/webrev/ Let me know what you think. Specification-wise we need to describe how the default implementation should behave without diving into specific implementation details. It now becomes clearer that these issues introduce behavioural changes: 1) A List implementing RandomAccess but not extending from AbstractList may result in different fail-fast behaviour; and 2) A List implementing RandomAccess may be operated on concurrently via List.get when it is the source of a stream pipeline executed in parallel. I think 1) is ok. 2) is obviously the primary motivation for this change, but it could potentially affect third-party List implementations whose indexed-accessor performs side-effects. That seems a questionable thing to do for something that implements RandomAccess, but there is a lot of odd code out there. Sorry, i should have raised this point earlier. On reflection i think your case trumps that of such odd code. Thoughts? Thanks, Paul. > On 31 May 2016, at 05:36, Ito, Hiroshi <hiroshi....@gs.com> wrote: > > Hi Paul, > > Thank you very much for your feedback, and apologize for the delay in > response.. > > I have incorporated your comments in the attached patch. Please kindly take a > look and let me know if you have further feedback. > > - Modified @implSpec to add a description in case the list implements > RandomAccess. > - Added modification checking in RandomAccessSpliterator, only when the list > implements AbstractList. > > Sorry for the confusion about SubList. It was all about the concurrent > modification checking, so adding the change above pretty much addressed my > issue earlier. > > Thanks, > Hiroshi > > -----Original Message----- > From: Paul Sandoz [mailto:paul.san...@oracle.com] > Sent: Thursday, May 12, 2016 8:46 PM > To: Ito, Hiroshi [Tech] > Cc: core-libs-dev@openjdk.java.net; Chan, Sunny [Tech]; Raab, Donald [Tech] > Subject: Re: RFR: Implement RandomAccess spliterator > > Hi Hiroshi, > > This is a good example of what seems like a small feature and yet there are > some unexpected complexities :-) > > > We will need to refine the implementation specification of List.spliterator, > which currently states: > > * @implSpec > * The default implementation creates a > * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator > * from the list's {@code Iterator}. The spliterator inherits the > * <em>fail-fast</em> properties of the list's iterator. > > > Since the existing implementation is derived from the iterator: > > @Override > default Spliterator<E> spliterator() { > return Spliterators.spliterator(this, Spliterator.ORDERED); > } > > concurrent modification checking will occur. The RandomAccessSpliterator > should also support modification checking, which i think requires it be an > inner class to check co-mod state. > > > I am struggling to understand the points you make about the spliterator of a > sub-list of a Vector being required to be an iterator-based implementation. > Since AbstractList.SubList can access a Vector's elements through > List.get/set why cannot RandomAccessSpliterator? > > If we want to support random access spliterators on sub-lists i think we > would anyway need to override the spliterator method to check for concurrent > modification (as is the case of the iterator method). > > Paul. > >> On 11 May 2016, at 11:25, Ito, Hiroshi <hiroshi....@gs.com> wrote: >> >> Hi, >> >> Please kindly review the attached patch for RandomAccessSpliterator >> implementation. >> >> Currently default implementation of spliterator is an IteratorSpliterator >> which is not optimal for RandomAccess data structures (besides ArrayList and >> Vector). This patch is to provide a default RandomAccessSpliterator >> implementation for RandomAccess data structure. >> >> The figures below demonstrate the performance difference before and after >> the change. Note the significant performance improvement in test >> SelectTest.parallel_lazy_streams_gsc (parallel streams performance test for >> non-JDK Lists that implement RandomAccess but don't yet implement their own >> spliterators). >> >> Benchmark code: >> https://github.com/goldmansachs/gs-collections/blob/master/jmh-tests/src/main/java/com/gs/collections/impl/jmh/SelectTest.java >> >> With IteratorSpliterator as default: >> >> Benchmark Mode Cnt Score Error Units >> SelectTest.parallel_lazy_jdk thrpt 20 172.671 ± 14.231 ops/s >> SelectTest.parallel_lazy_streams_gsc thrpt 20 20.662 ± 0.493 ops/s >> SelectTest.serial_lazy_jdk thrpt 20 89.384 ± 4.431 ops/s >> SelectTest.serial_lazy_streams_gsc thrpt 20 80.831 ± 7.875 ops/s >> >> With RandomAccessSpliterator as default: >> >> Benchmark Mode Cnt Score Error Units >> SelectTest.parallel_lazy_jdk thrpt 20 174.190 ± 16.870 ops/s >> SelectTest.parallel_lazy_streams_gsc thrpt 20 180.740 ± 9.594 ops/s >> SelectTest.serial_lazy_jdk thrpt 20 85.719 ± 2.414 ops/s >> SelectTest.serial_lazy_streams_gsc thrpt 20 78.760 ± 1.029 ops/s >> >> Majority of the patch is contributed by Paul Sandoz and he should be >> credited in the Contributed-by field. >> >> Along with this patch submission, we have a question for SubList spliterator >> implementation that we retained old behavior for now (i.e. return >> IteratorSpliterator, refer to RandomAccessSubList#spliterator()). We have >> found that Vector's subList is wrapped by RandomAccessSubList, that is >> RandomAccess but not a Vector anymore, and it expects to use >> IteratorSpliterator. We were not sure what's the best approach to >> distinguish Vector from other RandomAccess data structure within >> RandomAccessSublist, so we kept it return IteratorSpliterator for now. >> >> One approach could be to introduce VectorSubList that returns >> IteratorSpliterator (or an implementation similar to VectorSpliterator?). >> Then we could revert the spliterator() override in RandomAccessSublist. >> >> What would be your suggestion to handle this? >> >> Depending on your suggestion, we might fix the subList spliterator in this >> patch, or submit a separate patch if the amount of the change is significant. >> >> Thanks, >> Hiroshi >> <RandomAccessSpliterator.patch.txt> > > <RandomAccessSpliterator_0531.patch.txt>
