<html><head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<p>On 09. 08. 22 0:05, <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:1709510871.19940633.1659996342020.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>Sunday, August 7, 2022 11:17:16 AM<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 07. 08. 22 10:02, <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: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">
<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;"><b>From:
</b>"jan lahoda" <a class="moz-txt-link-rfc2396E" href="mailto:jan.lahoda@oracle.com" target="_blank" moz-do-not-send="true"><jan.lahoda@oracle.com></a><br>
<b>To: </b>"Remi Forax" <a class="moz-txt-link-rfc2396E" href="mailto:forax@univ-mlv.fr" target="_blank" moz-do-not-send="true"><forax@univ-mlv.fr></a><br>
<b>Cc: </b>"Jan Lahoda" <a class="moz-txt-link-rfc2396E" href="mailto:jlahoda@openjdk.org" target="_blank" moz-do-not-send="true"><jlahoda@openjdk.org></a>,
"Brian Goetz" <a class="moz-txt-link-rfc2396E" href="mailto:brian.goetz@oracle.com" target="_blank" moz-do-not-send="true"><brian.goetz@oracle.com></a>,
"compiler-dev" <a class="moz-txt-link-rfc2396E" href="mailto:compiler-dev@openjdk.org" target="_blank" moz-do-not-send="true"><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>
<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>
</div>
<div>- it's easier to visualize<br>
</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>
</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 cite="mid:36794892.19552004.1659859352180.JavaMail.zimbra@u-pem.fr">
<div style="font-family: arial, helvetica, sans-serif;
font-size: 12pt; color: #000000">
<div>
<div><br>
</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>
</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>
</blockquote>
<div><br>
</div>
<div>I think we are switching subject and entering into the
"what guarantee we should provide to user with respect to
separate compilation ?".<br data-mce-bogus="1">
</div>
</div>
</div>
</blockquote>
<p><br>
</p>
<p>I don't think this is switching subject. This is still the same
question: when it is safe to change the order the cases.</p>
<p><br>
</p>
<blockquote type="cite" cite="mid:1709510871.19940633.1659996342020.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>
<div>One problem i see is that in practice it is likely that
the definition of the data have changed but the patterns
have not be recompiled so the patterns are now wrongs.</div>
<div>(Pattern Matching is about data oriented programming,
where data definition are more important than the
algorithms/computation on the data)<br data-mce-bogus="1">
</div>
<div><br data-mce-bogus="1">
</div>
<div>So perfectly executing a stale list of patterns is not
that useful in my opinion.<br data-mce-bogus="1">
</div>
</div>
</div>
</blockquote>
<p><br>
</p>
<p>As I said - it is possible the answer is that we can reorder the
cases in situations like this. But that's not a decision that
should be made in an implementation PR.</p>
<p><br>
</p>
<blockquote type="cite" cite="mid:1709510871.19940633.1659996342020.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><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.</p>
</blockquote>
<div><br>
</div>
<div>i agree it should be discussed more.<br data-mce-bogus="1">
</div>
<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><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.</p>
</blockquote>
<div><br>
</div>
<div>I'm not even sure that it's easier at runtime because of
erasure, patterns are correctly typecked or not depending on
the types, but at runtime we only have class with the
generic information erased,<br data-mce-bogus="1">
</div>
<div>so apart if we decide to fully duplicate the whole
typechecking done at compile time to redo it at runtime, the
information we have at runtime does not help us that much.<br data-mce-bogus="1">
</div>
<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><br>
</p>
<br>
<blockquote cite="mid:36794892.19552004.1659859352180.JavaMail.zimbra@u-pem.fr">
<div style="font-family: arial, helvetica, sans-serif;
font-size: 12pt; color: #000000">
<div>
<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>
</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?</p>
</blockquote>
<div><br>
</div>
<div>It's not wrong, but by only merging subsequent patterns
you are creating an arcane knowledge of writing the patterns
"the right way" to get more performance.<br data-mce-bogus="1">
</div>
</div>
</div>
</blockquote>
<p><br>
</p>
<p>As I've said several times, the current patch allows case
reordering, but it is not clear which reorderings are safe, so it
is not doing them. The implementation wouldn't be too difficult, I
believe: while accummulating cases for a primary type X, when
looking at case for a different primary type Y, we can evaluate
whether it is fine to skip the current case, and if yes, we would
continue and evaluate the next case. The most difficult part here
is to decide which reordering is safe and which is not.</p>
<p><br>
</p>
<p>Overall, I am much more worried about not introducing a wrong
behavior. We've been changing translations of various constructs
in the past, while keeping behavior, and while that is not ideal,
it was not that much problematic either. We've made changes to
String concatenation and try-with-resources, for example. Fixing
broken behavior is likely to be much more difficult.</p>
<p><br>
</p>
<p>Jan<br>
</p>
<p><br>
</p>
<blockquote type="cite" cite="mid:1709510871.19940633.1659996342020.JavaMail.zimbra@u-pem.fr">
<div style="font-family: arial, helvetica, sans-serif; font-size:
12pt; color: #000000">
<div data-marker="__QUOTED_TEXT__">
<div>It's not really an issue now because record patterns are
still a preview feature but it's a serious issue in the long
run.<br data-mce-bogus="1">
</div>
<div><br data-mce-bogus="1">
</div>
<div>Rémi<br data-mce-bogus="1">
</div>
<div><br data-mce-bogus="1">
</div>
</div>
</div>
</blockquote>
</body>
</html>