Performance of default Spliterators

[Raab, Donald [Tech]]

Here are some performance tests I was trying out tonight with GSC.  The results here are for filtering a list of size 1 million 3 times with different predicates on a 2 core Windows machine.  The tests here were warmed up 100 times then executed 200 times so a human doesn't mind waiting.  The result of the tests for JDK-Parallel were significantly different enough for me to notice so I started digging into the implementation details a bit.

FastList is our mutable RandomAccess List which is getting the IteratorSpliterator for JDK-Parallel.

**JDK-Serial Filter: FastList size: 1,000,000 Count: 200 Total(ms): 17,735 Avg(ms): 88.679
GSC-Serial** Select: FastList size: 1,000,000 Count: 200 Total(ms): 12,754 Avg(ms): 63.771

JDK-Parallel Filter: FastList size: 1,000,000 Count: 200 Total(ms): 23,415 Avg(ms): 117.076
GSC-Parallel Select: FastList size: 1,000,000 Count: 200 Total(ms): 7,121 Avg(ms): 35.607
GSC-ForkJoin Select: FastList size: 1,000,000 Count: 200 Total(ms): 6,524 Avg(ms): 32.62

Compared to java.util.ArrayList which had a much better JDK-Parallel result because of the specialized override.

**JDK-Serial Filter: ArrayList size: 1,000,000 Count: 200 Total(ms): 14,019 Avg(ms): 70.097
GSC-Serial** Select: ArrayList size: 1,000,000 Count: 200 Total(ms): 12,398 Avg(ms): 61.99

JDK-Parallel Filter: ArrayList size: 1,000,000 Count: 200 Total(ms): 7,591 Avg(ms): 37.959
GSC-ForkJoin Select: ArrayList size: 1,000,000 Count: 200 Total(ms): 6,612 Avg(ms): 33.064
GSC-Parallel Select: ArrayList size: 1,000,000 Count: 200 Total(ms): 6,638 Avg(ms): 33.195

> -----Original Message-----
> From: Brian Goetz [mailto:brian.goetz at oracle.com]
> Sent: Friday, May 10, 2013 1:54 AM
> To: Raab, Donald [Tech]
> Cc: lambda-libs-spec-experts at openjdk.java.net
> Subject: Re: Performance of default Spliterators
> 
> Entirely reasonable.  Actually, might not even need much implementing.
> You could do:
> 
>    return IntStream.range(0, size()).map(List::get);
> 
> (if you could tolerate the early binding to size.)
> 
> The efficacy question is: what List implementations implement RA that
> don't already have their own specialized spliterator?
> 
> On 5/9/2013 7:53 PM, Raab, Donald [Tech] wrote:
> > Apologies if this was already discussed, thought about, planned or in
> > progress.
> > Right now in the build I am using (about a week old) spliterator
> > returns the following:
> >      default Spliterator<E> spliterator() {
> >          return Spliterators.spliterator(this, Spliterator.ORDERED);
> >      }
> > For ArrayList this is overridden to return an ArrayListSpliterator.
> I
> > think there should be an instance of check in spliterator to check
> for
> > RandomAccess so performance is better for other RandomAccess lists
> > that might be implemented in other libraries. So the following code
> > would need to be changed from this:
> >      public static <T> Spliterator<T> spliterator(Collection<?
> extends T> c,
> >                                                   int
> > additionalCharacteristics) {
> >          return new IteratorSpliterator<>(Objects.requireNonNull(c),
> >                                           additionalCharacteristics);
> >      }
> > To this:
> >      public static <T> Spliterator<T> spliterator(Collection<?
> extends T> c,
> >                                                   int
> > additionalCharacteristics) {
> >          if (c instanceof RandomAccess)
> >          return new RandomAccessSpliterator<>(c,
> additionalCharacteristics);
> >          return new IteratorSpliterator<>(Objects.requireNonNull(c),
> >                                           additionalCharacteristics);
> >      }
> > RandomAccessSpliterator would of course need to be implemented.
> > Thoughts?  Make sense?  Already planned?