[External] : Re: Semantics of multiple patterns with the same prefix in a switch

[forax at univ-mlv.fr]

----- Mail original -----
> De: "Brian Goetz" <brian.goetz at oracle.com>
> À: "Remi Forax" <forax at univ-mlv.fr>, "Guy Steele" <guy.steele at oracle.com>
> Cc: "amber-spec-experts" <amber-spec-experts at openjdk.java.net>
> Envoyé: Lundi 1 Février 2021 14:57:40
> Objet: Re: [External] : Re: Semantics of multiple patterns with the same prefix in a switch

>>
>> I fully agree, whatever we decide, the order should be left-to-right.
>>
>> Given that the VMs/JITs are already able to share common sub
>> expressions if a method can be inlined and there is no side effect,
>> and that allowing optimizations to maybe occur is not WORA.
>>
>> I see two possible semantics,
>>   - either the compiler and runtime metafactory do not share of the
>> computation of the same pattern (the VM/JIT still can)
>>   - or we allow the computation of patterns with the same prefix (to
>> keep the left-to-right order) to be shared even if they are maybe side
>> effects.
>>     "With the same prefix" meaning that the patterns on the left that
>> share the same surface syntax will share the same computation results.
>>
>> In the first case, we only rely on the VM/JIT magic, in the other
>> case, we hope that no sane user will write a pattern method with side
>> effect.
>>
>> So said differently, does the second proposed semantics make sense or
>> is too clever ?
> 
> Let's posit that it is "clever" (maybe just enough, maybe too much), and
> evaluate the other side of the equation: what's the benefit?
> 
> Clearly, if I have a 27-case switch statement:
> 
>     case Foo(A a):
>     case Foo(B b):
>     ...
>     case Foo(Z z):
>     default:
> 
> then there is some benefit.  And surely this will describe _some_ switch
> statements.  But, will it describe a lot of them?  Or are we more likely
> to see things like:
> 
>     case Foo(A a):
>     case Foo(B b):
>     case Bar(C c):
>     case Bar(D d):
>     case Wooga(E e):
> 
> in which "case" we will not see all that much benefit by optimizing away
> a stray invocation in the second and fourth cases.
> 
> Where I think the lion's share of the optimization opportunity here is
> trying to prune cases based on the head type.  If, for example, we know
> that it's a Foo, then cases 3,4,5 can be known to not apply, and if we
> fail to match cases 1 or 2, we're done (or we fall into the default.)  I
> think exposing these optimizations -- which have the chance to reduce
> O(n) switch dispatch into O(1) -- is where the highest leverage is.

yes, being able to switch on type in O(1) or O(ln) is the first optimization that should be done (with the one that uses few ifs because they are very few possible classes (2 or 3 if sealed from my own experience)),
that why we are first introducing the switch on type with no deconstructor in a first phase and add deconstructors and more patterns in a second phase.

> 
> 
> Given that, my proposal is:
>  - Let's take as a baseline that we're going to do the dumb and
> predictable thing, for now
>  - Work on our translation strategy and see how much we can squeeze out
> just based on the easy stuff
>  - Evaluate how much incrementally the "clever head" strategy would buy;
>  - Evaluate how much incrementally the "if the user does side-effects
> in a pattern, it's their own fault" approach would buy.

I don't see the "clever head" (as you call it) as an optimization but more has the way people constructs a switch with patterns in their head, if the object starts with Foo it can be a A or a B after.
For me, it's more a semantics issue than an optimization issue if you prefer.

Rémi