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

[Guy Steele]

Yes, I should have not used the word “refactoring”; I should have said “rewrite (to a form that may or may not be equivalent with respect to side effects)”.

The point is that the programmer gets final approval over the form of the code.

You cannot always refactor `y = User.foo(x)*User.foo(x);` into `z = User.foo(x); y = z*z;` but it’s the sort of rewriting that a savvy user )with an appropriate understanding of whether side effects are relevant) may choose to do.  I argue that the use of patterns is similar.

And I agree that the presence of guards may make it more difficult, or impossible, to perform such a relatively simple rewriting.  All I meant to say is:

	* Such rewritings are available in simple cases that may be very common
	* The programmer (who may have access to knowledge that the compiler does not) may need to judge whether such a rewriting is valid in a specific context
	* In any case, such tricks are probably needed only when performance is critical (and otherwise it is preferable not to engage in such micromanagement)

> On Feb 1, 2021, at 2:59 PM, Alan Malloy <amalloy at google.com> wrote:
> 
> You have to be careful with that refactoring, because it isn't obvious how to make it work with guards / and-patterns. Suppose I write:
> 
> switch (x) {
>   case Foo(int y) & true(y == 1): ...
>   case Foo(int y) & true(y == 2): ...
>   case Object o: ... // could be a Foo with a different y
> }
> 
> It's important that fallthrough is preserved from the first two cases into the third, which you won't trivially have if you refactor into a nested switch. You could get there with the "continue" notion for imperatively setting up explicit fallback - this was discussed some time ago but I'm not sure it's still part of the plan. Even so, it gets complicated to do this, especially if you need to nest patterns more than one level deep.
> 
> On Mon, Feb 1, 2021 at 11:47 AM Guy Steele <guy.steele at oracle.com <mailto:guy.steele at oracle.com>> wrote:
> 
> 
> > On Feb 1, 2021, at 8:57 AM, Brian Goetz <brian.goetz at oracle.com <mailto:brian.goetz at oracle.com>> wrote:
> > 
> > 
> >> 
> >> 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.
> > 
> > 
> > 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.
> 
> And let’s also keep in mind that if we have the “dumb and predictable thing” as a baseline, then, after all, the programmer also has some control over the situation: if performance of
> 
>     case Foo(A a):
>     case Foo(B b):
>     case Bar(C c):
>     case Bar(D d):
>     case Wooga(E e):
> 
> is not satisfactory because it’s a Foo 99% of the time (that’s why the Foo cases were listed firs, after all?!), then the switch can easily be refactored (with IDE assistance?) to either
> 
>     case Foo z:
>         switch (z) {
>             case Foo(A a):
>             case Foo(B b):
>         }
>     case Bar z:
>         switch (z) {
>             case Bar(C c):
>             case Bar(D d):
>         }
>     case Wooga z:
>         switch (z) {
>             case Wooga(E e):
>         }
> 
> (which works in the general case where patterns may have more than one argument) or
> 
>     case Foo(var z):
>         switch (z) {
>             case A a:
>             case B b:
>         }
>     case Bar(var z):
>         switch (z) {
>             case C c:
>             case D d:
>         }
>     case Wooga(var z):
>         switch (z) {
>             case E e:
>         }
> 
> (which is more concise in this specific case), and in fact the three styles can be mixed if you want:
> 
>     case Foo z:
>         switch (z) {
>             case Foo(A a):
>             case Foo(B b1, B b2):
>         }
>     case Bar(var z):
>         switch (z) {
>             case C c:
>             case D d:
>         }
>     case Wooga(E e):
> 
> Thus the programmer can always micromanage the dispatch structure if performance is an issue.  And the performance model for the baseline approach is pretty straightforward and should be easy to understand.
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.java.net/pipermail/amber-spec-experts/attachments/20210201/aada53da/attachment-0001.htm>