RFR: 8319220: Pattern matching switch with a lot of cases is unduly slow

[Jan Lahoda]

On Fri, 3 Nov 2023 08:51:48 GMT, Adam Sotona <asotona at openjdk.org> wrote:

>> Consider code like:
>> 
>> void test(Object o) {
>>     switch (o) {
>>         case X1 -> {}
>>         case X2 -> {}
>> ...(about 100 cases)
>> ``` 
>> 
>> javac will compile the switch into a switch whose selector is an indy invocation to `SwitchBootstraps.typeSwitch`, with static arguments being the types in the cases.
>> 
>> `SwitchBootstraps.typeSwitch` will then create a chain of `MethodHandle`s performing `instanceof` checks between the switch's selector and the given case type. The problem is that when the number of cases is high enough, (more than ~40-50), the chain gets too long, and the tests won't inline anymore. This then leads to a very bad performance, when compared to manually written if-instanceof-else-if-instanceof- chain.
>> 
>> The proposal herein is to use bytecode (written using the ClassFile API/library) instead of the `MethodHandle`s chain. The overall performance of this seems to be similar to the manually written if-instanceof-else-if-instanceof- chain.
>> 
>> Using the benchmark from the bug, and this patch, I am getting:
>> 
>> MyBenchmark.testIfElse100  thrpt    5  521826.326 ± 7510.042  ops/s
>> MyBenchmark.testSwitch100  thrpt    5  505440.170 ± 3757.178  ops/s
>> 
>> 
>> The most tricky part of this new way to generate the tests is handling of non-type case labels, and in particular cases with enum constant labels. The resolution of enum constants is deferred as much as possible, by using an indirection through the `ResolvedEnumLabels`.
>> 
>> Further improvements may be possible, esp. for some specific cases (like all cases having a type, and the type being a final class).
>
> src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 393:
> 
>> 391:                             cb.constantInstruction(0)
>> 392:                               .ireturn();
>> 393:                         }
> 
> Isn't this generating a dead code for labels.length == 0 ?

Right, it does (did). Fixed. Thanks!

> src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java line 415:
> 
>> 413:                             switchCases.add(SwitchCase.of(idx, target));
>> 414:                         }
>> 415:                         cases = cases.reversed();
> 
> switchCases for tableswitch do not need to be pre-ordered, code builder does the processign

I guess I would prefer to keep the reverse here, to reduce the cognitive load, as `cases` must be processed in original order (and hence reversed here), and it may not be clear why reverse one, and not the other. (Given the `List` is an `ArrayList`, the reverse operation should not have much impact on anything, if I read how it is implemented correctly.)

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

PR Review Comment: https://git.openjdk.org/jdk/pull/16489#discussion_r1381330275
PR Review Comment: https://git.openjdk.org/jdk/pull/16489#discussion_r1381393396