RFR: 8291966: SwitchBootstrap.typeSwitch could be faster [v2]

[Rémi Forax]

On Tue, 17 Jan 2023 15:55:40 GMT, Jan Lahoda <jlahoda at openjdk.org> wrote:

>> 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>;
>>                     }
>> 
>> 
>> This appear to run faster than the current implementation, using testcase similar to the one used for https://github.com/openjdk/jdk/pull/9746 , these are the results
>> 
>> PatternsOptimizationTest.testLegacyIndyLongSwitch   thrpt   25   1515989.562 ± 32047.918  ops/s
>> PatternsOptimizationTest.testHandleIndyLongSwitch   thrpt   25   2630707.585 ± 37202.210  ops/s
>> 
>> PatternsOptimizationTest.testLegacyIndyShortSwitch  thrpt   25   6789310.900 ± 61921.636  ops/s
>> PatternsOptimizationTest.testHandleIndyShortSwitch  thrpt   25  10771729.464 ± 69607.467  ops/s
>> 
>> 
>> The "LegacyIndy" is the current implementation, "HandleIndy" is the one proposed here. The translation in javac used is the one from #9746 in all cases.
>
> Jan Lahoda has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains four additional commits since the last revision:
> 
>  - Adding comments
>  - Improving performance
>  - Merge branch 'master' into JDK-8291966
>  - 8291966: SwitchBootstrap.typeSwitch could be faster

Also there is a lot of use cases where the type switch is called only with instances of the same class, for those scenarii, the VM should be able to fully remove the type switch and inline the body of the corresponding case like this is done with a virtual call.

I don't think there is a way currently to explain to the VM that the a hash map really acts as a cache so if the key is a constant then the value is a constant too (this optimization is also missing when JITing ClassValue.get()).

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

PR Comment: https://git.openjdk.org/jdk/pull/9779#issuecomment-1531526385