<html><head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<p>On 07. 08. 22 10:02, <a class="moz-txt-link-abbreviated" href="mailto:forax@univ-mlv.fr">forax@univ-mlv.fr</a> wrote:<br>
</p>
<blockquote type="cite" cite="mid:36794892.19552004.1659859352180.JavaMail.zimbra@u-pem.fr">
<div style="font-family: arial, helvetica, sans-serif; font-size:
12pt; color: #000000">
<div><br>
</div>
<div><br>
</div>
<hr id="zwchr" data-marker="__DIVIDER__">
<div data-marker="__HEADERS__">
<blockquote style="border-left:2px solid
#1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><b>From:
</b>"jan lahoda" <a class="moz-txt-link-rfc2396E" href="mailto:jan.lahoda@oracle.com"><jan.lahoda@oracle.com></a><br>
<b>To: </b>"Remi Forax" <a class="moz-txt-link-rfc2396E" href="mailto:forax@univ-mlv.fr"><forax@univ-mlv.fr></a><br>
<b>Cc: </b>"Jan Lahoda" <a class="moz-txt-link-rfc2396E" href="mailto:jlahoda@openjdk.org"><jlahoda@openjdk.org></a>, "Brian
Goetz" <a class="moz-txt-link-rfc2396E" href="mailto:brian.goetz@oracle.com"><brian.goetz@oracle.com></a>, "compiler-dev"
<a class="moz-txt-link-rfc2396E" href="mailto:compiler-dev@openjdk.org"><compiler-dev@openjdk.org></a><br>
<b>Sent: </b>Friday, August 5, 2022 11:54:05 PM<br>
<b>Subject: </b>Re: [External] : Re: RFR: 8291769:
Translation of switch with record patterns could be improved<br>
</blockquote>
</div>
<div data-marker="__QUOTED_TEXT__">
<blockquote style="border-left:2px solid
#1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;">
<p>On 05. 08. 22 22:52, <a class="moz-txt-link-abbreviated
moz-txt-link-freetext" href="mailto:forax@univ-mlv.fr" target="_blank" moz-do-not-send="true">forax@univ-mlv.fr</a>
wrote:<br>
</p>
<blockquote cite="mid:1724934379.19079517.1659732755546.JavaMail.zimbra@u-pem.fr">
<pre class="moz-quote-pre">[...]
</pre>
<blockquote>
<blockquote>
<blockquote>
<pre class="moz-quote-pre">In any case, I'm a bit afraid that we could enhance a translation patch
forever, always adding new cases that can be optimized. So, I think we
need to draw a line somewhere where the patch provides a benefit while
still being testable and reviewable. With a possible separate
improvements, if they prove to be useful. It is possible I haven't drawn
the line far enough, but looking at the patch, it seems complex enough.
</pre>
</blockquote>
<pre class="moz-quote-pre">I think the issue is that a list of pattern is not the right intermediary
structure to try to optimize the pattern matching, a decision tree is a better
intermediary representation (this is how pattern matching is usually optimized,
i've not invented something new :) )
Here is an example of such decision tree:
<a class="moz-txt-link-freetext" href="https://urldefense.com/v3/__https://github.com/forax/switch-pattern-combinator__;!!ACWV5N9M2RV99hQ!JevAQE8IkRf4n-BMKA2sMTNFfJ5sAyJ1xopR2O9rq_45-xqaHOgirecR8E4zIGB_RgMb27G3tlcHEuGADjk$" target="_blank" moz-do-not-send="true">https://urldefense.com/v3/__https://github.com/forax/switch-pattern-combinator__;!!ACWV5N9M2RV99hQ!JevAQE8IkRf4n-BMKA2sMTNFfJ5sAyJ1xopR2O9rq_45-xqaHOgirecR8E4zIGB_RgMb27G3tlcHEuGADjk$</a>
</pre>
</blockquote>
<pre class="moz-quote-pre">I am not really opposed to having an intermediate structure, but I think
the overall cost of the structure is likely to be significant, and it
should provide significantly better code to offset that.
</pre>
</blockquote>
<pre class="moz-quote-pre">I agree.
</pre>
<blockquote>
<pre class="moz-quote-pre">Looking at the page, I see:
The advantage of a decision tree is that if two patterns have a common
prefix, the code for the common prefix is generated only once.
I wonder if there's a *conceptual* difference between what this PR is
doing and what your code is doing. The PR here is trying to take common
prefixes (of viable cases) and generate code for them only once. I don't
think that not optimizing
case A(String s) -> {}
case A a -> {}
is a conceptual difference, but if this is something that is seen as
critical, I am fairly sure I can implement that without creating a brand
new structure and code to convert the AST into it and back.
</pre>
</blockquote>
<pre class="moz-quote-pre">You need the intermediary structure when the common prefix are not subsequent
case A(B b) ->
case B(A a) ->
case A(C c) ->
Here the first and the last case shares a common prefix. </pre>
</blockquote>
<p><br>
</p>
<p>Sorry, but I don't see why I can't do this particular
thing without a specialized intermediate representation. </p>
</blockquote>
<div><br>
</div>
<div>The patterns are a partial orders, because we can
optimize the ones with a common prefix, we need a sort, a
decision tree is equivalent to a sort.</div>
<div>There are several advantages to use a decision tree
instead of a sort,<br data-mce-bogus="1">
</div>
<div>- it's easier to visualize<br data-mce-bogus="1">
</div>
<div>- it mimics the the usual hand-written code (you don't
repeat the instanceofs, you enclose them)</div>
<div>- i believe that for the code generation, doing local
decisions on each node is good enough, we do not need to
propagate information in between nodes.<br data-mce-bogus="1">
</div>
</div>
</div>
</blockquote>
<p><br>
</p>
<p>Yes, the current PR does not do reordering of cases. It could, I
just didn't think of the rules too much in principle, and didn't
want to make the patch overly complex or break something.</p>
<p><br>
</p>
<p>I guess I can visualize the AST nodes quite fine.<br>
</p>
<p><br>
</p>
<blockquote type="cite" cite="mid:36794892.19552004.1659859352180.JavaMail.zimbra@u-pem.fr">
<div style="font-family: arial, helvetica, sans-serif; font-size:
12pt; color: #000000">
<div data-marker="__QUOTED_TEXT__">
<div><br data-mce-bogus="1">
</div>
<blockquote style="border-left:2px solid
#1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;">
<p>A bigger question, I think, is when it is safe to do so,
and when not.</p>
</blockquote>
<div><br>
</div>
<div>yes, not all re-ordering are safe, we need to keep some
constraints. Fortunately, the ordering problems only arise
when there are guards.<br data-mce-bogus="1">
</div>
</div>
</div>
</blockquote>
<p><br>
</p>
<p>I think it is much more than (complex) guards. Like, for example:</p>
<p>record R(Object o) {}</p>
<p>interface I {}</p>
<p><br>
</p>
<p>case R(String s) -> {}</p>
<p>case I i -> {}</p>
<p>case R(Integer i) -> {}</p>
<p><br>
</p>
<p>Now, can we change the order of "I" and "R(Integer i)"? If we do
and if we don't, the runtime behavior can differ in case of
separate compilation when "R" is changed to implement "I".</p>
<p><br>
</p>
<p>But, even for:</p>
<p>final class A {}</p>
<p>final class B {}</p>
<p><br>
</p>
<p>case A a when ... -> {}</p>
<p>case B b -> {}</p>
<p>case A a -> {}</p>
<p><br>
</p>
<p>Can we change the order of the cases? I am not sure, because,
again, with separate compilation, this can lead to a different
outcome.</p>
<p><br>
</p>
<p>And maybe the answer is that we can do reordering in these cases.
Or maybe we can in some of these cases, and can't in orders. I
don't think this was ever discussed in depth.<br>
</p>
<p><br>
</p>
<p>Some of these decisions would be easier if we did the decision at
runtime, of course. Which brings its own problems, as discussed
elsewhere.<br>
</p>
<br>
<blockquote type="cite" cite="mid:36794892.19552004.1659859352180.JavaMail.zimbra@u-pem.fr">
<div style="font-family: arial, helvetica, sans-serif; font-size:
12pt; color: #000000">
<div data-marker="__QUOTED_TEXT__">
<div>The idea is that for each node of the decision tree, you
should generate the code in that order, first for the record
pattern, then the code for the guards then the code for the
type pattern, in that order.<br data-mce-bogus="1">
</div>
</div>
</div>
</blockquote>
<p><br>
</p>
<p>The current PR first generates (an analog of) the instanceof of
the record type, then code for the nested patterns, and then the
guard of the case. Which allows to join the cases into nested
switches (or ifs, if we go there). Not sure what is wrong with
that?<br>
</p>
<p><br>
</p>
<p>Jan<br>
</p>
<p><br>
</p>
<blockquote type="cite" cite="mid:36794892.19552004.1659859352180.JavaMail.zimbra@u-pem.fr">
<div style="font-family: arial, helvetica, sans-serif; font-size:
12pt; color: #000000">
<div data-marker="__QUOTED_TEXT__">
<div>If the guards are recorded in the same order as in the
pattern matching (this is equivalent to say that the sort
should be stable in term of guards), we should be ok.<br data-mce-bogus="1">
</div>
<div><br data-mce-bogus="1">
</div>
<div>As you said, the current spec allows to freely mix type
patterns and type pattern + guard pattern with the same
type, this has to be fixed at the spec level.<br data-mce-bogus="1">
</div>
<div>I think it's reasonable to introduce an order between the
type pattern + guard pattern and the type pattern on the
same type, because it's more readable and because we do not
want users to care to much about the order of the patterns
to get good performance. You should get good performance by
default, and not have to crawle StackOverflow to learn the
arcane of finding the "right order" for patterns.<br data-mce-bogus="1">
</div>
<div><br data-mce-bogus="1">
</div>
Rémi
<div><br>
</div>
</div>
</div>
</blockquote>
</body>
</html>