RFR: 8263087: Add a MethodHandle combinator that switches over a set of MethodHandles

[Rémi Forax]

On Fri, 9 Apr 2021 19:57:10 GMT, Jorn Vernee <jvernee at openjdk.org> wrote:

>>> yes, for all the switches, pattern-switch, enum-switch but not for the string switch which requires a lookup switch.
>> Can you outline how to use the tableswitch combinator in the case of a switch on strings ?
>> 
>> Jan Lahoda has made several good examples of that: https://github.com/lahodaj/jdk/blob/switch-bootstrap/src/java.base/share/classes/java/lang/runtime/SwitchBootstraps.java i.e. several filtering strategies for translating a String into a table index (which can then be fed to `tableswitch`)
>> 
>> I ran some benchmarks:
>> 
>> ![results](http://cr.openjdk.java.net/~jvernee/StringSwitch_10.svg)
>> 
>> Here, 'legacy' is what C2 does with `lookupswitch`.
>> 
>> Maybe it's worth it to include such an example & benchmark in this patch as well (show off how to emulate `lookupswitch`)
>
> I've uploaded a benchmark that simulates a lookup switch using the tableSwitch combinator as well, using a HashMap lookup as a filter: https://github.com/openjdk/jdk/commit/a7157eb0ef1b7190aabfb2689539801c6692bbae
> 
> For that particular key set (the same as from the graph above), HashMap is faster:
> 
> Benchmark                                              Mode  Cnt   Score   Error  Units
> MethodHandlesEmulateLookupSwitch.emulatedLookupSwitch  avgt   30  19.450 � 0.079  ms/op
> MethodHandlesEmulateLookupSwitch.nativeLookupSwitch    avgt   30  25.370 � 0.159  ms/op
> 
> But, I've found it really depends on the key set. However, this is mostly to demonstrate that emulation can have competitive performance with native `lookupswitch`. e.g. to get constant folding for constant inputs another filter has to be used, since C2 can not see through the HashMap lookups.

Ok, let restart from the beginning,
you have two strategy to de-sugar a switch,
- if what you do after the case do not mutate any variables, you can desugar each case to a method more or less like a lambda (it's not exactly like a lambda because there is no capture) and you have an indy in front that will call the right method handles
- you have a front end, with an indy that associate the object to an int and a backend which is tableswitch in the bytecode

The first strategy is an optimization, it will get you good performance by example if you compare a switch on a hirerachy on types and the equivalent method call. But you can not use that strategy for all switch, it's more an optimization.
The second strategy let you encode any switches.

The tests above are using the first strategy, which I think is not what we should implement by default given that it doesn't work will all cases. In the particular case of a switch on string, javac generates two switches, the front one and the back one, if we want to compare, we should implement the second strategy, so indy or the equivalent constant handle should take a String as parameter and return an int.

On the test themselves, for the hash, the Map should be directly bound, it will be more efficient, the asm version doesn't not appear in the graphics and there is a missing strategy that is using a MutableCallSite to switch from the a cascade of guards using the real values (store the String value even if it goes to `default`) and then switch to a lookup switch which i've found is the optimal strategy in real code (it works a lot like a bi-morphic cache but on string values instead of on classes).

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

PR: https://git.openjdk.java.net/jdk/pull/3401