[External] : Re: RFR: 8263087: Add a MethodHandle combinator that switches over a set of MethodHandles

[John Rose]

On Apr 9, 2021, at 11:15 AM, forax at univ-mlv.fr wrote:
> 
> ----- Mail original -----
>> De: "John Rose" <john.r.rose at oracle.com>
>> À: "Remi Forax" <forax at univ-mlv.fr>
>> Cc: "Jorn Vernee" <jvernee at openjdk.java.net>, "core-libs-dev" <core-libs-dev at openjdk.java.net>
>> Envoyé: Vendredi 9 Avril 2021 20:01:18
>> Objet: Re: RFR: 8263087: Add a MethodHandle combinator that switches over a set of MethodHandles
> 
> Hi John,
> 
>> On Apr 9, 2021, at 9:55 AM, Remi Forax <forax at univ-mlv.fr> wrote:
>>> 
>>> I think the combinator should be lookupswitch which is more general than
>>> tableswitch with a special case when generating the bytecode to generate a
>>> tableswitch instead of a lookupswitch if the indexes are subsequent.
>> 
>> We can get there in the simpler steps Jorn has outlined.
> 
> I fail to see how it can work.

If you have a fixed set of N cases it is always valid
to number them compactly in [0,N).  If there is
another association of keys in some set K to cases,
then you simply build a mapping K → [0,N).  That
works for enums, lookupswitch, strings, and patterns.
The mapping functions would be:
  - Enum::ordinal
  - a lookupswitch of cases `case i: return n`, n in [0,N]
  - some perfect hash, composed with lookupswitch
  - some decision tree that outputs compact case numbers

In the second case, C2 will inline the lookupswitch and
tableswitch together and do branch-to-branch tensioning.
The result will be the same as if the intermediate tableswitch
had not been used.

The MH combinator for lookupswitch can use a data-driven
reverse lookup in a (frozen/stable) int[] array, using binary
search.  The bytecode emitter can render such a thing as
an internal lookupswitch, if that seems desirable.  But
the stable array with binary search scales to other types
besides int, so it’s the right primitive.

The SwitchBootstraps class is the place to match a
static decision tree or decision chain (of N cases) of
an arbitrary shape to compact case labels in [0,N).
Then they all feed to Jorn’s primitive.

> 
>> 
>> The combinator is much simpler if the case numbers are implicit in [0,N). Then
>> it’s natural to filter on the [0,N) input as a separately factored choice.
> 
> An array of MethodHandles + a default method handle is simpler than an array of sorted ints + an array of MethodHandles + a default method, but not much simpler.

Simpler by the complexity of the sorting, which is a sharp edge.
The type “sorted int array without duplicates and unaliased
or frozen” is pretty involved.  Easy to make mistakes with it.

> 
>> That also scales to pattern-switch.
> 
> yes, for all the switches, pattern-switch, enum-switch but not for the string switch which requires a lookup switch.

Nope; see above.

> Can you outline how to use the tableswitch combinator in the case of a switch on strings ?

Above; reduce to perfect hash plus lookupswitch
producing compact int values to feed to a tableswitch.

Summary:  Switches only need one case label domain:  [0,N).
Everything else is case label mappings.

— John