Compile slow down against trait bound of nested structs

[KeenS]

I'm not sure if this should be reported as a regression. I found compiling my code with Rust 1.41.0 took triple time compared to the previous version. It occurred 1 year ago and filed at my repo, so this is a bit old issue.

The code contains nested structs with trait bounds. It took some time to compile in the previous version too. I guess compiling this code take exponential time even in older versions of rust compiler because when I add a pass to the chain, compile time increases under certain multiplier. The issue is the multiplier increased in Rust 1.41.0.

Here is some brief measures:

$ time rustc +1.36.0 slow_compilation.rs
rustc +1.36.0 slow_compilation.rs  16.25s user 0.68s system 99% cpu 16.939 total
$ time rustc +1.40.0 slow_compilation.rs
rustc +1.40.0 slow_compilation.rs  21.16s user 0.58s system 99% cpu 21.743 total
$ time rustc +1.41.0 slow_compilation.rs
rustc +1.41.0 slow_compilation.rs  59.95s user 0.69s system 99% cpu 1:00.66 total
$ time rustc +1.50.0 slow_compilation.rs
rustc +1.50.0 slow_compilation.rs  48.87s user 0.75s system 99% cpu 49.634 total
$ time rustc +nightly slow_compilation.rs
rustc +nightly slow_compilation.rs  50.08s user 0.60s system 100% cpu 50.671 total

Compiling slowed down in 1.41.0. Though there are some improvements in the latest versions, it is still slow.

Here is flamegraph of rust compiler against compiling the code:

I git bisected and found the problem is introduced in this PR: #66408

Code

I tried this code:

use std::fmt::Display;
use std::marker::PhantomData;

pub trait Pass<T, E> {
    type Target;
    fn trans(&mut self, t: T) -> Result<Self::Target, E>;
}

pub struct PrintablePass<T>(pub T, pub &'static str);

impl<T, In, Out, Err> Pass<In, Err> for PrintablePass<T>
where
    T: Pass<In, Err, Target = Out>,
    Out: Display,
{
    type Target = Out;

    fn trans(&mut self, i: In) -> Result<Self::Target, Err> {
        let o = self.0.trans(i)?;
        Ok(o)
    }
}

pub struct Chain<F, FO, S, SO> {
    pub fst: F,
    pub snd: S,
    phantom: PhantomData<(FO, SO)>,
}

impl<F, FO, S, SO> Chain<F, FO, S, SO> {
    pub fn new(fst: F, snd: S) -> Self {
        Chain {
            fst,
            snd,
            phantom: PhantomData,
        }
    }
}

impl<F, E, S, T, In, Out> Pass<In, E> for Chain<F, T, S, Out>
where
    F: Pass<In, E, Target = T>,
    S: Pass<T, E, Target = Out>,
{
    type Target = Out;

    fn trans(&mut self, i: In) -> Result<Self::Target, E> {
        let &mut Chain {
            ref mut fst,
            ref mut snd,
            ..
        } = self;
        let t = fst.trans(i)?;
        let o = snd.trans(t)?;
        Ok(o)
    }
}

#[macro_export]
macro_rules! compile_pass {
    ($($labels: ident : $passes: expr,)*) => {
        compile_pass!($($labels: $passes),*)
    };
    ($label: ident : $pass: expr, $($labels: ident : $passes: expr),*) => {
        Chain::new(PrintablePass($pass, stringify!($label)), compile_pass!($($labels: $passes),*))
    };
    ($label: ident : $pass: expr) => {
        PrintablePass($pass, stringify!($label))
    };
}

macro_rules! def_pass {
    ($name: ident) => {
        struct $name;
        impl<'a> Pass<&'a str, ()> for $name {
            type Target = &'a str;
            fn trans(&mut self, i: &'a str) -> Result<Self::Target, ()> {
                Ok(i)
            }
        }
    };
}

def_pass!(Parse);
def_pass!(Desugar);
def_pass!(Rename);
def_pass!(VarToConstructor);
def_pass!(Typer);
def_pass!(CaseSimplify);
def_pass!(AST2HIR);
def_pass!(ConstructorToEnum);
def_pass!(Simplify);
def_pass!(FlatExpr);
def_pass!(FlatLet);
def_pass!(UnnestFunc);
def_pass!(ForceClosure);
def_pass!(HIR2MIR);
def_pass!(UnAlias);
def_pass!(BlockArrange);
def_pass!(MIR2LIR);
def_pass!(LIR2WASM);

pub fn compile_str<'a>(input: &'a str) -> Result<&'a str, ()> {
    let mut passes = compile_pass![
        parse: Parse,
        desugar: Desugar,
        rename: Rename,
        var_to_constructor: VarToConstructor,
        typing: Typer,
        case_simplify: CaseSimplify,
        ast_to_hir: AST2HIR,
        constructor_to_enum: ConstructorToEnum,
        simplify: Simplify,
        flattening_expression: FlatExpr,
        flattening_let: FlatLet,
        unnest_functions: UnnestFunc,
        closure_conversion: ForceClosure,
        hir_to_mir: HIR2MIR,
        unalias: UnAlias,
        block_arrange: BlockArrange,
        mir_to_lir: MIR2LIR,
        backend: LIR2WASM,
    ];

    passes.trans(input)
}

fn main() {}

I expected to see this happen: compiles in < 30s

Instead, this happened: compiles in > 60s

Version it worked on

It most recently worked on: 1.40.0

Version with regression

rustc --version --verbose:

rustc +1.41.0 --version --verbose
rustc 1.41.0 (5e1a79984 2020-01-27)
binary: rustc
commit-hash: 5e1a799842ba6ed4a57e91f7ab9435947482f7d8
commit-date: 2020-01-27
host: x86_64-unknown-linux-gnu
release: 1.41.0
LLVM version: 9.0

Backtrace

Backtrace

<backtrace>

[apiraino]

Removing priority label for these kind of issues, added automatically by the bot. We want to keep an eye on them but we can't prioritize them at this time.

anyway thanks @KeenS for the great work of bisecting. This will come in handy.

@rustbot label -I-prioritize