RFR: 8196106: Support nested infinite or recursive flat mapped streams [v2]

[Viktor Klang]

On Tue, 9 Apr 2024 10:04:44 GMT, Viktor Klang <vklang at openjdk.org> wrote:

>> This PR implements Gatherer-inspired encoding of `flatMap` that shows that it is both competitive performance-wise as well as improve correctness.
>> 
>> Below is the performance of `Stream::flatMap` (for reference types):
>> 
>> Before this PR:
>> 
>> 
>> Benchmark            (size)   Mode  Cnt        Score       Error  Units
>> FlatMap.par_array        10  thrpt   12   294008,937 ? 54369,110  ops/s
>> FlatMap.par_array       100  thrpt   12    62411,229 ? 14868,119  ops/s
>> FlatMap.par_array      1000  thrpt   12     8263,821 ?   452,622  ops/s
>> FlatMap.par_iterate      10  thrpt   12    23029,978 ?  4274,449  ops/s
>> FlatMap.par_iterate     100  thrpt   12    10532,907 ?   321,694  ops/s
>> FlatMap.par_iterate    1000  thrpt   12      981,571 ?   135,270  ops/s
>> FlatMap.seq_array        10  thrpt   12  2955648,495 ? 32539,142  ops/s
>> FlatMap.seq_array       100  thrpt   12    41851,009 ?   377,546  ops/s
>> FlatMap.seq_array      1000  thrpt   12     1740,281 ?  1229,974  ops/s
>> FlatMap.seq_iterate      10  thrpt   12   321727,690 ?  5149,356  ops/s
>> FlatMap.seq_iterate     100  thrpt   12     8437,198 ?    56,635  ops/s
>> FlatMap.seq_iterate    1000  thrpt   12       76,994 ?     0,965  ops/s
>> 
>> 
>> After this PR:
>> 
>> 
>> Benchmark            (size)   Mode  Cnt        Score        Error  Units
>> FlatMap.par_array        10  thrpt   12   283350,051 ?  35567,223  ops/s
>> FlatMap.par_array       100  thrpt   12    53846,906 ?  19241,913  ops/s
>> FlatMap.par_array      1000  thrpt   12     8230,909 ?    156,362  ops/s
>> FlatMap.par_iterate      10  thrpt   12    26328,500 ?   5411,401  ops/s
>> FlatMap.par_iterate     100  thrpt   12    10470,862 ?    249,991  ops/s
>> FlatMap.par_iterate    1000  thrpt   12      986,511 ?    224,050  ops/s
>> FlatMap.seq_array        10  thrpt   12  5654826,565 ?  27317,453  ops/s
>> FlatMap.seq_array       100  thrpt   12   187929,786 ?    542,787  ops/s
>> FlatMap.seq_array      1000  thrpt   12     2385,346 ?      9,827  ops/s
>> FlatMap.seq_iterate      10  thrpt   12   812722,403 ? 160500,399  ops/s
>> FlatMap.seq_iterate     100  thrpt   12    13542,472 ?    118,769  ops/s
>> FlatMap.seq_iterate    1000  thrpt   12      157,056 ?      1,814  ops/s
>
> Viktor Klang has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Updating copyright year

src/java.base/share/classes/java/util/stream/DoublePipeline.java line 268:

> 266:                 class FlatMap implements Sink.OfDouble, DoublePredicate {
> 267:                     boolean cancel;
> 268:                     private final boolean shorts = isShortCircuitingPipeline();

If there's a known, short-circuiting, operation in the pipeline, we have to use `allMatch` but in the case where we know that there's nothing which could short-circuit we can go down a fast-path to `forEach`.

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/18625#discussion_r1557369039