cache the results of type projection and normalization

[nikomatsakis]

Both in trans and in typeck. Must be somewhat careful around type parameters and so forth. Probably we want to introduce a cache onto the fulfillment context to use for normalization as well.

[arielb1]

cc me (this seems to take 10% of no-opt time).

[DemiMarie]

Which functions in the compiler need to be memoized?

[jonas-schievink]

@drbo FulfillmentContext::normalize_projection_type

[Marwes]

I was thinking about implementing this but I have run into some trouble. From what I can gather it is possible for type inference to try multiple different alternatives before it finds the correct typing. This means that types returned after normalizing and selecting associated types may actually be wrong and thus cannot be cached.

Is there some way/place where it is known that the result of normalizing is actually the correct way so that caching can be done correctly? The other way I thought of doing it is to rely on the snapshoting in the InferCtxt so that bad types can be rolled back but my implementation still seems to cache bad types in that implementation.

[nikomatsakis]

It's worth nothing that over the last week or so I've been drawing up plans
for overhauling this part of the compiler. Under the new design I am
currently considering, there isn't even a notion of normalization per se
(rather the compiler tracks "congruent" types using a congruence closure
algorithm). I intend to try and write this up over the next few days.

On Mon, Mar 7, 2016 at 12:10 PM, Markus Westerlind <[email protected]

wrote:

I was thinking about implementing this but I have run into some trouble.
From what I can gather it is possible for type inference to try multiple
different alternatives before it finds the correct typing. This means that
types returned after normalizing and selecting associated types may
actually be wrong and thus cannot be cached.

Is there some way/place where it is known that the result of normalizing
is actually the correct way so that caching can be done correctly? The
other way I thought of doing it is to rely on the snapshoting in the
InferCtxt so that bad types can be rolled back but my implementation still
seems to cache bad types in that implementation.

—
Reply to this email directly or view it on GitHub
#20304 (comment).

[Marwes]

I will hold off working on this then. Looking forward to seeing this issue resolved.

[nikomatsakis]

So, actually, I've been rethinking my "rethinking". That is, I now think the work on congruence closure is of secondary importance and can be deferred. I've implemented a simple cache for projection -- I have plans for a more elaborate one -- but it seems to be effective e.g. for the example in #31849.

[Mark-Simulacrum]

@nikomatsakis Is this still a problem today?

[ishitatsuyuki]

This is still a thing today, although I've improved the situation in #48296 by reducing the complexity of recursion itself.

[syntacticsugarglider]

This is still an issue and under the right circumstances is severe enough that it entirely blocks compilation of real-world code due to OOM.
The reproduction here exercises the issue both on the latest nightly and with the changes from #77325 applied, which does seem to mediate the issue as it was exercised by some other (previous) reproductions but isn't consistent across all examples that exercise the issue. I reported both #74456 and #70513 which I've now closed but each independently reproduce the issue (though, again, some of those reproductions are fixed by #77325). The underlying problem here isn't solved by anything that's been implemented since, though, and it's still blocking the work I was trying to do when I submitted those issues some 7 or 8 months ago. There was a long and winding discussion of this in this zulip thread with the ultimate conclusion that all of the previously filed issues all share the same cause.
I would love to contribute a fix but I don't fully understand the current process by which projections are normalized. I have a vague understanding of the rewriting process but not the actual operations that are being performed here, the purpose of the cache, the "ambiguity" mentioned in the FIXME comment in the source (which appears to be the cause of the duplication), etc. and no understanding of what steps would be necessary to correct the underlying issue.
Is the normalization process in its current state documented anywhere in a way that's focused on implementation details?

[the8472]

@syntacticsugarglider you may want to test with #90913. For me it fixes the reproducer in #74456 and a different performance issue I ran into. So it might help with other ones too.
It's a spot-fix for opt_normalize_projection_type, not a general fix to all obligation-processing methods. So it's possible that it doesn't fix all issues.

[syntacticsugarglider]

@the8472 thanks for the heads-up, gave that a try and it fixes the OOM but my test project I have sitting around (not the repro on that issue) still doesn't build, i gave it a core on my 4900HS for over an hour of CPU time to no avail. I'll do some profiling when I get a chance and play around with different repros, definitely possible it's a different issue.