[External] : Re: RFR: 8291769: Translation of switch with record patterns could be improved
Jan Lahoda
jan.lahoda at oracle.com
Tue Aug 9 06:53:45 UTC 2022
On 09. 08. 22 0:05, forax at univ-mlv.fr wrote:
>
>
> ------------------------------------------------------------------------
>
> *From: *"jan lahoda" <jan.lahoda at oracle.com>
> *To: *"Remi Forax" <forax at univ-mlv.fr>
> *Cc: *"Jan Lahoda" <jlahoda at openjdk.org>, "Brian Goetz"
> <brian.goetz at oracle.com>, "compiler-dev" <compiler-dev at openjdk.org>
> *Sent: *Sunday, August 7, 2022 11:17:16 AM
> *Subject: *Re: [External] : Re: RFR: 8291769: Translation of
> switch with record patterns could be improved
>
> On 07. 08. 22 10:02, forax at univ-mlv.fr wrote:
>
>
>
> ------------------------------------------------------------------------
>
> *From: *"jan lahoda" <jan.lahoda at oracle.com>
> *To: *"Remi Forax" <forax at univ-mlv.fr>
> *Cc: *"Jan Lahoda" <jlahoda at openjdk.org>, "Brian Goetz"
> <brian.goetz at oracle.com>, "compiler-dev"
> <compiler-dev at openjdk.org>
> *Sent: *Friday, August 5, 2022 11:54:05 PM
> *Subject: *Re: [External] : Re: RFR: 8291769: Translation
> of switch with record patterns could be improved
>
> On 05. 08. 22 22:52, forax at univ-mlv.fr wrote:
>
> [...]
>
> 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.
>
> 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:
> https://urldefense.com/v3/__https://github.com/forax/switch-pattern-combinator__;!!ACWV5N9M2RV99hQ!JevAQE8IkRf4n-BMKA2sMTNFfJ5sAyJ1xopR2O9rq_45-xqaHOgirecR8E4zIGB_RgMb27G3tlcHEuGADjk$
>
> 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.
>
> I agree.
>
> 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.
>
> 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.
>
>
> Sorry, but I don't see why I can't do this particular
> thing without a specialized intermediate representation.
>
>
> 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.
> There are several advantages to use a decision tree instead of
> a sort,
> - it's easier to visualize
> - it mimics the the usual hand-written code (you don't repeat
> the instanceofs, you enclose them)
> - 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.
>
>
> 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.
>
>
> I guess I can visualize the AST nodes quite fine.
>
>
>
> A bigger question, I think, is when it is safe to do so,
> and when not.
>
>
> yes, not all re-ordering are safe, we need to keep some
> constraints. Fortunately, the ordering problems only arise
> when there are guards.
>
>
> I think it is much more than (complex) guards. Like, for example:
>
> record R(Object o) {}
>
> interface I {}
>
>
> case R(String s) -> {}
>
> case I i -> {}
>
> case R(Integer i) -> {}
>
>
> 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".
>
>
> But, even for:
>
> final class A {}
>
> final class B {}
>
>
> case A a when ... -> {}
>
> case B b -> {}
>
> case A a -> {}
>
>
> Can we change the order of the cases? I am not sure, because,
> again, with separate compilation, this can lead to a different
> outcome.
>
>
> I think we are switching subject and entering into the "what guarantee
> we should provide to user with respect to separate compilation ?".
I don't think this is switching subject. This is still the same
question: when it is safe to change the order the cases.
>
> 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.
> (Pattern Matching is about data oriented programming, where data
> definition are more important than the algorithms/computation on the data)
>
> So perfectly executing a stale list of patterns is not that useful in
> my opinion.
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.
>
>
> 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.
>
>
> i agree it should be discussed more.
>
>
>
> Some of these decisions would be easier if we did the decision at
> runtime, of course. Which brings its own problems, as discussed
> elsewhere.
>
>
> 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,
> 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.
>
>
>
> 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.
>
>
> 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?
>
>
> 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.
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.
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.
Jan
> 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.
>
> Rémi
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20220809/08805cb6/attachment-0001.htm>
More information about the compiler-dev
mailing list