Exponential performance cliff compiling associated types with equality constraints

@huonw

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(())
        ;
}

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.

cc me

Nominating because this seems to impact servo.

1.0 beta, P-high.

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).

#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.

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();
}

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.

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.

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> {
}

@Marwes

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.

@asajeffrey

@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)

@Marwes

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

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

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

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

This looks fixed with the projection cache.

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

Merge pull request rust-lang#22204 from Shourya742/2026-04-21-migrate…

Navigation Menu

Repository navigation

Exponential performance cliff compiling associated types with equality constraints #22204

8 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Exponential performance cliff compiling associated types with equality constraints #22204

Description

Activity

huonw commented on Feb 12, 2015

jdm commented on Feb 12, 2015

brson commented on Feb 12, 2015

pnkfelix commented on Feb 12, 2015

larsbergstrom commented on Feb 13, 2015

Gankra commented on Feb 13, 2015

gereeter commented on Feb 22, 2015

8 remaining items

TheZalli commented on Feb 24, 2016

asajeffrey commented on Feb 25, 2016

asajeffrey commented on Feb 25, 2016

asajeffrey commented on Mar 1, 2016

Marwes commented on Mar 1, 2016

asajeffrey commented on Mar 1, 2016

nikomatsakis commented on Mar 21, 2016

nikomatsakis commented on Mar 21, 2016

nikomatsakis commented on Mar 21, 2016

arielb1 commented on Jun 9, 2016

ishitatsuyuki commented on Apr 2, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions