deeply-nested chain hangs with Item = u32 #70749
Labels
A-LLVM
Area: Code generation parts specific to LLVM. Both correctness bugs and optimization-related issues.
C-bug
Category: This is a bug.
I-hang
Issue: The compiler never terminates, due to infinite loops, deadlock, livelock, etc.
T-compiler
Relevant to the compiler team, which will review and decide on the PR/issue.
Comments
cuviper
added
A-LLVM
|
I found this in the process of evaluating changes to Importantly, this test code does not hang with those changes. So if the compiler is fixed to handle this better, it should probably come with a self-contained regression test including the "old" |
jonas-schievink
added
the
I-hang
The good news is that it did finish when I wasn't looking -- then I ran it again to actually time it: |
|
I ran into a very similar issue while trying to enable the MIR inline pass by default. (More info in this Zulip thread) If I remember correctly, using |
|
Hmm, with new PM it completed in "only" 8 minutes here, and then 13 minutes the second time, with a snapshot of the stack like this: Backtrace
|
|
Since #70896 did land, removing the reproducer, here's a self-contained version: #![crate_type = "lib"]
#![allow(unused)]
pub fn foo() -> Box<dyn Iterator<Item = u32>> {
use std::iter::empty;
Box::new(
empty()
.my_chain(empty())
.my_chain(empty())
.my_chain(empty())
.my_chain(empty())
.my_chain(empty())
.my_chain(empty())
.my_chain(empty())
.my_chain(empty())
.my_chain(empty())
.my_chain(empty()) // 10th
.my_chain(empty())
.my_chain(empty())
.my_chain(empty())
.my_chain(empty())
.my_chain(empty())
.my_chain(empty()), // 16th
)
}
// The `Chain` implementation changed in #70896, which stopped reproducing the optimization hang,
// but here's a reduced copy of the old `Chain` for posterity.
struct Chain<A, B> {
a: A,
b: B,
state: ChainState,
}
enum ChainState {
Both,
Front,
Back,
}
impl<A, B> Iterator for Chain<A, B>
where
A: Iterator,
B: Iterator<Item = A::Item>,
{
type Item = A::Item;
#[inline]
fn next(&mut self) -> Option<A::Item> {
match self.state {
ChainState::Both => match self.a.next() {
elt @ Some(..) => elt,
None => {
self.state = ChainState::Back;
self.b.next()
}
},
ChainState::Front => self.a.next(),
ChainState::Back => self.b.next(),
}
}
}
trait IteratorExt: Iterator {
fn my_chain<U>(self, other: U) -> Chain<Self, U::IntoIter>
where
Self: Sized,
U: IntoIterator<Item = Self::Item>,
{
Chain {
a: self,
b: other.into_iter(),
state: ChainState::Both,
}
}
}
impl<I: Iterator> IteratorExt for I {}This compiles quickly (~150ms) in debug mode, but takes a very long time to optimize. I didn't wait to fully time it yet, but it's more than a minute, which is already unacceptable. (edit: 35m34s) With |
|
The performance bug can be triggered in original example by slightly increasing the LLVM inlining threshold (currently the issue starts at The partitioning |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I tried this code:
This is adapted from the deeply-nested test, just changing
Item = ()toItem = u32.Building with
rustc +nightly --crate-type lib -Copt-level=2 src/lib.rsseems to hang indefinitely.I expected to see this happen: completion in a few seconds at most.
Instead, this happened: I'm still waiting...
Meta
rustc --version --verbose:Also happens on 1.42.0 and 1.43.0-beta.3.
Attaching rust-gdb, I see two busy LLVM threads:
Backtrace
The text was updated successfully, but these errors were encountered: