Exponential compile-time and type_length_limit blowup when nesting closure wrappers

[vorner]

I think this is better explained by a code snippet:

#![recursion_limit="128"]
#![type_length_limit="67108864"]

fn main() {
    let s = S19::default();
    s.call_me((), &|()| ());
}

trait CallMe<T: Copy> {
    fn call_me<F: Fn(T)>(&self, t: T, f: &F);
}

impl<T: Copy> CallMe<T> for () {
    fn call_me<F: Fn(T)>(&self, _: T, _: &F) {}
}

#[derive(Default, Debug)]
struct S<T>(T, T);

impl<T: Copy, P: CallMe<T>> CallMe<T> for S<P> {
    fn call_me<F: Fn(T)>(&self, t: T, f: &F) {
        let wrapped = |t: _| {
            f(t);
        };
        self.0.call_me(t, &wrapped);
        self.1.call_me(t, &wrapped);
    }
}

type S0 = S<()>;
type S1 = S<S0>;
type S2 = S<S1>;
type S3 = S<S2>;
type S4 = S<S3>;
type S5 = S<S4>;
type S6 = S<S5>;
type S7 = S<S6>;
type S8 = S<S7>;
type S9 = S<S8>;
type S10 = S<S9>;
type S11 = S<S10>;
type S12 = S<S11>;
type S13 = S<S12>;
type S14 = S<S13>;
type S15 = S<S14>;
type S16 = S<S15>;
type S17 = S<S16>;
type S18 = S<S17>;
type S19 = S<S18>;

What it does is it creates a closure on each level, that wraps another received closure. With the number of levels the compile time and the needed type_length_limit grows exponentially.

However, if I change the two calls to:

self.0.call_me(t, &f);
self.1.call_me(t, &f);

then the blow-up goes away and it compiles almost instantaneously (I tried it up to 120 levels, without increasing the type length limit), so nesting the S structures like this is OK. But if I change only one of the calls (or even remove it) and leave just one call to the wrapper, the blowup is still there. However, there seems to be nothing around the wrapper that should make it exponential ‒ it's contains just one call to the wrapped f, has no captures, and if I look at the code, I still count only one distinct closure on each level.

The times I've measured with different number of levels:

11: 0.5
12: 0.74
13: 0.97
14: 1.56
15: 2.66
16: 5.02
17: 9.16
18: 18.50
19: 37.72

This is happening both on stable and nightly:

rustc 1.30.0-nightly (63c75d375 2018-09-21)
binary: rustc
commit-hash: 63c75d375d76d0bcc586f9cb5520ced24bc58450
commit-date: 2018-09-21
host: x86_64-unknown-linux-gnu
release: 1.30.0-nightly
LLVM version: 8.0

@ishitatsuyuki mentioned at IRC that he would want to have a look.

[vorner]

And another thing I've noticed. cargo check does not trigger the limits and is fast no matter how many levels I put there (but I guess these limits are for the phases cargo check doesn't do).

[eddyb]

cc #54175 @nikomatsakis

[ishitatsuyuki]

So well, type_length_limit is a monomorphization time thing and it's used for symbol name (lengths). It's no wonder that the blowup happened because you actually raised the type_length_limit.

As type aliases are identical to the original type, we can't generate things like debug symbols of a reasonable length in this case. We have to combine both caching and digesting to make the symbol shorter.

[vorner]

How is it possible then that if I don't call the wrapper, but f, no limit is triggered? It still needs to create the symbol names for the call_me method for each S with a very long name. What I'm trying to point out here is, it all works as a charm without the wrapper closure, but that closure doesn't bring anything special to the table, so why does it make a difference?

And I still don't think the compiler would take 30 seconds to create 20 or so symbol names, each 6 MB long.

What I'm trying to say ‒ I understand than if the bigger limit is needed, it takes longer. But I think the bigger limit should not be needed here. Or, at least, I don't see why it should be.

[eddyb]

@vorner We don't put types in symbol names except for the X in <X as Trait>::method, so I think that's likely what the closure is doing here.

If we move to proper C++-like mangling, we can use the compression features and bypass this problem entirely.

EDIT: I likely was wrong, see below.

[ishitatsuyuki]

Triage, Pending Pre-RFC that aims to solve this: https://internals.rust-lang.org/t/pre-rfc-a-new-symbol-mangling-scheme

[eddyb]

After working on the parts of rustc relevant to this issue, I'm pretty sure none of those types are getting into symbol names, but rather this is type_length_limit's walk over the generic arguments:

rust/src/librustc_mir/monomorphize/collector.rs

Line 470 in 72bc620

let type_length = instance.substs.types().flat_map(|ty| ty.walk()).count();

The reason closures trigger this is because F is both a type parameter of the closure and a capture, so the walk above doubles itself at every level (and it's breadth-first, so I assume its memory allocations are responsible for the slowdown).

We can trigger the type_length_limit behavior for closures with (F, F), too, and so I managed to reproduce the slowdown without closures (or really any calls):

(click to open)

#![type_length_limit="8388607"]

pub const MAIN: fn() = <S21 as Exp<()>>::exp as fn();

trait Exp<X> {
    fn exp();
}

impl<X> Exp<X> for () {
    fn exp() {}
}

impl<T: Exp<(X, X)>, X> Exp<X> for (T,) {
    fn exp() {
        <T as Exp<(X, X)>>::exp as fn();
    }
}

type S<T> = (T,);
type S0 = S<()>;
type S1 = S<S0>;
type S2 = S<S1>;
type S3 = S<S2>;
type S4 = S<S3>;
type S5 = S<S4>;
type S6 = S<S5>;
type S7 = S<S6>;
type S8 = S<S7>;
type S9 = S<S8>;
type S10 = S<S9>;
type S11 = S<S10>;
type S12 = S<S11>;
type S13 = S<S12>;
type S14 = S<S13>;
type S15 = S<S14>;
type S16 = S<S15>;
type S17 = S<S16>;
type S18 = S<S17>;
type S19 = S<S18>;
type S20 = S<S19>;
type S21 = S<S20>;

Note that a downside of using (X, X) instead of a closure is that tuples are actually exponential in debuginfo, unlike closures (which only show their captures), so you either need to compile unoptimized w/o debuginfo, or in release mode (e.g. on the playground - it'd be nice if it also had the former, cc @lqd).

---

What can you (@vorner) do?

Not much, I'm afraid you can't avoid this issue, if you need a closure with a capture.
However, if you don't need the Fn() trait (or at least not for the code that contains the wrapper closure), you can build your own Fn-like trait, and instead of a closure you can have a struct which is only parameterized by F once (unlike the closure, which ends up doing it twice).
Or you can wait for one of the fixes below (but the issue will, of course, persist in older versions).

What can we do?

For type_length_limit specifically, it could control the walk more directly, and cache the sizes of subtrees, which should reduce the cost for this to something linear.
I am, however, worried this may be inefficient for most "type lengths", which are probably going to be relatively small anyway, and where the current walk is likely pretty cheap.
IIRC type_length_limit was added to avoid the compiler spending a lot of time without appearing to do anything, I wonder if that could be solved some other way?

For closure captures, maybe they should refer to their parameters abstractly, so we never have to substitute captures (until we need to e.g. compute layout)? Or even keep captures outside of the type itself (had we done this and found it inefficient?)
cc @rust-lang/wg-traits @rust-lang/wg-compiler-nll @arielb1

I'm nominating this issue for discussion at the next compiler team meeting, wrt the last two points above (type_length_limit and closure captures).

[pnkfelix]

triage: tagging as P-medium, under assumption that the exponential time blowup here is only observable if the user "opts in" via type_length_limit with large values. Leaving nominated for discussion since, well, it still needs to be discussed.

If the prior assumption is invalid, feel free to challenge that priority assignment.