Exponential performance cliff compiling associated types with equality constraints

[nrc]

This was first observed due to a bunch of chain calls in rustdoc (#21694). @huonw provided a minimal test case:

struct Pair<A, B>(A, B);

trait Foo: Sized {
    type Item = ();
    fn foo<B>(self, other: B) -> Pair<Self, B> {
        Pair(self, other)
    }
}
impl Foo for () {
    type Item = ();
}
#[cfg(equality)]
impl<A: Foo, B: Foo<Item = A::Item>> Foo for Pair<A, B> {
    type Item = A::Item;
}
#[cfg(not(equality))]
impl<A: Foo, B: Foo> Foo for Pair<A, B> {
    type Item = A::Item;
}

fn main() {
    ().foo(())
        .foo(())
        .foo(())
        .foo(())
        .foo(())
        .foo(())
        .foo(())
        .foo(())
        .foo(())
        ;
}

[huonw]

This also applies for trait bounds, e.g. replacing the equality impl with

trait X<T> {}

impl X<()> for () {}

#[cfg(equality)]
impl<A: Foo, B: Foo> Foo for Pair<A, B>
        where A::Item: X<B::Item> {
    type Item = A::Item;
}

gives similar results.

[jdm]

cc me

[brson]

Nominating because this seems to impact servo.

[pnkfelix]

1.0 beta, P-high.

[larsbergstrom]

I am not 100% sure we are hitting this - I believe that when we were investigating the perf regressions we suspected this, but I am not certain. Is there something we can do to verify we're hitting it? (assuming you would postpone it if it's not an issue for Servo).

[Gankra]

#21694 demonstrates that if you're hitting it, it should show up in the type checking phase, which is otherwise quite lean. Should show up pretty clearly.

[gereeter]

A slightly more minimal test case:

struct A<X>(X);

trait Foo: Sized {
    type Item;
    fn go(self) -> A<Self> {
        A(self)
    }
}

impl Foo for () {
    type Item = ();
}

#[cfg(equality)]
impl<X: Foo<Item=()>> Foo for A<X> {
    type Item = ();
}

#[cfg(not(equality))]
impl<X: Foo> Foo for A<X> {
    type Item = ();
}

fn main() {
    ().go().go().go().go()
      .go().go().go().go()
      .go().go().go().go()
      .go().go().go().go();
}

[pnkfelix]

1.0 polish (if anything; definitely puntable if we cannot fix in time).

[arielb1]

There are 2 problems here:
1) evaluate_predicates_recursively doesn't do memoization (this can easily be fixed).
2) we don't memoize associated types. this is harder to fix as they could have inferred and infer-skolemized contents, and generate nested obligations (esp. region obligations). I kind-of want to fix this already for trans, but trans doesn't have these difficulties.

[Ralle]

All of us using this crate ( https://github.com/Marwes/combine ) are waiting for this to get fixed. My compile time for a 500 line program is over 2 minutes. The maintainer of combine has helped people try to optimize their code for the compiler to run faster, not the result. I would very much like to see this ticket on any milestone, so I can look forward to Rust being usable in my parser project.

[TheZalli]

Same as Ralle, I came here from combine. It seems like a really nice parsing library for my project, but even the simple demonstration test that was in their docs took alarmingly long to compile, so I hope this gets fixed soon.

[asajeffrey]

Ditto, coming here from perf issues with my parser library (#31849). My minimal example is just chaining iterators (https://play.rust-lang.org/?gist=a0c05fbf5c43234fb7c3):

fn main() {
    let iter = (0..2)
        .chain(0..2)
        .chain(0..2)
        .chain(0..2)
        .chain(0..2)
        .chain(0..2)
        .chain(0..2)
        .chain(0..2)
        .chain(0..2)
        .chain(0..2)
        .chain(0..2);
    for i in iter { println!("{:?}", i); }
}

On my machine, chaining 15 iterators takes 1min to typecheck, and uses about 500M of memory.

[asajeffrey]

Separating out the projection trait (HasItem) as a separate trait seems to be a work-around... https://play.rust-lang.org/?gist=1cf9886dd074e073cd6a

trait HasItem {
    type Item;
}

trait TDIterator<Item> {
    fn next(&mut self) -> Option<Item>;
}

trait BUIterator: HasItem + TDIterator<<Self as HasItem>::Item> {
}

[asajeffrey]

The work-around does scale up to the Parsell parser library (see, e.g. http://asajeffrey.github.io/parsell/target/doc/parsell/trait.StatefulInfer.html). It may be that combine can use a similar work-around? cc @Marwes.

[Marwes]

@asajeffrey It would unfortunately be a backwards incompatible change so I am afraid I cannot do it at the moment for combine. I may do it for 2.0 though I am not inclinded to rush towards that at the moment.

(I did test compiling a branch I already had where combine's Input type is a parameter instead of associated and it cut compiling the tests into half 1m10s -> 32s)

[asajeffrey]

@Marwes indeed, Parsell has the luxury of still being at v0.x.x so I can make changes like this more easily.

[nikomatsakis]

Just FYI, my projection caching branch (PR coming soon) totally solves this problem, from what I can tell.

[nikomatsakis]

hmm, although actually maybe it's already been solved. At least stage0 seems to run fine too.

[nikomatsakis]

I take it back, the chained iterator case is still quite slow.

[arielb1]

This looks fixed with the projection cache.

[ishitatsuyuki]

#48296 should have solved this completely. Closing as obsolete.