jdk 8291769: Translation of switch with record patterns could be improved

trafficstars

This is an attempt to improve the performance and scalability of switches with record patterns.

There are two main parts of this patch:

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.

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.

I ran the new code through a JMH benchmark: PatternsOptimizationTest.java.txt

The results are:

for "long" testcase (a switch with many cases):

PatternsOptimizationTest.testExistingTranslationLongSwitch   thrpt   25  1025740.668 ± 15325.355  ops/s
PatternsOptimizationTest.testNewTranslationLongSwitch        thrpt   25  1588461.471 ± 15315.509  ops/s

for "short" testcase (a switch with no so many cases):

PatternsOptimizationTest.testExistingTranslationShortSwitch  thrpt   25  6418845.624 ± 75981.939  ops/s
PatternsOptimizationTest.testNewTranslationShortSwitch       thrpt   25  6894823.439 ± 67420.858  ops/s

So, the performance seems to be improved, at least in these cases.

As a follow-up work, there are several other improvements that may be worth investigating like using if cascades instead of switches with very few cases (but possibly not very trivial for switch expressions, at least for switch expressions of type boolean), or improving the code produced by the runtime bootstrap method (SwitchBootstraps.typeSwitch).

Progress

[x] Change must be properly reviewed (1 review required, with at least 1 Reviewer)
[x] Change must not contain extraneous whitespace
[x] Commit message must refer to an issue

Issue

JDK-8291769: Translation of switch with record patterns could be improved

Reviewers

Vicente Romero (@vicente-romero-oracle - Reviewer) ⚠️ Review applies to 4f9f7f98

Reviewing

Using git

Checkout this PR locally:
$ git fetch https://git.openjdk.org/jdk pull/9746/head:pull/9746
$ git checkout pull/9746

Update a local copy of the PR:
$ git checkout pull/9746
$ git pull https://git.openjdk.org/jdk pull/9746/head

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 9746

View PR using the GUI difftool:
$ git pr show -t 9746

Using diff file

Download this PR as a diff file:
https://git.openjdk.org/jdk/pull/9746.diff

Aug 04 '22 14:08 lahodaj

:wave: Welcome back jlahoda! A progress list of the required criteria for merging this PR into master will be added to the body of your pull request. There are additional pull request commands available for use with this pull request.

Aug 04 '22 14:08 bridgekeeper[bot]

@lahodaj The following label will be automatically applied to this pull request:

compiler

When this pull request is ready to be reviewed, an "RFR" email will be sent to the corresponding mailing list. If you would like to change these labels, use the /label pull request command.

Aug 04 '22 15:08 openjdk[bot]

Webrevs

Aug 04 '22 15:08 mlbridge[bot]

Mailing list message from Remi Forax on compiler-dev:

----- 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.

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. 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)

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.

R?mi

Aug 04 '22 18:08 mlbridge[bot]

Mailing list message from Jan Lahoda on compiler-dev:

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://github.com/openjdk/jdk/pull/9746/commits/7ddeafab1d1ea23285e60765ec0e61d7a509e442

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.)

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.

Thanks,

??? Jan

R?mi

Aug 04 '22 18:08 mlbridge[bot]

Mailing list message from forax at univ-mlv.fr on compiler-dev:

----- 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.

so depending on how a user write a switch, performance are different, for example, with I a sealed type and A and B to subtype storing a field of type I

switch (i) { case A(A a) -> {} case A(B b) -> {} case B(A a) -> {} case B(B b) -> {} }

vs

switch (i) { case A(A a) -> {} case B(A a) -> {} case A(B b) -> {} case B(B b) -> {} }

that does not seem to be a good property for a desugaring, or i miss something ?

R?mi

Aug 04 '22 18:08 mlbridge[bot]

Mailing list message from forax at univ-mlv.fr on compiler-dev:

----- 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://github.com/openjdk/jdk/pull/9746/commits/7ddeafab1d1ea23285e60765ec0e61d7a509e442

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.

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 ...

Thanks,

??? Jan

R?mi

Aug 04 '22 18:08 mlbridge[bot]

Mailing list message from Jan Lahoda on compiler-dev:

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.

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.

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.

Thanks,

??? Jan

Thanks,

??? Jan

R?mi

Aug 04 '22 22:08 mlbridge[bot]

Mailing list message from forax at univ-mlv.fr on compiler-dev:

----- 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.

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://github.com/forax/switch-pattern-combinator

regards, R?mi

Aug 05 '22 20:08 mlbridge[bot]

Mailing list message from Jan Lahoda on compiler-dev:

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

Aug 05 '22 20:08 mlbridge[bot]

Mailing list message from forax at univ-mlv.fr on compiler-dev:

----- 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: Friday, August 5, 2022 9:35:14 PM Subject: Re: [External] : Re: RFR: 8291769: Translation of switch with record patterns could be improved

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 reorderings possible. In the above case, I doubt we could reorder the cases/patterns in any way.

I wonder if this example shows that there is a missing rule when computing the dominance relationships, if we want to make those patterns easy to read, i believe that having the guard at the end is more readable

case Box(String s) -> {} case Box(Integer i) -> {} case Box b when guard1(b) -> {} case Box b when guard2(b) -> {}

Having a guard should not a be a free from the dominance relationships card.

The dominance algorithm should be more something like we checks first without the guards and then we add the guards.

We already have a dominance between "case Box b when ..." and "case Box b" and between case Box(..) and case Box b so it seems quite logical to have one between case Box(...) and case Box b when ...

R?mi

Aug 06 '22 13:08 mlbridge[bot]

Mailing list message from forax at univ-mlv.fr on compiler-dev:

[...]

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.

I agree.

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.

You need the intermediary structure when the common prefix are not subsequent

case A(B b) -> case B(A a) -> case A(C c) ->

Here the first and the last case shares a common prefix.

It is also true the current code does not reorder 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.

One of the reason to backpedal on the idea of guarded patterns is to try to cleanly separate what can do side effects thus limit the reordering and what should not do side effects. A guard can do side effect thus it's not a pattern. A deconstructing pattern using a deconstructor should not do side effect ("should not" like in a stream, if you do it, you are on your own) because it's a pattern.

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.

The idea of using a cast is that you provide a good error message to the users because the ClassCastException stores the class that is not handled by the pattern matching. You loose that information if you use an explicit fallback.

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.

It is safe to do if the compiler has type-checked the patterns before, the cast is only done in case of a sealed type, not if there is a common supertype at the end.

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.)

"provide new bindings" => do you have an example of that ? I don't think a guard should be allowed to do that. It looks like a big gunfoot to me.

Thanks,

??? Jan

regards, R?mi

Aug 06 '22 13:08 mlbridge[bot]

Mailing list message from Jan Lahoda on compiler-dev:

On 05. 08. 22 22:52, forax at univ-mlv.fr wrote:

[...]

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. I agree.

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. You need the intermediary structure when the common prefix are not subsequent

case A(B b) -> case B(A a) -> case A(C c) ->

Here the first and the last case shares a common prefix.

Sorry, but I don't see why I can't do this particular thing without a specialized intermediate representation. A bigger question, I think, is when it is safe to do so, and when not.

It is also true the current code does not reorder 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. One of the reason to backpedal on the idea of guarded patterns is to try to cleanly separate what can do side effects thus limit the reordering and what should not do side effects. A guard can do side effect thus it's not a pattern. A deconstructing pattern using a deconstructor should not do side effect ("should not" like in a stream, if you do it, you are on your own) because it's a pattern.

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. The idea of using a cast is that you provide a good error message to the users because the ClassCastException stores the class that is not handled by the pattern matching. You loose that information if you use an explicit fallback.

Sorry, but if I understand what you are proposing is:

B b = (B) obj; //magical catch handler somewhere handling the CCE

$rest$;

what I am saying is that this can be achieved by an analog of:

if (obj instanceof B b) {

??? $rest$;

} else {

???? throw <an-exception-we-want>(obj.getClass());

}

What information is lost?

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. It is safe to do if the compiler has type-checked the patterns before, the cast is only done in case of a sealed type, not if there is a common supertype at the end.

I mean - consider:

sealed interface I {}

final class OnlySubtypeAtCompileTime implements I {}

record Box(I i) {}

Object b = new Box(<a-new-subtype-not-known-at-compile-time>);

switch (b) {

???? case Box(OnlySubtypeAtCompileTime t) -> System.err.println("Should probably not fail here,");

???? case Object obj -> System.err.println("but should end up here.");

}

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.) "provide new bindings" => do you have an example of that ?

Sure:

public class TA { ???public static void main(String... args) { ???????Object o = new Box(""); ???????switch (o) { ???????????case Box b when b.o() instanceof String s -> System.err.println(s); ???????????default -> {} ???????} ???} ???record Box(Object o) {} }

(There can be any number of new bindings from the guard, of course.)

I don't think a guard should be allowed to do that. It looks like a big gunfoot to me.

I believe the current specification supports guards that introduce new bindings:

http://cr.openjdk.java.net/~gbierman/jep427%2b405/jep427+405-20220601/specs/patterns-switch-record-patterns-jls.html#jls-6.3.4

To me, it seems desirable. In any case, an implementation PR is probably not very well suited to discuss opinions on what should be specced. In particular (but not only) a PR that is not expected to change the semantics.

Jan

Thanks,

??? Jan

regards, R?mi

-------------- next part -------------- An HTML attachment was scrubbed... URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20220805/93c245e7/attachment-0001.htm>

Aug 06 '22 13:08 mlbridge[bot]

Mailing list message from forax at univ-mlv.fr on compiler-dev:

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: Friday, August 5, 2022 11:54:05 PM Subject: Re: [External] : Re: RFR: 8291769: Translation of switch with record patterns could be improved

On 05. 08. 22 22:52, [ mailto:forax at univ-mlv.fr | forax at univ-mlv.fr ] wrote:

[...]

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$ | 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.

I agree.

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.

You need the intermediary structure when the common prefix are not subsequent

case A(B b) -> case B(A a) -> case A(C c) ->

Here the first and the last case shares a common prefix.

Sorry, but I don't see why I can't do this particular thing without a specialized intermediate representation.

The patterns are a partial orders, because we can optimize the ones with a common prefix, we need a sort, a decision tree is equivalent to a sort. There are several advantages to use a decision tree instead of a sort, - it's easier to visualize - it mimics the the usual hand-written code (you don't repeat the instanceofs, you enclose them) - i believe that for the code generation, doing local decisions on each node is good enough, we do not need to propagate information in between nodes.

A bigger question, I think, is when it is safe to do so, and when not.

yes, not all re-ordering are safe, we need to keep some constraints. Fortunately, the ordering problems only arise when there are guards. The idea is that for each node of the decision tree, you should generate the code in that order, first for the record pattern, then the code for the guards then the code for the type pattern, in that order. If the guards are recorded in the same order as in the pattern matching (this is equivalent to say that the sort should be stable in term of guards), we should be ok.

As you said, the current spec allows to freely mix type patterns and type pattern + guard pattern with the same type, this has to be fixed at the spec level. I think it's reasonable to introduce an order between the type pattern + guard pattern and the type pattern on the same type, because it's more readable and because we do not want users to care to much about the order of the patterns to get good performance. You should get good performance by default, and not have to crawle StackOverflow to learn the arcane of finding the "right order" for patterns.

R?mi -------------- next part -------------- An HTML attachment was scrubbed... URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20220807/f31904fe/attachment.htm>

Aug 07 '22 10:08 mlbridge[bot]

Mailing list message from forax at univ-mlv.fr on compiler-dev:

[...]

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.

The idea of using a cast is that you provide a good error message to the users because the ClassCastException stores the class that is not handled by the pattern matching. You loose that information if you use an explicit fallback.

Sorry, but if I understand what you are proposing is:

B b = (B) obj; //magical catch handler somewhere handling the CCE

$rest$;

what I am saying is that this can be achieved by an analog of:

if (obj instanceof B b) {

$rest$;

} else {

throw <an-exception-we-want>(obj.getClass());

}

What information is lost?

sorry I misunderstood you. There is no information lost in this case, the generated bytecodes is just bigger which one one reason cited by Brian to only throw once in the fallback case.

Nitpicking, "null" is treated differently so the code should be

if (obj == null) { throw NPE; }

if (obj instanceof B b) {

$rest$;

} else {

throw <an-exception-we-want>(obj.getClass());

}

Using a cast also has an issue with null but the NPE can be thrown implicitly if the sub-pattern is a record (something you know locally for each node of the decision tree).

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.

It is safe to do if the compiler has type-checked the patterns before, the cast is only done in case of a sealed type, not if there is a common supertype at the end.

I mean - consider:

sealed interface I {}

final class OnlySubtypeAtCompileTime implements I {}

record Box(I i) {}

Object b = new Box(<a-new-subtype-not-known-at-compile-time>);

switch (b) {

case Box(OnlySubtypeAtCompileTime t) -> System.err.println("Should probably not fail here,");

case Object obj -> System.err.println("but should end up here.");

}

I think we are agreeing here that in this case, using a cast instead of an instanceof is a mistake. We only need the cast in case if there is a sealed type and no fallback, this information has flow from the type-ckecking.

R?mi -------------- next part -------------- An HTML attachment was scrubbed... URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20220807/924682c3/attachment-0001.htm>

Aug 07 '22 10:08 mlbridge[bot]

Mailing list message from forax at univ-mlv.fr on compiler-dev:

[...]

"provide new bindings" => do you have an example of that ?

Sure:

public class TA { public static void main(String... args) { Object o = new Box(""); switch (o) { case Box b when b.o() instanceof String s -> System.err.println(s); default -> {} } } record Box(Object o) {} }

(There can be any number of new bindings from the guard, of course.)

I don't think a guard should be allowed to do that. It looks like a big gunfoot to me.

I believe the current specification supports guards that introduce new bindings:

[ http://cr.openjdk.java.net/~gbierman/jep427%2b405/jep427+405-20220601/specs/patterns-switch-record-patterns-jls.html#jls-6.3.4 | http://cr.openjdk.java.net/~gbierman/jep427%2b405/jep427+405-20220601/specs/patterns-switch-record-patterns-jls.html#jls-6.3.4 ]

To me, it seems desirable. In any case, an implementation PR is probably not very well suited to discuss opinions on what should be specced. In particular (but not only) a PR that is not expected to change the semantics.

Ok, thanks for the example, it means we should lift the when expression not has a static method but as a static pattern method, something which will be more clear when we will have a better idea about how to do that once user defined pattern method like Optional.of(value -> ...) will be introduced.

R?mi -------------- next part -------------- An HTML attachment was scrubbed... URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20220807/df609ccf/attachment.htm>

Aug 07 '22 10:08 mlbridge[bot]

Mailing list message from Jan Lahoda on compiler-dev:

On 07. 08. 22 10:02, forax at univ-mlv.fr wrote:

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

\*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\: \*Friday\, August 5\, 2022 11\:54\:05 PM
\*Subject\: \*Re\: \[External\] \: Re\: RFR\: 8291769\: Translation of
switch with record patterns could be improved

On 05\. 08\. 22 22\:52\, forax at univ\-mlv\.fr wrote\:

    \[\.\.\.\]

                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\.

    I agree\.

        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\.

    You need the intermediary structure when the common prefix are not subsequent

    case A\(B b\) \->
    case B\(A a\) \->
    case A\(C c\) \->

    Here the first and the last case shares a common prefix\.


Sorry\, but I don\'t see why I can\'t do this particular thing
without a specialized intermediate representation\.

The patterns are a partial orders, because we can optimize the ones with a common prefix, we need a sort, a decision tree is equivalent to a sort. There are several advantages to use a decision tree instead of a sort, - it's easier to visualize - it mimics the the usual hand-written code (you don't repeat the instanceofs, you enclose them) - i believe that for the code generation, doing local decisions on each node is good enough, we do not need to propagate information in between nodes.

Yes, the current PR does not do reordering of cases. It could, I just didn't think of the rules too much in principle, and didn't want to make the patch overly complex or break something.

I guess I can visualize the AST nodes quite fine.

A bigger question\, I think\, is when it is safe to do so\, and when not\.
yes, not all re-ordering are safe, we need to keep some constraints. Fortunately, the ordering problems only arise when there are guards.

I think it is much more than (complex) guards. Like, for example:

record R(Object o) {}

interface I {}

case R(String s) -> {}

case I i -> {}

case R(Integer i) -> {}

Now, can we change the order of "I" and "R(Integer i)"? If we do and if we don't, the runtime behavior can differ in case of separate compilation when "R" is changed to implement "I".

But, even for:

final class A {}

final class B {}

case A a when ... -> {}

case B b -> {}

case A a -> {}

Can we change the order of the cases? I am not sure, because, again, with separate compilation, this can lead to a different outcome.

And maybe the answer is that we can do reordering in these cases. Or maybe we can in some of these cases, and can't in orders. I don't think this was ever discussed in depth.

Some of these decisions would be easier if we did the decision at runtime, of course. Which brings its own problems, as discussed elsewhere.

The idea is that for each node of the decision tree, you should generate the code in that order, first for the record pattern, then the code for the guards then the code for the type pattern, in that order.

The current PR first generates (an analog of) the instanceof of the record type, then code for the nested patterns, and then the guard of the case. Which allows to join the cases into nested switches (or ifs, if we go there). Not sure what is wrong with that?

Jan

If the guards are recorded in the same order as in the pattern matching (this is equivalent to say that the sort should be stable in term of guards), we should be ok.

As you said, the current spec allows to freely mix type patterns and type pattern + guard pattern with the same type, this has to be fixed at the spec level. I think it's reasonable to introduce an order between the type pattern + guard pattern and the type pattern on the same type, because it's more readable and because we do not want users to care to much about the order of the patterns to get good performance. You should get good performance by default, and not have to crawle StackOverflow to learn the arcane of finding the "right order" for patterns.

R?mi

-------------- next part -------------- An HTML attachment was scrubbed... URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20220807/2a71ec82/attachment-0001.htm>

Aug 07 '22 10:08 mlbridge[bot]

Mailing list message from Jan Lahoda on compiler-dev:

On 07. 08. 22 10:19, forax at univ-mlv.fr wrote:

[...]

    \"provide new bindings\" \=> do you have an example of that \?


Sure\:

public class TA \{
\?\?\?public static void main\(String\.\.\. args\) \{
\?\?\?\?\?\?\?Object o \= new Box\(\"\"\)\;
\?\?\?\?\?\?\?switch \(o\) \{
\?\?\?\?\?\?\?\?\?\?\?case Box b when b\.o\(\) instanceof String s \->
System\.err\.println\(s\)\;
\?\?\?\?\?\?\?\?\?\?\?default \-> \{\}
\?\?\?\?\?\?\?\}
\?\?\?\}
\?\?\?record Box\(Object o\) \{\}
\}


\(There can be any number of new bindings from the guard\, of course\.\)


    I don\'t think a guard should be allowed to do that\. It looks like a big gunfoot to me\.


I believe the current specification supports guards that introduce
new bindings\:

http\:\/\/cr\.openjdk\.java\.net\/\~gbierman\/jep427\%2b405\/jep427\+405\-20220601\/specs\/patterns\-switch\-record\-patterns\-jls\.html\#jls\-6\.3\.4


To me\, it seems desirable\. In any case\, an implementation PR is
probably not very well suited to discuss opinions on what should
be specced\. In particular \(but not only\) a PR that is not expected
to change the semantics\.

Ok, thanks for the example, it means we should lift the when expression not has a static method but as a static pattern method, something which will be more clear when we will have a better idea about how to do that once user defined pattern method like Optional.of(value -> ...) will be introduced.

Which I guess leaves as with a question: what are we going to do until user patterns are defined. Do we keep the current slow code, or do we try to improve that (which is that this PR is trying to do)? (And maybe learn something in the process.)

Jan

R?mi

-------------- next part -------------- An HTML attachment was scrubbed... URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20220807/7326a6cc/attachment.htm>

Aug 07 '22 10:08 mlbridge[bot]

Mailing list message from forax at univ-mlv.fr on compiler-dev:

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: Sunday, August 7, 2022 11:22:28 AM Subject: Re: [External] : Re: RFR: 8291769: Translation of switch with record patterns could be improved

On 07. 08. 22 10:19, [ mailto:forax at univ-mlv.fr | forax at univ-mlv.fr ] wrote:

[...]

"provide new bindings" => do you have an example of that ?

Sure:

public class TA { public static void main(String... args) { Object o = new Box(""); switch (o) { case Box b when b.o() instanceof String s -> System.err.println(s); default -> {} } } record Box(Object o) {} }

(There can be any number of new bindings from the guard, of course.)

I don't think a guard should be allowed to do that. It looks like a big gunfoot to me.

I believe the current specification supports guards that introduce new bindings:

[ http://cr.openjdk.java.net/~gbierman/jep427%2b405/jep427+405-20220601/specs/patterns-switch-record-patterns-jls.html#jls-6.3.4 | http://cr.openjdk.java.net/~gbierman/jep427%2b405/jep427+405-20220601/specs/patterns-switch-record-patterns-jls.html#jls-6.3.4 ]

To me, it seems desirable. In any case, an implementation PR is probably not very well suited to discuss opinions on what should be specced. In particular (but not only) a PR that is not expected to change the semantics. Ok, thanks for the example, it means we should lift the when expression not has a static method but as a static pattern method, something which will be more clear when we will have a better idea about how to do that once user defined pattern method like Optional.of(value -> ...) will be introduced.

Which I guess leaves as with a question: what are we going to do until user patterns are defined. Do we keep the current slow code, or do we try to improve that (which is that this PR is trying to do)? (And maybe learn something in the process.)

I'm ok with this PR but in the long term i hope we can make a better job. I still fear people re-organizing their patterns to get more performance instead of getting good performance out of the box.

Jan

R?mi

R?mi

-------------- next part -------------- An HTML attachment was scrubbed... URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20220808/a1ddf45d/attachment.htm>

Aug 09 '22 11:08 mlbridge[bot]

Mailing list message from forax at univ-mlv.fr on compiler-dev:

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: Sunday, August 7, 2022 11:17:16 AM Subject: Re: [External] : Re: RFR: 8291769: Translation of switch with record patterns could be improved

On 07. 08. 22 10:02, [ mailto:forax at univ-mlv.fr | forax at univ-mlv.fr ] wrote:

From: "jan lahoda" [ mailto:jan.lahoda at oracle.com | <jan.lahoda at oracle.com> ] To: "Remi Forax" [ mailto:forax at univ-mlv.fr | <forax at univ-mlv.fr> ] Cc: "Jan Lahoda" [ mailto:jlahoda at openjdk.org | <jlahoda at openjdk.org> ] , "Brian Goetz" [ mailto:brian.goetz at oracle.com | <brian.goetz at oracle.com> ] , "compiler-dev" [ mailto:compiler-dev at openjdk.org | <compiler-dev at openjdk.org> ] Sent: Friday, August 5, 2022 11:54:05 PM Subject: Re: [External] : Re: RFR: 8291769: Translation of switch with record patterns could be improved

On 05. 08. 22 22:52, [ mailto:forax at univ-mlv.fr | forax at univ-mlv.fr ] wrote:

[...]

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$ | 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.

I agree.

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.

You need the intermediary structure when the common prefix are not subsequent

case A(B b) -> case B(A a) -> case A(C c) ->

Here the first and the last case shares a common prefix.

Sorry, but I don't see why I can't do this particular thing without a specialized intermediate representation. The patterns are a partial orders, because we can optimize the ones with a common prefix, we need a sort, a decision tree is equivalent to a sort. There are several advantages to use a decision tree instead of a sort, - it's easier to visualize - it mimics the the usual hand-written code (you don't repeat the instanceofs, you enclose them) - i believe that for the code generation, doing local decisions on each node is good enough, we do not need to propagate information in between nodes.

Yes, the current PR does not do reordering of cases. It could, I just didn't think of the rules too much in principle, and didn't want to make the patch overly complex or break something.

I guess I can visualize the AST nodes quite fine.

A bigger question, I think, is when it is safe to do so, and when not. yes, not all re-ordering are safe, we need to keep some constraints. Fortunately, the ordering problems only arise when there are guards.

I think it is much more than (complex) guards. Like, for example:

record R(Object o) {}

interface I {}

case R(String s) -> {}

case I i -> {}

case R(Integer i) -> {}

Now, can we change the order of "I" and "R(Integer i)"? If we do and if we don't, the runtime behavior can differ in case of separate compilation when "R" is changed to implement "I".

But, even for:

final class A {}

final class B {}

case A a when ... -> {}

case B b -> {}

case A a -> {}

Can we change the order of the cases? I am not sure, because, again, with separate compilation, this can lead to a different outcome.

I think we are switching subject and entering into the "what guarantee we should provide to user with respect to separate compilation ?".

One problem i see is that in practice it is likely that the definition of the data have changed but the patterns have not be recompiled so the patterns are now wrongs. (Pattern Matching is about data oriented programming, where data definition are more important than the algorithms/computation on the data)

So perfectly executing a stale list of patterns is not that useful in my opinion.

And maybe the answer is that we can do reordering in these cases. Or maybe we can in some of these cases, and can't in orders. I don't think this was ever discussed in depth.

i agree it should be discussed more.

Some of these decisions would be easier if we did the decision at runtime, of course. Which brings its own problems, as discussed elsewhere.

I'm not even sure that it's easier at runtime because of erasure, patterns are correctly typecked or not depending on the types, but at runtime we only have class with the generic information erased, so apart if we decide to fully duplicate the whole typechecking done at compile time to redo it at runtime, the information we have at runtime does not help us that much.

The idea is that for each node of the decision tree, you should generate the code in that order, first for the record pattern, then the code for the guards then the code for the type pattern, in that order.

The current PR first generates (an analog of) the instanceof of the record type, then code for the nested patterns, and then the guard of the case. Which allows to join the cases into nested switches (or ifs, if we go there). Not sure what is wrong with that?

It's not wrong, but by only merging subsequent patterns you are creating an arcane knowledge of writing the patterns "the right way" to get more performance. It's not really an issue now because record patterns are still a preview feature but it's a serious issue in the long run.

R?mi -------------- next part -------------- An HTML attachment was scrubbed... URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20220809/dcd910f6/attachment-0001.htm>

Aug 09 '22 11:08 mlbridge[bot]

Mailing list message from Jan Lahoda on compiler-dev:

On 09. 08. 22 0:05, forax at univ-mlv.fr wrote:

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

\*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\: \*Sunday\, August 7\, 2022 11\:17\:16 AM
\*Subject\: \*Re\: \[External\] \: Re\: RFR\: 8291769\: Translation of
switch with record patterns could be improved

On 07\. 08\. 22 10\:02\, forax at univ\-mlv\.fr wrote\:



    \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-

        \*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\: \*Friday\, August 5\, 2022 11\:54\:05 PM
        \*Subject\: \*Re\: \[External\] \: Re\: RFR\: 8291769\: Translation
        of switch with record patterns could be improved

        On 05\. 08\. 22 22\:52\, forax at univ\-mlv\.fr wrote\:

            \[\.\.\.\]

                        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\.

            I agree\.

                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\.

            You need the intermediary structure when the common prefix are not subsequent

            case A\(B b\) \->
            case B\(A a\) \->
            case A\(C c\) \->

            Here the first and the last case shares a common prefix\.


        Sorry\, but I don\'t see why I can\'t do this particular
        thing without a specialized intermediate representation\.


    The patterns are a partial orders\, because we can optimize the
    ones with a common prefix\, we need a sort\, a decision tree is
    equivalent to a sort\.
    There are several advantages to use a decision tree instead of
    a sort\,
    \- it\'s easier to visualize
    \- it mimics the the usual hand\-written code \(you don\'t repeat
    the instanceofs\, you enclose them\)
    \- i believe that for the code generation\, doing local
    decisions on each node is good enough\, we do not need to
    propagate information in between nodes\.


Yes\, the current PR does not do reordering of cases\. It could\, I
just didn\'t think of the rules too much in principle\, and didn\'t
want to make the patch overly complex or break something\.


I guess I can visualize the AST nodes quite fine\.



        A bigger question\, I think\, is when it is safe to do so\,
        and when not\.


    yes\, not all re\-ordering are safe\, we need to keep some
    constraints\. Fortunately\, the ordering problems only arise
    when there are guards\.


I think it is much more than \(complex\) guards\. Like\, for example\:

record R\(Object o\) \{\}

interface I \{\}


case R\(String s\) \-> \{\}

case I i \-> \{\}

case R\(Integer i\) \-> \{\}


Now\, can we change the order of \"I\" and \"R\(Integer i\)\"\? If we do
and if we don\'t\, the runtime behavior can differ in case of
separate compilation when \"R\" is changed to implement \"I\"\.


But\, even for\:

final class A \{\}

final class B \{\}


case A a when \.\.\. \-> \{\}

case B b \-> \{\}

case A a \-> \{\}


Can we change the order of the cases\? I am not sure\, because\,
again\, with separate compilation\, this can lead to a different
outcome\.

I think we are switching subject and entering into the "what guarantee we should provide to user with respect to separate compilation ?".

I don't think this is switching subject. This is still the same question: when it is safe to change the order the cases.

One problem i see is that in practice it is likely that the definition of the data have changed but the patterns have not be recompiled so the patterns are now wrongs. (Pattern Matching is about data oriented programming, where data definition are more important than the algorithms/computation on the data)

So perfectly executing a stale list of patterns is not that useful in my opinion.

As I said - it is possible the answer is that we can reorder the cases in situations like this. But that's not a decision that should be made in an implementation PR.

And maybe the answer is that we can do reordering in these cases\.
Or maybe we can in some of these cases\, and can\'t in orders\. I
don\'t think this was ever discussed in depth\.
i agree it should be discussed more.
Some of these decisions would be easier if we did the decision at
runtime\, of course\. Which brings its own problems\, as discussed
elsewhere\.
I'm not even sure that it's easier at runtime because of erasure, patterns are correctly typecked or not depending on the types, but at runtime we only have class with the generic information erased, so apart if we decide to fully duplicate the whole typechecking done at compile time to redo it at runtime, the information we have at runtime does not help us that much.
    The idea is that for each node of the decision tree\, you
    should generate the code in that order\, first for the record
    pattern\, then the code for the guards then the code for the
    type pattern\, in that order\.


The current PR first generates $an analog of$ the instanceof of
the record type\, then code for the nested patterns\, and then the
guard of the case\. Which allows to join the cases into nested
switches $or ifs\, if we go there$\. Not sure what is wrong with that\?
It's not wrong, but by only merging subsequent patterns you are creating an arcane knowledge of writing the patterns "the right way" to get more performance.

As I've said several times, the current patch allows case reordering, but it is not clear which reorderings are safe, so it is not doing them. The implementation wouldn't be too difficult, I believe: while accummulating cases for a primary type X, when looking at case for a different primary type Y, we can evaluate whether it is fine to skip the current case, and if yes, we would continue and evaluate the next case. The most difficult part here is to decide which reordering is safe and which is not.

Overall, I am much more worried about not introducing a wrong behavior. We've been changing translations of various constructs in the past, while keeping behavior, and while that is not ideal, it was not that much problematic either. We've made changes to String concatenation and try-with-resources, for example. Fixing broken behavior is likely to be much more difficult.

Jan

It's not really an issue now because record patterns are still a preview feature but it's a serious issue in the long run.

R?mi

-------------- next part -------------- An HTML attachment was scrubbed... URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20220809/08805cb6/attachment-0001.htm>

Aug 09 '22 11:08 mlbridge[bot]

just curious: is there any performance degradation in the compilation time while compiling long test cases?

Aug 11 '22 18:08 vicente-romero-oracle

just curious: is there any performance degradation in the compilation time while compiling long test cases?

I tried with a switch with 512+1 cases (record pattern for triplet, with nested record patterns for triplets), and on an informal test, the time seems to be roughly the same with and without this patch. (The switch is too big for a classfile without this patch, so the compilation fails during code generation without this patch.)

Aug 12 '22 08:08 lahodaj

just curious: is there any performance degradation in the compilation time while compiling long test cases?

I tried with a switch with 512+1 cases (record pattern for triplet, with nested record patterns for triplets), and on an informal test, the time seems to be roughly the same with and without this patch. (The switch is too big for a classfile without this patch, so the compilation fails during code generation without this patch.)

nice, thanks

Aug 12 '22 13:08 vicente-romero-oracle

side, although not related to this patch I think that the parser generated error messages the compiler issues for code like:

record Box(Object... o) {}

class Test {

    private int test(Object obj) {
        return switch (obj) {
            case Box(String... s) -> 0;
            default -> -1;
        };
    }
}

could be improved. I'm not suggesting this to be fixed as part of this patch though.

Aug 12 '22 20:08 vicente-romero-oracle

@lahodaj this pull request can not be integrated into master due to one or more merge conflicts. To resolve these merge conflicts and update this pull request you can run the following commands in the local repository for your personal fork:

git checkout JDK-8291769
git fetch https://git.openjdk.org/jdk master
git merge FETCH_HEAD
# resolve conflicts and follow the instructions given by git merge
git commit -m "Merge master"
git push

Sep 01 '22 18:09 openjdk[bot]

not strictly related to this patch but for this code:

record Box(Object o) {}

class Test {
    private int test(Object obj) {
        return switch (obj) {
            case Box(String s) -> 0;
            case Box(Integer i) -> 0;
            case Box(Number n) -> 0;
            case Box(CharSequence cs) -> 0;

            default -> -1;
        };
    }
}

after compiling it without the preview options set as in: javac Test.java, javac issues two errors in the same line:

Test.java:6: error: patterns in switch statements are a preview feature and are disabled by default.
            case Box(String s) -> 0;
                 ^
  (use --enable-preview to enable patterns in switch statements)
Test.java:6: error: deconstruction patterns are a preview feature and are disabled by default.
            case Box(String s) -> 0;
                    ^
  (use --enable-preview to enable deconstruction patterns)
2 errors

Sep 27 '22 20:09 vicente-romero-oracle

another side comment but given that we are retouching this code, I'm seeing that TransPatterns is a phase that is run always regardless of the presence or not of patterns. Shouldn't we do something similar as for LambdaToMethod that is executed only if there are lambdas? Of course there is no need to address this as part of this patch

Sep 27 '22 23:09 vicente-romero-oracle

@lahodaj This change now passes all automated pre-integration checks.

ℹ️ This project also has non-automated pre-integration requirements. Please see the file CONTRIBUTING.md for details.

After integration, the commit message for the final commit will be:

8291769: Translation of switch with record patterns could be improved

Reviewed-by: vromero

You can use pull request commands such as /summary, /contributor and /issue to adjust it as needed.

At the time when this comment was updated there had been 25 new commits pushed to the master branch:

1b924659c87045796f62e66d69ff388b79c4467f: 8297608: JFR: Incorrect duration after chunk rotation
6065696e5df2cde8c313083217ead3417d04c365: 8297982: Exclude vmTestbase/nsk/monitoring/stress/lowmem/ with ZGC until 8297979 is fixed
415cfd2e28e6b7613712ab63a1ab66522e9bf0f2: 8297285: Shenandoah pacing causes assertion failure during VM initialization
df072556a5a155adfe89a2504c2cf680fe4ffac7: 8297984: Turn on warnings as errors for javadoc
227364d5927f94764fdb84f7d0b4c88c8dc25d89: 8297953: Fix several C2 IR matching tests for RISC-V
1370228cd718736f0c822d50b85a0b27c8ca40de: 8297941: Add override modifier in space.hpp
319faa5afc37df5fd9ce4305e6e38a7bd4b39c65: 8296084: javax/swing/JSpinner/4788637/bug4788637.java fails intermittently on a VM
b73363fd7b3295635a2ccce0cea72586643c5bb4: 8297686: JFR: Improve documentation of EventStream::onMetadata(Consumer)
1376f330119c832d24a986cc915cb2f82768a02c: 8297911: Memory leak in JfrUpcalls::on_retransform
5c0ff26f321ad36daa34bfc5b2d013b6c4a03810: 8291444: GHA builds/tests won't run manually if disabled from automatic running
... and 15 more: https://git.openjdk.org/jdk/compare/9f94cbec51df7556d34fffa810e59dd9eb8521df...master

As there are no conflicts, your changes will automatically be rebased on top of these commits when integrating. If you prefer to avoid this automatic rebasing, please check the documentation for the /integrate command for further details.

➡️ To integrate this PR with the above commit message to the master branch, type /integrate in a new comment.

Sep 30 '22 15:09 openjdk[bot]

@lahodaj This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!

Nov 10 '22 21:11 bridgekeeper[bot]

jdk jdk copied to clipboard

8291769: Translation of switch with record patterns could be improved

Progress

Issue

Reviewers

Reviewing

Webrevs

jdk
jdk copied to clipboard