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

[Adam Sotona]

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

I did several experiments with generated lookupswitch over class hashes (for final and sealed class labels only).
My experiments and benchmark results are actually showing following facts:
- traversal expanded to tableswitch (as proposed here) is significantly faster than circulating over an array
- expanded lookupswitch over class hashes is unfortunately slower than this proposal, even when benchmarked on large switches containing final or sealed class labels only

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

Marked as reviewed by asotona (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/9779#pullrequestreview-1424836407