Exponential time complexity when type checking code with equality constraints #125267
Labels
A-typesystem
Area: The type system
C-optimization
Category: An issue highlighting optimization opportunities or PRs implementing such
I-compiletime
Issue: Problems and improvements with respect to compile times.
S-has-mcve
Status: A Minimal Complete and Verifiable Example has been found for this issue
T-compiler
Relevant to the compiler team, which will review and decide on the PR/issue.
Given this significantly reduced example of real-world code,
compiling with the larger number of chained methods (i.e. with
#[cfg(feature = "slowdown")]
) results in apparent exponential (correlation = 0.992) time complexity forcargo check
. The code as written takes approximately 9-10 seconds to type check on my laptop. Uncommenting two of the three lines that are presently commented out took 7m51s (471 seconds) for the same.Checking with
-Znext-solver
improves the situation quite a bit, but the behavior still seems to be exponential.Removing the equality constraints from
or_unify
avoids the pathological case entirely. I suspect this is a starting point for investigating a possible fix.Difference using
-Zself-profile
(nearly all rows elided for brevity, plus most changes are just noise)Total cpu time: -11.830756846s
Without performing a thorough check, I checked the time to type check on both 1.65 and 1.40 with similar results. Given that, this behavior has been around for 4+ years at a minimum.
The text was updated successfully, but these errors were encountered: