[External] : Re: RFR: 8291769: Translation of switch with record patterns could be improved
Jan Lahoda
jan.lahoda at oracle.com
Fri Aug 5 19:35:14 UTC 2022
On 05. 08. 22 19:24, forax at univ-mlv.fr wrote:
>
> ----- Original Message -----
>> From: "jan lahoda" <jan.lahoda at oracle.com>
>> To: "Remi Forax" <forax at univ-mlv.fr>
>> Cc: "Jan Lahoda" <jlahoda at openjdk.org>, "Brian Goetz" <brian.goetz at oracle.com>, "compiler-dev"
>> <compiler-dev at openjdk.org>
>> Sent: Thursday, August 4, 2022 10:10:06 PM
>> Subject: Re: [External] : Re: RFR: 8291769: Translation of switch with record patterns could be improved
>> On 04. 08. 22 19:23, forax at univ-mlv.fr wrote:
>>
>>> ----- Original Message -----
>>>> From: "jan lahoda" <jan.lahoda at oracle.com>
>>>> To: "Remi Forax" <forax at univ-mlv.fr>, "Jan Lahoda" <jlahoda at openjdk.org>, "Brian
>>>> Goetz" <brian.goetz at oracle.com>
>>>> Cc: "compiler-dev" <compiler-dev at openjdk.org>
>>>> Sent: Thursday, August 4, 2022 6:35:18 PM
>>>> Subject: Re: RFR: 8291769: Translation of switch with record patterns could be
>>>> improved
>>>> On 04. 08. 22 17:43, Remi Forax wrote:
>>>>
>>>>> ----- Original Message -----
>>>>>> From: "Jan Lahoda" <jlahoda at openjdk.org>
>>>>>> To: compiler-dev at openjdk.org
>>>>>> Sent: Thursday, August 4, 2022 5:04:52 PM
>>>>>> Subject: RFR: 8291769: Translation of switch with record patterns could be
>>>>>> improved
>>>>>> This is an attempt to improve the performance and scalability of switches with
>>>>>> record patterns.
>>>>>>
>>>>>> There are two main parts of this patch:
>>>>>> 1. for cases of consecutive runs of cases with the same record pattern, these
>>>>>> are replaced with a single case and a nested switch. E.g.:
>>>>>>
>>>>>> switch (obj) {
>>>>>> case Box(String s) -> {}
>>>>>> case Box(Integer i) -> {}
>>>>>> case Box(Number n) -> {}
>>>>>> ...
>>>>>> }
>>>>>> =>
>>>>>> switch (obj) {
>>>>>> case Box b ->
>>>>>> switch (b.o()) {
>>>>>> case String s -> {}
>>>>>> case Integer i -> {}
>>>>>> case Number n -> {}
>>>>>> default -> continue-with-outer-switch;
>>>>>> };
>>>>>> ...
>>>>>> }
>>>>>>
>>>>>>
>>>>>> This is done by first unrolling the record patterns into simple binding patterns
>>>>>> a guards, and then by finding cases with the common binding pattern as a label
>>>>>> and a viable guard. Binding patterns are reused as much as possibly,
>>>>>> eliminating specialized handling of record patterns as much as possible.
>>>>> How it works when you have a record pattern followed by a type pattern with the
>>>>> same type ?
>>>>> Something like:
>>>>>
>>>>> switch (obj) {
>>>>> case Box(String s) -> {}
>>>>> case Box(Integer i) -> {}
>>>>>
>>>>> case Box b -> {}
>>>>> }
>>>>>
>>>>> because you now have twice the same type pattern on the outer switch but the
>>>>> first one should not NPE.
>>>> Currently the `case Box b -> {}` is kept separate. It would be possible
>>>> to merge (it would simply be a default in the nested switch), but it is
>>>> an additional complexity in a fairly complex code already.
>>>>
>>>>
>>>>>> 2. When a record accessor method fails with an exception, we need to wrap this
>>>>>> exception with a `MatchException`. Currently this is being done by introducing
>>>>>> a special proxy method which catches the exception and re-throws. The proposed
>>>>>> patch here eliminates the need for the accessor methods by producing an
>>>>>> appropriate `ExceptionTable` in the classfile, and a separate catch handler.
>>>>>> This handler is attached to the innermost usable block, which is either the
>>>>>> method block, lambda body, (static or non-static) initializer or a try block.
>>>>>> This should ensure correct semantics, while not producing too many unnecessary
>>>>>> catch handlers.
>>>>> Yes !
>>>>>
>>>>> As said above, the semantics for null is slightly changed, because now you may
>>>>> throw a NPE instead of a MatchException.
>>>> The idea here is that the semantics should not be changed, and changes
>>>> to semantics are bugs. But thanks to your comment, I realized null
>>>> record components are not handled properly, so I've attempted to fix that:
>>>>
>>>> https://urldefense.com/v3/__https://github.com/openjdk/jdk/pull/9746/commits/7ddeafab1d1ea23285e60765ec0e61d7a509e442__;!!ACWV5N9M2RV99hQ!ILgm-CykKXhL7fJ8n8zqHYDrHshMWU9tnE836sT6jAqJVoQZnExXgSxUax5NhJvl3XzSqgJzPPzm_1SYQYk$
>>>>
>>>>
>>>>> You can add explicit nullchecks to throw a MatchException instead but i think we
>>>>> can do better for our users.
>>>>>
>>>>> I believe that with this transformation, we can now make the difference between
>>>>> the 3 kinds of errors,
>>>>> - the call to the accessor / destructor fails throwing an error similar to
>>>>> ExceptionInTheInitializerError (ExceptionInTheDestructorError ?)
>>>>> - the tested value is null throwing a NPE because most of them are implicit when
>>>>> b.o() is called. This means that the compiler has to insert a requireNonNull if
>>>>> the nullcheck is not implicit.
>>>>> - when there are more permitted subtypes at runtime throwing an
>>>>> IncompatibleClassChangeError (like with an switch expression on an enum)
>>>> (FWIW, I believe the spec is saying what should happen in specific
>>>> cases, so I don't think this is something javac should decide on its
>>>> own. javac can decide on how the behavior is implemented, but not the
>>>> behavior.)
>>> yes, i want to change the spec because as a user it's hard to know how to fix
>>> the code when a MatchException is thrown.
>> Sure - but I am not quite sure if this PR is a place to discuss that.
>>
>>
>>>>> for the last one, the idea is that if there is a sealed type, instead of
>>>>> generating an if instanceof for all cases, the last one should not be an
>>>>> instanceof but just a cast with a cacth handler that catch the
>>>>> ClassCastException and throw an IncompatibleClassChangeError wrapping the CCE
>>>>> instead.
>>>> Note that when switching over a type we don't generate instanceof for
>>>> the subtypes of that type. The typeSwitch bootstrap/indy does the
>>>> checks, and the bytecode produced by javac only produces checkcasts. (It
>>>> may produce instanceofs for the nested patterns, though.) It would be
>>>> possible to use a default instead of the last case, and add catch
>>>> handler for the checkcast, but generating cases for all the checked
>>>> types, and adding a default which throws (which I believe is the current
>>>> implementation) feels much easier and cleaner to implement, and I don't
>>>> really see a significant disadvantage in that.
>>> It's a performance issue because you need to recheck the same type pattern
>>> multiple times if the switch alternate a record pattern followed by a type
>>> pattern followed by a record pattern ...
>>
>> I assume you are referring to the following case, not to a case where we
>> would be catching ClassCastExceptions:
>>
>> case Box(String s) -> {}
>>
>> case Box b -> {}
>>
>>
>> It is true there will (likely) be one more instanceof at runtime, and we
>> could avoid this at the cost of an additional complexity in javac.
> yes, i think that in the end we will need to build a decision tree, in can be done in javac or inside a bootstrap method (like the lambda proxy is generated),
> the later having the advantage to not requirering recompilation to enjoy more performance.
>
>>
>> If the record pattern and type pattern would alternate multiple times,
>> that would (I think) require the type patterns to have guards. Like:
>>
>> case Box(String s) -> {}
>>
>> case Box b when guard1(b) -> {}
>>
>> case Box(Integer i) -> {}
>>
>> case Box b when guard2(b) -> {}
>>
>> ...
>>
>>
>> Optimizing this is even more challenging, as we would need to preserve
>> the order.
> You only need to preserve the order of the "when", not the order of the full pattern matching.
Yes, some re-orderings may be possible, but the guard will very severely
limit the reoderings possible. In the above case, I doubt we could
reorder the cases/patterns in any way.
>
> and i was thinking to a pattern matching like that:
> switch(o) {
> case A(String s) -> ...
> case A a -> ...
> case B(String s) -> ...
> case B b ->
> }
>
> which alternate a record pattern and a type pattern.
>
>>
>> In any case, I'm a bit afraid that we could enhance a translation patch
>> forever, always adding new cases that can be optimized. So, I think we
>> need to draw a line somewhere where the patch provides a benefit while
>> still being testable and reviewable. With a possible separate
>> improvements, if they prove to be useful. It is possible I haven't drawn
>> the line far enough, but looking at the patch, it seems complex enough.
> I think the issue is that a list of pattern is not the right intermediary structure to try to optimize the pattern matching, a decision tree is a better intermediary representation (this is how pattern matching is usually optimized, i've not invented something new :) )
>
> Here is an example of such decision tree:
> https://urldefense.com/v3/__https://github.com/forax/switch-pattern-combinator__;!!ACWV5N9M2RV99hQ!JevAQE8IkRf4n-BMKA2sMTNFfJ5sAyJ1xopR2O9rq_45-xqaHOgirecR8E4zIGB_RgMb27G3tlcHEuGADjk$
I am not really opposed to having an intermediate structure, but I think
the overall cost of the structure is likely to be significant, and it
should provide significantly better code to offset that.
Looking at the page, I see:
The advantage of a decision tree is that if two patterns have a common
prefix, the code for the common prefix is generated only once.
I wonder if there's a *conceptual* difference between what this PR is
doing and what your code is doing. The PR here is trying to take common
prefixes (of viable cases) and generate code for them only once. I don't
think that not optimizing
case A(String s) -> {}
case A a -> {}
is a conceptual difference, but if this is something that is seen as
critical, I am fairly sure I can implement that without creating a brand
new structure and code to convert the AST into it and back.
It is also true the current code does not reoder the cases. I am not
sure if your code does reordering, but I didn't see a set of rules for
safe reorderings, which I think is the biggest problem here. My thinking
of safe rules for reordering was limited so far, and the ability to
reorder cases may be limited due to guards and separate compilation
considerations (we can also have new pattern types which may limit our
ability to reorder cases). But even though this PR does not reorder
cases, it is in principle doable.
Situation would, of course, be different if we tried to optimize not
only prefixes of the patterns - but this does not seem to be the
proposal in switch-pattern-combinator.
As for casting to the last permitted type - I don't see how this relates
to decision trees. While casting and catching might look interesting
from the bytecode perspective, it is something that is likely to be
relatively complex to implement in javac, and using an (effective)
instanceof and an explicit fallback does not really sound terrible.
There is also a question on when this is safe to do - if there's a `case
Object o` at the end of the switch, then probably this is not correct to
do anyway, etc.
Regarding deferring all this to runtime, that has definitely a lot of
desirable properties. And there were multiple experiments with that.
But, the API for that is fairly complex - probably easier to do now when
we have guards on cases, not guarded patterns, but still likely
significant. (Overall, guard are really tough, because they a) capture;
b) provide new bindings.)
Thanks,
Jan
>
> regards,
> Rémi
>
More information about the compiler-dev
mailing list