RFR: 8196106: Support nested infinite or recursive flat mapped streams

[Viktor Klang]

On Thu, 4 Apr 2024 12:18:07 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

@PaulSandoz @AlanBateman I've added a commit to this PR which removes the use of Gatherer for Stream::flatMap, but instead implements flatMap for all of the pipelines using the same encoding which Gatherer would use. It seems very competitive performance-wise, and resolves at least one open JBS-issue with flatMap (will look to see if it resolves more than that)

src/java.base/share/classes/java/util/stream/AbstractPipeline.java line 436:

> 434:      }
> 435: 
> 436:     /**

Note to self, update Copyright year to 2024

src/java.base/share/classes/java/util/stream/GathererOp.java line 30:

> 28: 
> 29: import java.lang.invoke.MethodHandles;
> 30: import java.lang.invoke.VarHandle;

Note to self, update copyright year

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

PR Comment: https://git.openjdk.org/jdk/pull/18625#issuecomment-2042381405
PR Review Comment: https://git.openjdk.org/jdk/pull/18625#discussion_r1557358718
PR Review Comment: https://git.openjdk.org/jdk/pull/18625#discussion_r1557359258