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

[ExE Boss]

On Mon, 29 May 2023 07:25:26 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 pull request now contains six commits:
> 
>  - Reflecting review feedback.
>  - Merge branch 'master' into JDK-8291966
>  - Adding comments
>  - Improving performance
>  - Merge branch 'master' into JDK-8291966
>  - 8291966: SwitchBootstrap.typeSwitch could be faster

src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 340:

> 338:                                                                             createRepeatIndexSwitch(lookup, labels),
> 339:                                                                             MethodHandles.insertArguments(MAPPED_ENUM_LOOKUP, 1, lookup, enumClass, labels, new EnumMap())));
> 340:             target = MethodHandles.permuteArguments(body, MethodType.methodType(int.class, Object.class, int.class), 1, 0);

This `guardWithTest` does the opposite to what’s described in the above comment.

src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 389:

> 387:             }
> 388:         }
> 389:         return enumMap.map[value.ordinal()];

`enumMap.map` never gets set before this line.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1550058760
PR Review Comment: https://git.openjdk.org/jdk/pull/9779#discussion_r1550057327