RFR: 8291966: SwitchBootstrap.typeSwitch could be faster

[Remi Forax]

----- Original Message -----
> From: "Jan Lahoda" <jlahoda at openjdk.org>
> To: "core-libs-dev" <core-libs-dev at openjdk.org>
> Sent: Friday, August 5, 2022 6:22:48 PM
> Subject: RFR: 8291966: SwitchBootstrap.typeSwitch could be faster

> The pattern matching switches are using a bootstrap method
> `SwitchBootstrap.typeSwitch` to implement the jumps in the switch. Basically,
> for a switch like:
> 
> switch (obj) {
>    case String s when s.isEmpty() -> {}
>    case String s -> {}
>    case CharSequence cs -> {}
>    ...
> }
> 
> 
> this method will produce a MethodHandle that will be analyze the provided
> selector value (`obj` in the example), and will return the case index to which
> the switch should jump. This method also accepts a (re)start index for the
> search, which is used to handle guards. For example, if the `s.isEmpty()` guard
> in the above sample returns false, the matching is restarted on the next case.
> 
> The current implementation is fairly slow, it basically goes through the labels
> in a loop. The proposal here is to replace that with a MethodHandle structure
> like this:
> 
> obj == null ? -1
>                  : switch (restartIndex) {
>                        case 0 -> obj instanceof String ? 0 : obj instanceof CharSequence ? 2 : ... ;
>                        case 1 -> obj instanceof String ? 1 : obj instanceof CharSequence ? 2 : ... ;
>                        case 2 -> obj instanceof CharSequence ? 2 : ... ;
>                        ...
>                        default -> <labels-count>;
>                    }

You only need restart index at the beginning and after a when, so in your example, only 0 and 1 are required, you can skip the generation of 2 because you will never restart at 2.

If you start to see the typeswitch as a bunch of method handles, i wonder if it's not better to lift any when expressions as a static methods (exactly like a lambda body) and then send them as constant method handles to the type switch so you do not need a restart index.

Anyway, i agree that it's a better translation than the existing one.

I think that in the end game, we will go to the same route as with the lambda proxy, the whole pattern matching with the when expressions as constant method handles will be send to one bootstrap method that will create an intermediary decision tree, generate the corresponding bytecode (using the classfile API) and load it as a hidden class. This provides a clean API separation between the compiler and the runtime that knows how to optimize pattern matching query. 

Rémi