Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve inference SCC limiting code to avoid repeated inferring the same cycle #38517

Closed
Keno opened this issue Nov 20, 2020 · 2 comments
Closed
Labels
compiler:inference Type inference compiler:latency Compiler latency

Comments

@Keno
Copy link
Member

Keno commented Nov 20, 2020

Part of the problem in talking about this issue is that we don't have great terminology,
so I'm gonna use some terminology that I think is reasonable, but we should probably
come up with some proper names for all these concepts and put them in the devdocs.

Consider a call cycle like

   +------------+
   v            +
E+>A+>B+>C+>B'+>D->E'
   ^
F+-+

Where B, B' are the same method with different signatures, (as are E and E').
Now, when inference see a method cycle like B->B' it has some heuristics to
decide whether to allow this or whether to "limit" the signature B' (e.g. by widening
some arguments to Any to force it to have strictly less information than B, thus
preventing infinitely growing types). However, when it does this it must also
"poison" all inference frames between B and B' (in this case C) to avoid
caching it. This is done such that if some other caller enters C, (without having
gone through B), it will not be subject to the same limiting.
Now, in the example above, we later discover that C is actually part of the
SCC (strongly-connected component) A,B,C,B',D. In this case, we should
be able to undo the limiting, because any entry point into the SCC will always
eventually see the B->B' method cycle forcing limiting. However, we need
to be a bit careful, because we could also be in the situation E->SCC->E'
in which case the entire SCC does actually need to be poisoned to avoid
pessimizing inference for F->SCC->E'.

Currently we only track a boolean for the limited flag, which is insufficient to
distinguish the above two cases. We should extend this information to track
which limiting decisions the current results depend on, then figuring out if
they are part of the current SCC or not.

As an additional refinement, we could also clear any limiting decisions that
don't actually affect the return value of the current function.

cc @NHDaly @Sacha0 @vtjnash

@Keno Keno added compiler:inference Type inference compiler:latency Compiler latency labels Nov 20, 2020
@vchuravy
Copy link
Member

Yeah I recall looking at a case with Peter where having a A -> B -> A disabled the normal self-recursion heuristic, which limited the kind of codes we could write, before having to use @generated as an escape hatch. So I am all in favor of handling this.

@vtjnash
Copy link
Member

vtjnash commented Dec 24, 2020

To be clear, this is proposing caching the result, without changing it (knowing that it won't change)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler:inference Type inference compiler:latency Compiler latency
Projects
None yet
Development

No branches or pull requests

3 participants