default random access list spliterator

[Michael Hixson]

Hi Tagir, Paul,

Ah, it looks like Donald Raab had exactly the same suggestion.  Sorry
for the repeat.  I was following that list at that time, and now I'm
wondering whether my idea was my own.  I agree with everything he
said.

> One problem which would arise is that such spliterator will not be able to properly track modCount and throw ConcurrentModificationException.

Putting this in AbstractList instead of List sounds fine. I bet you
could detect *more* co-mod cases and still improve performance, given
that the current implementation dumps half of the elements into
Spliterators.ArraySpliterator, which knows nothing about
modifications.

> But, perhaps we underestimated the integration with existing libraries?
(from the previous thread)
> The efficacy question is: what List implementations implement RA that  don't already have their own specialized spliterator?

Spliterator is pretty tough to implement.  AbstractList is easy.  I
bet most List *views* (as opposed to complete storage) will extend
AbstractList and provide get(int) and size(), and maybe a couple of
other methods, but not the full catalog.  That is my experience
anyway.

-Michael

On Mon, Mar 7, 2016 at 2:08 AM, Paul Sandoz <paul.sandoz at oracle.com> wrote:
> Hi Michael,
>
> It could, stay tuned for some possible action on this.
>
> This is something we did discuss a while ago [1]. At the time we thought most List implementations would override so did not bother, and admittedly with the frenzy of all other stuff got de-prioritized. But, perhaps we underestimated the integration with existing libraries?
>
> To do that we would need to adjust the specification of the default behaviour which would also adjust the fail-fast behaviour as Tagir points out (which may be a reasonable compromise in the case, it should be possible to detect certain co-mod cases)
>
> Paul.
>
> [1] http://mail.openjdk.java.net/pipermail/lambda-libs-spec-experts/2013-May/001770.html <http://mail.openjdk.java.net/pipermail/lambda-libs-spec-experts/2013-May/001770.html>
>
>> On 7 Mar 2016, at 10:02, Michael Hixson <michael.hixson at gmail.com> wrote:
>>
>> The default List.spliterator() is iterator-based.  Could this be
>> improved for random access lists, using List.get(int) to fetch
>> elements instead of List.iterator()?
>>
>> I think it could improve most on Spliterator.trySplit().  The current
>> implementation allocates a new array for split-off elements.  I see
>> almost twice the throughput from list.parallelStream().forEach(...)
>> with a custom get(int)-based implementation over the default one.
>>
>> For example, instead of this:
>>
>>    default Spliterator<E> spliterator() {
>>        return Spliterators.spliterator(this, Spliterator.ORDERED);
>>    }
>>
>> I'm suggesting something like this:
>>
>>    default Spliterator<E> spliterator() {
>>        return (this instanceof RandomAccess)
>>                ? Spliterators.randomAccessListSpliterator(this)
>>                : Spliterators.spliterator(this, Spliterator.ORDERED);
>>    }
>>
>> where randomAccessListSpliterator is new code that looks a lot like
>> Spliterators.ArraySpliterator.
>>
>> -Michael
>