RFR: 8154387 - Parallel unordered Stream.limit() tries to collect 128 elements even if limit is less

[Paul Sandoz]

Hi Tagir,

> On 16 Apr 2016, at 15:05, Tagir F. Valeev <amaembo at gmail.com> wrote:
> 
> Hello!
> 
> Please review and sponsor the following patch:
> https://bugs.openjdk.java.net/browse/JDK-8154387

Thanks for looking at this, it’s something i intended to get around to but never found the time. I closed JDK-8072841 as a dup of this.


> http://cr.openjdk.java.net/~tvaleev/webrev/8154387/r1/
> 

 913         UnorderedSliceSpliterator(T_SPLITR s, long skip, long limit) {
 914             this.s = s;
 915             this.unlimited = limit < 0;
 916             this.skipThreshold = limit >= 0 ? limit : 0;
 917             this.chunkSize = limit >= 0 ? (int)Math.min(CHUNK_SIZE,
 918                 (skip + limit) / ForkJoinPool.getCommonPoolParallelism() + 1) : CHUNK_SIZE;
 919             this.permits = new AtomicLong(limit >= 0 ? skip + limit : skip);
 920         }
 921

Note the common pool parallelism can never be 0. I dunno if you added 1 for that or another reason.

Did you consider:

  (skip + limit) / AbstractTask.LEAF_TARGET

?

What if chunkSize is zero? should it be a minimum of 1?

Testing wise i think our existing tests cover things ok.

Performance-wise looks good. Probable primes are my favourite way of easily increasing Q (cost per op) :-)

Can you run the stream tests and the perf tests with parallelism disabled:

  -Djava.util.concurrent.ForkJoinPool.common.parallelism=1

?

Thanks,
Paul.


> The rationale is to speed-up the parallel processing for unordered
> streams with low limit value. Such problems occur when you want to
> perform expensive filtering and select at most x elements which pass
> the filter (order does not matter). Currently unordered limit
> operation buffers up to 128 elements for each parallel task before it
> checks whether limit is reached. This is actually harmful when
> requested limit is lower: much more elements are requested from the
> upstream than necessary. Here's simple JMH test which illustrates the
> problem:
> 
> http://cr.openjdk.java.net/~tvaleev/webrev/8154387/jmh/
> It extracts the requested number of probable-primes from the list of
> 10000 BigInteger numbers. The results with 9ea+111:
> 
> Benchmark                    (limit)  Mode  Cnt      Score      Error  Units
> LimitTest.parLimit                 2  avgt   30    108,971 ±    0,643  us/op
> LimitTest.parLimit                20  avgt   30    934,176 ±   14,003  us/op
> LimitTest.parLimit               200  avgt   30   8772,417 ±  190,609  us/op
> LimitTest.parLimit              2000  avgt   30  41775,463 ± 1800,537  us/op
> LimitTest.parUnorderedLimit        2  avgt   30   2557,798 ±   13,161  us/op
> LimitTest.parUnorderedLimit       20  avgt   30   2578,283 ±   23,547  us/op
> LimitTest.parUnorderedLimit      200  avgt   30   4577,318 ±   40,793  us/op
> LimitTest.parUnorderedLimit     2000  avgt   30  12279,346 ±  523,823  us/op
> LimitTest.seqLimit                 2  avgt   30     34,831 ±    0,190  us/op
> LimitTest.seqLimit                20  avgt   30    369,729 ±    1,427  us/op
> LimitTest.seqLimit               200  avgt   30   3690,544 ±   13,907  us/op
> LimitTest.seqLimit              2000  avgt   30  36681,637 ±  156,538  us/op
> 
> When the limit is 2 or 20, parallel unordered version is slower than
> parallel ordered! Even for limit = 200 it's still slower than
> sequential operation.
> 
> The idea of the patch is to tweak the CHUNK_SIZE using the given limit and
> parallelism level. I used the following formula:
> 
> this.chunkSize = limit >= 0 ? (int)Math.min(CHUNK_SIZE,
>     (skip + limit) / ForkJoinPool.getCommonPoolParallelism() + 1) : CHUNK_SIZE;
> 
> This does not affect cases when limit is big or not set at all (in
> skip mode). However it greatly improves cases when limit is small:
> 
> Benchmark                    (limit)  Mode  Cnt      Score      Error  Units
> LimitTest.parLimit                 2  avgt   30    109,502 ±    0,750  us/op
> LimitTest.parLimit                20  avgt   30    954,716 ±   39,276  us/op
> LimitTest.parLimit               200  avgt   30   8706,226 ±  184,330  us/op
> LimitTest.parLimit              2000  avgt   30  42126,346 ± 3163,444  us/op
> LimitTest.parUnorderedLimit        2  avgt   30     39,303 ±    0,177  us/op !!!
> LimitTest.parUnorderedLimit       20  avgt   30    266,107 ±    0,492  us/op !!!
> LimitTest.parUnorderedLimit      200  avgt   30   2547,177 ±   58,538  us/op !!!
> LimitTest.parUnorderedLimit     2000  avgt   30  12216,402 ±  430,574  us/op
> LimitTest.seqLimit                 2  avgt   30     34,993 ±    0,704  us/op
> LimitTest.seqLimit                20  avgt   30    369,497 ±    1,754  us/op
> LimitTest.seqLimit               200  avgt   30   3716,059 ±   61,054  us/op
> LimitTest.seqLimit              2000  avgt   30  36814,356 ±  161,531  us/op
> 
> Here you can see that unordered cases are significantly improved. Now
> they are always faster than parallel ordered and faster than
> sequential for limit >= 20.
> 
> I did not think up how to test this patch as it does not change
> visible behavior, only speed. However all the existing tests pass.
> 
> What do you think?
> 
> With best regards,
> Tagir Valeev.
>