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

Exponential slowdown in catching an overflow error. #91949

Closed
steffahn opened this issue Dec 15, 2021 · 8 comments · Fixed by #97271
Closed

Exponential slowdown in catching an overflow error. #91949

steffahn opened this issue Dec 15, 2021 · 8 comments · Fixed by #97271
Labels
E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. I-compiletime Issue: Problems and improvements with respect to compile times. P-high High priority perf-regression Performance regression. regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@steffahn
Copy link
Member

steffahn commented Dec 15, 2021

This code is not expected to compile successfully:

fn main() {
    recurse(std::iter::empty());
}

struct Wrapped<T>(T);

struct IteratorOfWrapped<T, I: Iterator<Item = T>>(I);

impl<T, I: Iterator<Item = T>> Iterator for IteratorOfWrapped<T, I> {
    type Item = Wrapped<T>;
    fn next(&mut self) -> Option<Wrapped<T>> {
        self.0.next().map(Wrapped)
    }
}

fn recurse<T>(elements: T) -> Vec<char>
where
    T: Iterator<Item = ()>,
{
    recurse(IteratorOfWrapped(elements).map(|t| t.0))
}

This can't compile successfully because recurse<T> calls recurse<Map<IteratorOfWrapped<(), T>, [closure@<source>:22:51: 22:58]>> recursively, which then calls recurse<Map<IteratorOfWrapped<(), Map<IteratorOfWrapped<(), T>, [closure@<source>:22:51: 22:58]>>, [closure@<source>:22:51: 22:58]>>, and so on...

However up to stable 1.55, the code failed to compile quickly with the default recursion limit. On the compiler explorer, you can see it even handling #![recursion_limit = "800"] without timeout. However, go to 1.56 and it no longer reaches a compilation error in time with #![recursion_limit = "30"]. Still just as slow on nightly (rustc 1.59.0-nightly (6bda5b331 2021-12-12)).

@rustbot label: regression-from-stable-to-stable, perf-regression, I-compiletime, T-compiler, E-needs-bisection

Comes from: https://users.rust-lang.org/t/compiler-hanging/68804

Rough estimate on my machine: In the area of recursion_limit being 20-30, the time more-than doubles for each increase of the recursion limit by 2 or 3, so it really is exponential AFAICT.

@rustbot rustbot added E-needs-bisection Call for participation: This issue needs bisection: https://github.com/rust-lang/cargo-bisect-rustc I-compiletime Issue: Problems and improvements with respect to compile times. perf-regression Performance regression. regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Dec 15, 2021
@parasyte
Copy link

Possibly related to #89195?

@hkratz
Copy link
Contributor

hkratz commented Dec 15, 2021

Bisected to #85868, cc @Aaron1011

bisected with cargo-bisect-rustc v0.6.1 searched nightlies: from nightly-2021-06-01 to nightly-2021-12-08 regressed nightly: nightly-2021-09-03 searched commit range: https://github.com/rust-lang/rust/compare/50171c310cd15e1b2d3723766ce64e2e4d6696fc...371f3cd regressed commit: https://github.com/rust-lang/rust/commit/371f3cd3fe523d0b398ed1db1620667c53ba7d02

Host triple: x86_64-unknown-linux-gnu
Reproduce with:

cargo-bisect-rustc -t 3 --start 2021-06-01 --script ./test.sh

test.sh:

#!/bin/bash
cargo build
exit 0

@rustbot label -E-needs-bisection

@rustbot rustbot removed the E-needs-bisection Call for participation: This issue needs bisection: https://github.com/rust-lang/cargo-bisect-rustc label Dec 15, 2021
@steffahn
Copy link
Member Author

That PR seems incremental-compilation related. This leaves the question of whether the regression also happens without incremental compilation turned on, and whether or not it happens at the same point.

@wesleywiser
Copy link
Member

This is almost certainly the same issue as #89195 then.

@steffahn
Copy link
Member Author

steffahn commented Dec 15, 2021

Hard to know for certain until #89195 has a mvce. Also note that, as far as I understand, #89195 is observable with cargo check whereas this bug only appears with cargo build. (I somehow forgot to mention that...)

@apiraino
Copy link
Contributor

Assigning priority as discussed in the Zulip thread of the Prioritization Working Group.

@rustbot label -I-prioritize +P-high

@rustbot rustbot added P-high High priority and removed I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Dec 23, 2021
@wesleywiser
Copy link
Member

Retested since #90423 landed on nightly:

  • rustc 1.55.0 (c8dfcfe04 2021-09-06): 13.1 seconds
  • rustc 1.59.0-nightly (f8abed9 2021-12-26): 10.6 seconds

@steffahn
Copy link
Member Author

Seems to have fixed the problem, indeed. @rustbot label E-needs-test.

@rustbot rustbot added the E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. label Dec 27, 2021
JohnTitor added a commit to JohnTitor/rust that referenced this issue May 22, 2022
bors added a commit to rust-lang-ci/rust that referenced this issue May 23, 2022
Rollup of 5 pull requests

Successful merges:

 - rust-lang#97087 (Clarify slice and Vec iteration order)
 - rust-lang#97254 (Remove feature: `crate` visibility modifier)
 - rust-lang#97271 (Add regression test for rust-lang#91949)
 - rust-lang#97294 (std::time : fix variable name in the doc)
 - rust-lang#97303 (Fix some typos in arg checking algorithm)

Failed merges:

r? `@ghost`
`@rustbot` modify labels: rollup
@bors bors closed this as completed in 6d366f1 May 23, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
E-needs-test Call for participation: An issue has been fixed and does not reproduce, but no test has been added. I-compiletime Issue: Problems and improvements with respect to compile times. P-high High priority perf-regression Performance regression. regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

6 participants