Gatherer: spliterator characteristics are not propagated
forax at univ-mlv.fr
forax at univ-mlv.fr
Mon Jan 29 11:23:36 UTC 2024
> From: "Viktor Klang" <viktor.klang at oracle.com>
> To: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>, "Paul Sandoz"
> <psandoz at openjdk.java.net>
> Sent: Monday, January 29, 2024 11:07:02 AM
> Subject: Re: Gatherer: spliterator characteristics are not propagated
> If you have a look at my benchmarks, currently I only fuse gather(…) +
> collect(…) (so in this case not allMatch).
You also fuse repetitive calls to gather()
[ https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/stream/GathererOp.java#L64 | https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/stream/GathererOp.java#L64 ]
> Cheers,
> √
Rémi
> Viktor Klang
> Software Architect, Java Platform Group
> Oracle
> From: forax at univ-mlv.fr <forax at univ-mlv.fr>
> Sent: Monday, 29 January 2024 10:42
> To: Viktor Klang <viktor.klang at oracle.com>
> Cc: core-libs-dev <core-libs-dev at openjdk.java.net>; Paul Sandoz
> <psandoz at openjdk.java.net>
> Subject: [External] : Re: Gatherer: spliterator characteristics are not
> propagated
>> From: "Viktor Klang" <viktor.klang at oracle.com>
>> To: "Remi Forax" <forax at univ-mlv.fr>
>> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>, "Paul Sandoz"
>> <psandoz at openjdk.java.net>
>> Sent: Monday, January 29, 2024 8:41:21 AM
>> Subject: Re: Gatherer: spliterator characteristics are not propagated
>> For monomorphic benches it is likely not going to make any difference as the JIT
>> will likely do the same thing, also, the bench might be dominated by other
>> factors.
> For me, it's more that lambdas may be able to use late-inlining (inlining after
> the return value of an invokedynamic is known as constant) so results may be
> better than it should.
> Here is an example,
> @Benchmark
> public boolean map_allMatch_repeat_3 () {
> return integers .stream()
> .map( v -> v + 1 )
> .map( v -> v + 2 )
> .map( v -> v + 3 )
> .allMatch( v -> v < 1_000_000 );
> }
> @Benchmark
> public boolean mapToInt_allMatch_repeat_3 () {
> return integers .stream()
> .mapToInt( v -> v + 1 )
> .map( v -> v + 2 )
> .map( v -> v + 3 )
> .allMatch( v -> v < 1_000_000 );
> }
> @Benchmark
> public boolean gatherer_map_allMatch_repeat_3 () {
> // Gatherer with lambdas
> return integers .stream()
> .gather( map ( v -> v + 1 ))
> .gather( map ( v -> v + 2 ))
> .gather( map ( v -> v + 3 ))
> .allMatch( v -> v < 1_000_000 );
> }
> @Benchmark
> public boolean gatherer_mapsublcass_allMatch_repeat_3 () {
> // Gatherer as subclass
> return integers .stream()
> .gather( mapSubclass ( v -> v + 1 ))
> .gather( mapSubclass ( v -> v + 2 ))
> .gather( mapSubclass ( v -> v + 3 ))
> .allMatch( v -> v < 1_000_000 );
> }
> With 10 second warmups,
> Benchmark Mode Cnt Score
> Error Units
> MapGathererBenchmark.gatherer_map_allMatch_repeat_3 avgt 5 3359.336
> ± 137.314 us/op
> MapGathererBenchmark.gatherer_mapsublcass_allMatch_repeat_3 avgt 5 3755.388
> ± 50.858 us/op
> MapGathererBenchmark.mapToInt_allMatch_repeat_3 avgt 5 559.891
> ± 1.542 us/op
> MapGathererBenchmark.map_allMatch_repeat_3 avgt 5 1642.167
> ± 5.804 us/op
> Also, I wonder if fusing is not an anti-pattern for gatherers/streams, c2 take a
> loooong time to come with as code wich is not very fast.
>> Cheers,
>> √
> Rémi
>> Viktor Klang
>> Software Architect, Java Platform Group
>> Oracle
>> From: forax at univ-mlv.fr <forax at univ-mlv.fr>
>> Sent: Thursday, 25 January 2024 14:57
>> To: Viktor Klang <viktor.klang at oracle.com>
>> Cc: core-libs-dev <core-libs-dev at openjdk.java.net>; Paul Sandoz
>> <psandoz at openjdk.java.net>
>> Subject: [External] : Re: Gatherer: spliterator characteristics are not
>> propagated
>>> From: "Viktor Klang" <viktor.klang at oracle.com>
>>> To: "Remi Forax" <forax at univ-mlv.fr>
>>> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>, "Paul Sandoz"
>>> <psandoz at openjdk.java.net>
>>> Sent: Wednesday, January 24, 2024 2:45:15 PM
>>> Subject: Re: Gatherer: spliterator characteristics are not propagated
>>> As a (related) side-note, the ability to implement the interface directly has a
>>> significant benefit to being able to have tighter control on
>>> efficiency/performance as well as behavior under composition, here are some
>>> examples: [
>>> https://urldefense.com/v3/__https://github.com/openjdk/jdk/blob/master/test/micro/org/openjdk/bench/java/util/stream/ops/ref/BenchmarkGathererImpls.java*L113__;Iw!!ACWV5N9M2RV99hQ!MFknMPf08p9oLTHtcHIIljRuma7ct6sarJRqTWKzmBiiGJBjtDEZsgGrkDbwxLl1NhEwVwz-RhHv3h3t54rw$
>>> |
>>> https://github.com/openjdk/jdk/blob/master/test/micro/org/openjdk/bench/java/util/stream/ops/ref/BenchmarkGathererImpls.java#L113
>>> ]
>> I've not seen any differences in term of performance:
>> MapGathererBenchmark.gatherer_map_sum avgt 5 546.058 ± 4.224
>> us/op
>> MapGathererBenchmark.gatherer_mapsublcass_sum avgt 5 546.391 ± 1.508 us/op
>> but yes, being able to override andThen() is important.
>>> Cheers,
>>> √
>> Rémi
>>> Viktor Klang
>>> Software Architect, Java Platform Group
>>> Oracle
>>> From: core-libs-dev <core-libs-dev-retn at openjdk.org> on behalf of Viktor Klang
>>> <viktor.klang at oracle.com>
>>> Sent: Wednesday, 24 January 2024 14:34
>>> To: forax at univ-mlv.fr <forax at univ-mlv.fr>
>>> Cc: core-libs-dev <core-libs-dev at openjdk.java.net>; Paul Sandoz
>>> <psandoz at openjdk.java.net>
>>> Subject: Re: Gatherer: spliterator characteristics are not propagated
>>> Presuming that you mean mutating the Gatherer such that its behavior isn't
>>> stable, the difference (at least to me) is that creating such a mutable
>>> Gatherer would violate the specification of Gatherer: [
>>> https://urldefense.com/v3/__https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/stream/Gatherer.java*L63__;Iw!!ACWV5N9M2RV99hQ!MFknMPf08p9oLTHtcHIIljRuma7ct6sarJRqTWKzmBiiGJBjtDEZsgGrkDbwxLl1NhEwVwz-RhHv3uXOerfv$
>>> |
>>> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/stream/Gatherer.java#L63
>>> ]
>>> Cheers,
>>> √
>>> Viktor Klang
>>> Software Architect, Java Platform Group
>>> Oracle
>>> From: forax at univ-mlv.fr <forax at univ-mlv.fr>
>>> Sent: Tuesday, 23 January 2024 21:04
>>> To: Viktor Klang <viktor.klang at oracle.com>
>>> Cc: core-libs-dev <core-libs-dev at openjdk.java.net>; Paul Sandoz
>>> <psandoz at openjdk.java.net>
>>> Subject: [External] : Re: Gatherer: spliterator characteristics are not
>>> propagated
>>>> From: "Viktor Klang" <viktor.klang at oracle.com>
>>>> To: "Remi Forax" <forax at univ-mlv.fr>
>>>> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>, "Paul Sandoz"
>>>> <psandoz at openjdk.java.net>
>>>> Sent: Monday, January 22, 2024 10:06:27 PM
>>>> Subject: Re: Gatherer: spliterator characteristics are not propagated
>>>>> The flags are in sync with the implementation because the only way to create a
>>>>> Gatherer if through the factory methods and those factory methods (and only
>>>>> them) compute the proper combination of SEQUENTIAL | STATELESS | GREEDY. A user
>>>>> should not be able to set those flags. Only the flags KEEP_* are settable by a
>>>>> user.
>>>> But I presume this also requires to have a `int characteristics()`-method on the
>>>> Gatherer interfacewhich means that users who are not using the factory methods
>>>> will have full possibility of not only returning the flags, but returning any
>>>> int.
>>> The current implementation suffers the same kind of issue, it's easy to write a
>>> mutable Gatherer and change the functions after creation, worst, right in the
>>> middle of a call to stream.gather(...).
>>> Perhaps the Gatherer interface should be sealed ? We did not have that option
>>> during the 1.8 timeframe, when the Collector API was created.
>>>>> The stream implementation has a whole mechanism in place to propagate/preverse
>>>>> flags like SIZED, DISTINCT or SORTED. For me, discussing about the merit of
>>>>> this mechanism seems a little off topic. I would prefer the Gatherer to be a
>>>>> good citizen and works seemlessly with the other intermediary operations.
>>>> I can see where you're coming from here, but to me, adding API surface needs to
>>>> pull its weight.
>>>> In this case I wasn't convinced that it did, hence we're having this
>>>> conversation. \uD83D\uDE42
>>>> Cheers,
>>>> √
>>> regards,
>>> Rémi
>>>> Viktor Klang
>>>> Software Architect, Java Platform Group
>>>> Oracle
>>>> From: forax at univ-mlv.fr <forax at univ-mlv.fr>
>>>> Sent: Monday, 22 January 2024 19:56
>>>> To: Viktor Klang <viktor.klang at oracle.com>
>>>> Cc: core-libs-dev <core-libs-dev at openjdk.java.net>; Paul Sandoz
>>>> <psandoz at openjdk.java.net>
>>>> Subject: [External] : Re: Gatherer: spliterator characteristics are not
>>>> propagated
>>>>> From: "Viktor Klang" <viktor.klang at oracle.com>
>>>>> To: "Remi Forax" <forax at univ-mlv.fr>
>>>>> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>, "Paul Sandoz"
>>>>> <psandoz at openjdk.java.net>
>>>>> Sent: Monday, January 22, 2024 4:22:11 PM
>>>>> Subject: Re: Gatherer: spliterator characteristics are not propagated
>>>>> Hi Rémi,
>>>> Hello,
>>>>> For instance, stateless is neither recessive nor dominant, since the composition
>>>>> of two stateless operations is only ever stateless if they both are greedy as
>>>>> well: [
>>>>> https://urldefense.com/v3/__https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/stream/Gatherers.java*L588__;Iw!!ACWV5N9M2RV99hQ!Lm52jd6kovd5t-cmrqqSLiRcIajBGXLxh85LO3eeiL6UxbKZuNPcUnO6z2i0FzMEoNr7U-cOBuWPCjo57FVW$
>>>>> |
>>>>> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/stream/Gatherers.java#L588
>>>>> ]
>>>> Okay, so choosing SEQUENTIAL vs PARALELLIZABLE is not that important given that
>>>> the combination is ad-hoc, reflecting the characterristics is enough.
>>>>> So even if making it represented as ints (more like Spliterator, rather than
>>>>> Collector) makes things faster, it's still both work to track, propagate, and
>>>>> also becomes a side-channel that needs to remain in sync with the actual
>>>>> implementation of the logic.
>>>> The flags are in sync with the implementation because the only way to create a
>>>> Gatherer if through the factory methods and those factory methods (and only
>>>> them) compute the proper combination of SEQUENTIAL | STATELESS | GREEDY. A user
>>>> should not be able to set those flags. Only the flags KEEP_* are settable by a
>>>> user.
>>>>> One could argue that logic such as: someCollection.stream().map(…).count() is a
>>>>> performance bug/inefficiency in an of itself as it would be faster to do
>>>>> someCollection.size().
>>>> The stream implementation has a whole mechanism in place to propagate/preverse
>>>> flags like SIZED, DISTINCT or SORTED. For me, discussing about the merit of
>>>> this mechanism seems a little off topic. I would prefer the Gatherer to be a
>>>> good citizen and works seemlessly with the other intermediary operations.
>>>> Cheers,
>>>> √
>>>> Viktor Klang
>>>> Software Architect, Java Platform Group
>>>> Oracle
>>>> From: forax at univ-mlv.fr <forax at univ-mlv.fr>
>>>> Sent: Monday, 22 January 2024 19:56
>>>> To: Viktor Klang <viktor.klang at oracle.com>
>>>> Cc: core-libs-dev <core-libs-dev at openjdk.java.net>; Paul Sandoz
>>>> <psandoz at openjdk.java.net>
>>>> Subject: [External] : Re: Gatherer: spliterator characteristics are not
>>>> propagated
>>>>> From: "Viktor Klang" <viktor.klang at oracle.com>
>>>>> To: "Remi Forax" <forax at univ-mlv.fr>
>>>>> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>, "Paul Sandoz"
>>>>> <psandoz at openjdk.java.net>
>>>>> Sent: Monday, January 22, 2024 4:22:11 PM
>>>>> Subject: Re: Gatherer: spliterator characteristics are not propagated
>>>>> Hi Rémi,
>>>> Hello,
>>>>> For instance, stateless is neither recessive nor dominant, since the composition
>>>>> of two stateless operations is only ever stateless if they both are greedy as
>>>>> well: [
>>>>> https://urldefense.com/v3/__https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/stream/Gatherers.java*L588__;Iw!!ACWV5N9M2RV99hQ!Lm52jd6kovd5t-cmrqqSLiRcIajBGXLxh85LO3eeiL6UxbKZuNPcUnO6z2i0FzMEoNr7U-cOBuWPCjo57FVW$
>>>>> |
>>>>> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/stream/Gatherers.java#L588
>>>>> ]
>>>> Okay, so choosing SEQUENTIAL vs PARALELLIZABLE is not that important given that
>>>> the combination is ad-hoc, reflecting the characterristics is enough.
>>>>> So even if making it represented as ints (more like Spliterator, rather than
>>>>> Collector) makes things faster, it's still both work to track, propagate, and
>>>>> also becomes a side-channel that needs to remain in sync with the actual
>>>>> implementation of the logic.
>>>> The flags are in sync with the implementation because the only way to create a
>>>> Gatherer if through the factory methods and those factory methods (and only
>>>> them) compute the proper combination of SEQUENTIAL | STATELESS | GREEDY. A user
>>>> should not be able to set those flags. Only the flags KEEP_* are settable by a
>>>> user.
>>>>> One could argue that logic such as: someCollection.stream().map(…).count() is a
>>>>> performance bug/inefficiency in an of itself as it would be faster to do
>>>>> someCollection.size().
>>>> The stream implementation has a whole mechanism in place to propagate/preverse
>>>> flags like SIZED, DISTINCT or SORTED. For me, discussing about the merit of
>>>> this mechanism seems a little off topic. I would prefer the Gatherer to be a
>>>> good citizen and works seemlessly with the other intermediary operations.
>>>>> Cheers,
>>>>> √
>>>> regards,
>>>> Rémi
>>>>> Viktor Klang
>>>>> Software Architect, Java Platform Group
>>>>> Oracle
>>>>> From: forax at univ-mlv.fr <forax at univ-mlv.fr>
>>>>> Sent: Saturday, 20 January 2024 17:40
>>>>> To: Viktor Klang <viktor.klang at oracle.com>
>>>>> Cc: core-libs-dev <core-libs-dev at openjdk.java.net>; Paul Sandoz
>>>>> <psandoz at openjdk.java.net>
>>>>> Subject: [External] : Re: Gatherer: spliterator characteristics are not
>>>>> propagated
>>>>>> From: "Viktor Klang" <viktor.klang at oracle.com>
>>>>>> To: "Remi Forax" <forax at univ-mlv.fr>
>>>>>> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>, "Paul Sandoz"
>>>>>> <psandoz at openjdk.java.net>
>>>>>> Sent: Thursday, January 18, 2024 5:14:38 PM
>>>>>> Subject: Re: Gatherer: spliterator characteristics are not propagated
>>>>>>> And for A.andThen(B), A.flags & B.flags should work, the stream is sorted if
>>>>>>> both gatherers keep it sorted.
>>>>>> That is unfortunately not the case. That would presume that you can implement
>>>>>> the composition such that it can preserve all the common flags. Some flags
>>>>>> could be "dominant" and some "recessive" to use genetics nomenclature.
>>>>> Some flags of the stream pipeline are "recessive", mainly SHORT_CIRCUIT, but not
>>>>> the characteristics of the Gatherer which can have the corresponding "dominant"
>>>>> flag, GREEDY, in this case.
>>>>> And the same for sequential, the flag should be PARALELIZABLE and not
>>>>> SEQUENTIAL.
>>>>> The idea is that the Gatherer characteristics can have the same bit set at the
>>>>> same position as the stream op flags (as defined by StreamOpFlag).
>>>>> So KEEP_DISTINCT is in position 0, KEEP_SORTED in in position 2 and KEEP_SIZED
>>>>> is in position 3.
>>>>> For GREEDY, we use the same position as SHORT_CIRCUIT and we will flip the bit
>>>>> (using XOR) when we want to extract the stream op flags from the
>>>>> characteristics
>>>>> All the factory methods call the generic of() with a combination of
>>>>> PARALELIZABLE and STATELESS and the user can adds the characteristics GREEDY,
>>>>> KEEP_DISTINCT, KEEP_SORTED and KEEP_SIZED (otherwise an exception should be
>>>>> raised).
>>>>> In StreamOpFlag, there are two unused positions (14 and 15), that's perfect for
>>>>> our two new states PARALELIZABLE and STATELESS, so no problem here (technically
>>>>> we can also reuse positions of the Spliterator characteristic given that those
>>>>> flags are masked before being sent to the GathererOp super constructor).
>>>>> The way to transform a Gatherer characteristics op to a stream flags op is to
>>>>> flip the bits corresponding to SHORT_CIRCUIT, add the highter bit of all flags
>>>>> but SHORT-CIRCUIT (because stream op flags are encoded using 2 bits) and mask
>>>>> to only retain SHORT_CIRCUIT, KEEP_DISTINCT, KEEP_SORTED and KEEP_SIZED.
>>>>> public static int toOpFlags ( int characteristics ) {
>>>>> return (( characteristics ^ SHORT_CIRCUIT_MASK ) | HIGHER_BITS ) &
>>>>> STREAM_OP_MASK ;
>>>>> }
>>>>> see below for a full script.
>>>>>>> I suppose that if those flags already exist, it's because they have a purpose
>>>>>>> and i do not understand how it can make the other operations slower.
>>>>>> Extra invocations, extra storage, and extra composition overhead is not free.
>>>>>> Since Stream is one-shot you need to include the construction cost with the
>>>>>> execution cost. For something like an empty Stream construction cost scan be
>>>>>> 90+% of the total costs.
>>>>> If you create a Gatherer, the characteristics is a constant (so the validity
>>>>> check is removed, it's just a mask and a test) so the result of calling
>>>>> toOpFlags() is a constant too.
>>>>> If the factory method is not inlined, the cost is 3 bitwise operations which is
>>>>> I believe faster than the "instanceof Greedy" used in the current code.
>>>>>> Cheers,
>>>>>> √
>>>>> regards,
>>>>> Rémi
>>>>> ---
>>>>> public class GathererFlag {
>>>>> // cut and paste from StreamOpFlag
>>>>> /**
>>>>> * The bit pattern for setting/injecting a flag.
>>>>> */
>>>>> private static final int SET_BITS = 0b01 ;
>>>>> /**
>>>>> * The bit pattern for clearing a flag.
>>>>> */
>>>>> private static final int CLEAR_BITS = 0b10 ;
>>>>> /**
>>>>> * The bit pattern for preserving a flag.
>>>>> */
>>>>> private static final int PRESERVE_BITS = 0b11 ;
>>>>> private static int position ( int opFlagSet ) {
>>>>> return Integer . numberOfTrailingZeros ( opFlagSet ) >> 1 ;
>>>>> }
>>>>> private static final int DISTINCT_POSITION = position ( StreamOpFlag .
>>>>> IS_DISTINCT );
>>>>> private static final int SORTED_POSITION = position ( StreamOpFlag . IS_SORTED
>>>>> );
>>>>> private static final int SIZED_POSITION = position ( StreamOpFlag . IS_SIZED );
>>>>> private static final int SHORT_CIRCUIT_POSITION = position ( StreamOpFlag .
>>>>> IS_SHORT_CIRCUIT );
>>>>> private static final int STATELESS_POSITION = 14 ;
>>>>> private static final int PARELLIZABLE_POSITION = 15 ;
>>>>> public static final int PARELLIZABLE = SET_BITS << ( PARELLIZABLE_POSITION << 1
>>>>> );
>>>>> public static final int STATELESS = SET_BITS << ( STATELESS_POSITION << 1 );
>>>>> public static final int GREEDY = SET_BITS << ( SHORT_CIRCUIT_POSITION << 1 );
>>>>> public static final int KEEP_DISTINCT = SET_BITS << ( DISTINCT_POSITION << 1 );
>>>>> public static final int KEEP_SORTED = SET_BITS << ( SORTED_POSITION << 1 );
>>>>> public static final int KEEP_SIZED = SET_BITS << ( SIZED_POSITION << 1 );
>>>>> private static final int SHORT_CIRCUIT_MASK = SET_BITS << (
>>>>> SHORT_CIRCUIT_POSITION << 1 );
>>>>> // no GREEDY here
>>>>> private static final int HIGHER_BITS = ( PARELLIZABLE | STATELESS |
>>>>> KEEP_DISTINCT | KEEP_SORTED | KEEP_SIZED ) << 1 ;
>>>>> private static final int STREAM_OP_MASK =
>>>>> (( GREEDY | KEEP_DISTINCT | KEEP_SORTED | KEEP_SIZED ) << 1 ) |
>>>>> GREEDY | KEEP_DISTINCT | KEEP_SORTED | KEEP_SIZED ;
>>>>> public static String toString ( int characteristics ) {
>>>>> return Stream . of ( characteristics )
>>>>> .< String >mapMulti(( f , consumer ) -> {
>>>>> if (( f & PARELLIZABLE ) == PARELLIZABLE ) {
>>>>> consumer .accept( "PARELLIZABLE" );
>>>>> }
>>>>> if (( f & STATELESS ) == STATELESS ) {
>>>>> consumer .accept( "STATELESS" );
>>>>> }
>>>>> if (( f & GREEDY ) == GREEDY ) {
>>>>> consumer .accept( "GREEDY" );
>>>>> }
>>>>> if (( f & KEEP_DISTINCT ) == KEEP_DISTINCT ) {
>>>>> consumer .accept( "KEEP_DISTINCT" );
>>>>> }
>>>>> if (( f & KEEP_SORTED ) == KEEP_SORTED ) {
>>>>> consumer .accept( "KEEP_SORTED" );
>>>>> }
>>>>> if (( f & KEEP_SIZED ) == KEEP_SIZED ) {
>>>>> consumer .accept( "KEEP_SIZED" );
>>>>> }
>>>>> })
>>>>> .collect( Collectors . joining ( ", " ));
>>>>> }
>>>>> public static int toOpFlags ( int characteristics ) {
>>>>> return (( characteristics ^ SHORT_CIRCUIT_MASK ) | HIGHER_BITS ) &
>>>>> STREAM_OP_MASK ;
>>>>> }
>>>>> public static String toOpFlagsString ( int opFlags ) {
>>>>> return Arrays . stream ( StreamOpFlag . values ())
>>>>> .map( op -> {
>>>>> if ( op .isPreserved( opFlags )) {
>>>>> return "preserved " + op ;
>>>>> }
>>>>> if ( op .isCleared( opFlags )) {
>>>>> return "cleared " + op ;
>>>>> }
>>>>> if ( op .isKnown( opFlags )) {
>>>>> return "set " + op ;
>>>>> }
>>>>> return "?? " + op ;
>>>>> })
>>>>> .collect( Collectors . joining ( ", " ));
>>>>> }
>>>>> void main () {
>>>>> var characteristics = PARELLIZABLE | STATELESS | GREEDY | KEEP_DISTINCT |
>>>>> KEEP_SORTED | KEEP_SIZED ;
>>>>> System . out .println( toOpFlagsString ( toOpFlags ( characteristics )));
>>>>> var characteristics2 = STATELESS | KEEP_DISTINCT | KEEP_SIZED ;
>>>>> System . out .println( toOpFlagsString ( toOpFlags ( characteristics2 )));
>>>>> }
>>>>> }
>>>>>> Viktor Klang
>>>>>> Software Architect, Java Platform Group
>>>>>> Oracle
>>>>>> From: forax at univ-mlv.fr <forax at univ-mlv.fr>
>>>>>> Sent: Thursday, 18 January 2024 16:17
>>>>>> To: Viktor Klang <viktor.klang at oracle.com>
>>>>>> Cc: core-libs-dev <core-libs-dev at openjdk.java.net>; Paul Sandoz
>>>>>> <psandoz at openjdk.java.net>
>>>>>> Subject: [External] : Re: Gatherer: spliterator characteristics are not
>>>>>> propagated
>>>>>>> From: "Viktor Klang" <viktor.klang at oracle.com>
>>>>>>> To: "Remi Forax" <forax at univ-mlv.fr>
>>>>>>> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>, "Paul Sandoz"
>>>>>>> <psandoz at openjdk.java.net>
>>>>>>> Sent: Thursday, January 18, 2024 3:36:07 PM
>>>>>>> Subject: Re: Gatherer: spliterator characteristics are not propagated
>>>>>>> I suspect that it is a rather slippery slope, once KEEP-flags are added, then
>>>>>>> others will want to be able to have INJECT-flags, and then people might have
>>>>>>> different opinions w.r.t. the default should be to clear all flags etc.
>>>>>>> And that's even before one looks at the composition-part of it, what are the
>>>>>>> flags for A.andThen(B)? (then extrapolate to N compositions and the available
>>>>>>> set of flags always approaches 0)
>>>>>>> I spent quite a bit of time on this and in the end tracking all this info, and
>>>>>>> making sure that the flags of implementations correspond to the actual
>>>>>>> behavior, just ended up costing performance for most streams and introduced an
>>>>>>> extra dimension to creation and maintenance which I had a hard time justifying.
>>>>>> It can be a slippery slope if we were designing from the ground up but the
>>>>>> stream implementation already exists and SORTED, DISTINCT and SIZED are the
>>>>>> flags that are already tracked by the current implementation.
>>>>>> Currently only SHORT_CIRCUIT is set (if not greedy),
>>>>>> see [
>>>>>> https://urldefense.com/v3/__https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/stream/GathererOp.java*L209__;Iw!!ACWV5N9M2RV99hQ!PhMxqlDzLWPRuwYc7ECRKNPVs0BtnoE-RdT-Jdkng7S-iFuERAHYcWvJ-OMKGLrkPdSrUl3xj1R9ypyeqeWI$
>>>>>> |
>>>>>> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/stream/GathererOp.java#L209
>>>>>> ]
>>>>>> And for A.andThen(B), A.flags & B.flags should work, the stream is sorted if
>>>>>> both gatherers keep it sorted.
>>>>>>> Making specific, rare, combinations of operations faster at the expense of
>>>>>>> making 99% of all others slower is a hard pill for most to swallow.
>>>>>> I suppose that if those flags already exist, it's because they have a purpose
>>>>>> and i do not understand how it can make the other operations slower.
>>>>>>> Cheers,
>>>>>>> √
>>>>>> regards,
>>>>>> Rémi
>>>>>>> Viktor Klang
>>>>>>> Software Architect, Java Platform Group
>>>>>>> Oracle
>>>>>>> From: forax at univ-mlv.fr <forax at univ-mlv.fr>
>>>>>>> Sent: Thursday, 18 January 2024 10:28
>>>>>>> To: Viktor Klang <viktor.klang at oracle.com>
>>>>>>> Cc: core-libs-dev <core-libs-dev at openjdk.java.net>; Paul Sandoz
>>>>>>> <psandoz at openjdk.java.net>
>>>>>>> Subject: [External] : Re: Gatherer: spliterator characteristics are not
>>>>>>> propagated
>>>>>>>> From: "Viktor Klang" <viktor.klang at oracle.com>
>>>>>>>> To: "Remi Forax" <forax at univ-mlv.fr>, "core-libs-dev"
>>>>>>>> <core-libs-dev at openjdk.java.net>
>>>>>>>> Sent: Wednesday, January 17, 2024 8:48:07 PM
>>>>>>>> Subject: Re: Gatherer: spliterator characteristics are not propagated
>>>>>>>> Hi Rémi,
>>>>>>>> You can find some of my benches here: [
>>>>>>>> https://urldefense.com/v3/__https://github.com/openjdk/jdk/tree/master/test/micro/org/openjdk/bench/java/util/stream/ops/ref__;!!ACWV5N9M2RV99hQ!JJy6F9NoL6wKZQK5158up_fTRvH8X7F6JK8T7Euuf8vzbSQbr23eWa9S_yb61ksONVrLrdesCF_au5zyje2l$
>>>>>>>> |
>>>>>>>> https://github.com/openjdk/jdk/tree/master/test/micro/org/openjdk/bench/java/util/stream/ops/ref
>>>>>>>> ]
>>>>>>>> Initially I had Characteristics such as ORDERED etc on Gatherer but it just
>>>>>>>> didn't end up worth it when looking at the bench results over a wide array of
>>>>>>>> stream sizes and number of operations.
>>>>>>> I think there are 3 gatherer characteristics that make sense: KEEP_SORTED,
>>>>>>> KEEP_DISTINCT and KEEP_SIZED,
>>>>>>> all of them say that if the stream was sorted/distinct/sized then the stream
>>>>>>> returned by a call to gather() is still sorted (with the same comparator),
>>>>>>> distinct or sized.
>>>>>>> As examples, map() is KEEP_SIZED, filter() is KEEP_SORTED | KEEP_DISTINCT and
>>>>>>> windowFixed is KEEP_DISTINCT.
>>>>>>> [CC Paul, so he can correct me if i'm saying something stupid]
>>>>>>> Now for the benchmarks, it depends what you want to measure, benchmarking
>>>>>>> streams is tricky. This is what i know about benchmarking streams.
>>>>>>> First, the JIT has two ways to profile types at runtime,
>>>>>>> Either a method takes a function as parameter
>>>>>>> void map(Function function) {
>>>>>>> function.apply(...)
>>>>>>> }
>>>>>>> and when map is called with a subtype of Function, the JIT will propagate the
>>>>>>> exact type when map is inlined,
>>>>>>> Or a method use a field
>>>>>>> class Op {
>>>>>>> Function function;
>>>>>>> void map() {
>>>>>>> function.apply(...)
>>>>>>> }
>>>>>>> }
>>>>>>> in that case, the VM records the profile of function.apply() and if there are
>>>>>>> more than two different profiles, the VM declare profile poluttion and do not
>>>>>>> try to optimize.
>>>>>>> The Stream implementation tries very hard to use only parameters instead of
>>>>>>> fields, that's why it does not use classical Iterator that are pull iterator (a
>>>>>>> filter iterator requires a field) but a Spliterator which is a push iterator,
>>>>>>> the element is sent as parameter of the consumer.That's also why collect does
>>>>>>> not use the builder pattern (that accumulate values in fields) but a Collector
>>>>>>> that publish the functions to be called as parameter.
>>>>>>> Obvisously, this is more complex than that, a Collector stores the functions in
>>>>>>> fields so it should not work well but the implementation uses a record that
>>>>>>> plays well with escape analysis. Escape analysis see the fields of an instance
>>>>>>> as parameters so the functions of a Collector are correctly propagated (if the
>>>>>>> escape analysis works). And lambdas are using invokedynamic, and the VM tries
>>>>>>> really hard to inline invokedynamic, so lambdas (that captures value or not)
>>>>>>> are routinely fully inlined with the intermediate operation of a stream.
>>>>>>> In your tests, i've not seen comparaisons between an existing method like map()
>>>>>>> or filter() followed by a sorted()/distinct()/count()/toList(), i.e. operations
>>>>>>> where the characteristics KEEP_* have an impact and their equivalent using a
>>>>>>> Gatherer.
>>>>>>>> Cheers,
>>>>>>>> √
>>>>>>> regards,
>>>>>>> Rémi
>>>>>>>> Viktor Klang
>>>>>>>> Software Architect, Java Platform Group
>>>>>>>> Oracle
>>>>>>>> From: core-libs-dev <core-libs-dev-retn at openjdk.org> on behalf of Remi Forax
>>>>>>>> <forax at univ-mlv.fr>
>>>>>>>> Sent: Wednesday, 17 January 2024 16:48
>>>>>>>> To: core-libs-dev <core-libs-dev at openjdk.java.net>
>>>>>>>> Subject: Gatherer: spliterator characteristics are not propagated
>>>>>>>> While doing some benchmarking of the Gatherer API, i've found that the
>>>>>>>> characteristics of the spliterator was not propagated by the method
>>>>>>>> Stream.gather() making the stream slower than it should.
>>>>>>>> As an example, there is no way when reimplementing map() using a Gatherer to say
>>>>>>>> that this intermediate operation keep the size, which is important if the
>>>>>>>> terminal operation is toList() because if the size is known, toList() will
>>>>>>>> presize the List and avoid the creation of an intermediary ArrayList.
>>>>>>>> See [
>>>>>>>> https://urldefense.com/v3/__https://github.com/forax/we_are_all_to_gather/blob/master/src/main/java/com/gihtub/forax/wearealltogather/bench/MapGathererBenchmark.java__;!!ACWV5N9M2RV99hQ!JJy6F9NoL6wKZQK5158up_fTRvH8X7F6JK8T7Euuf8vzbSQbr23eWa9S_yb61ksONVrLrdesCF_auzwTY8aB$
>>>>>>>> |
>>>>>>>> https://github.com/forax/we_are_all_to_gather/blob/master/src/main/java/com/gihtub/forax/wearealltogather/bench/MapGathererBenchmark.java
>>>>>>>> ]
>>>>>>>> I think that adding a way to propagate the spliterator characteristics through a
>>>>>>>> Gatherer would greatly improve the performance of commons streams (at least all
>>>>>>>> the ones that end with a call to toList).
>>>>>>>> I have some idea of how to do that, but I prefer first to hear if i've overlook
>>>>>>>> something and if improving the performance is something worth changing the API.
>>>>>>>> regards,
>>>>>>>> Rémi
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20240129/25b0cc7e/attachment-0001.htm>
More information about the core-libs-dev
mailing list