Major regression in type checking performance compiling rustdoc #21694

Activity

1. nikomatsakis commented on Jan 27, 2015

   

   nikomatsakis

   on Jan 27, 2015

   Contributor

   More actions

   Nominating. We should track this down. Quite possibly due to #20304
2. nikomatsakis

   added

   I-nominated

   on Jan 27, 2015
3. nrc commented on Jan 27, 2015

   

   nrc

   on Jan 27, 2015

   Member

   More actions

   cc me
4. nrc commented on Jan 29, 2015

   

   nrc

   on Jan 29, 2015

   Member

   More actions

   I've been profiling this and the most time was spent in the hash function for Substs. Which is kind of weird.
5. nikomatsakis commented on Jan 29, 2015

   

   nikomatsakis

   on Jan 29, 2015

   Contributor

   More actions

   interesting, could be related to @huonw's changes to intern Substs
6. pnkfelix commented on Jan 29, 2015

   

   pnkfelix

   on Jan 29, 2015

   Contributor

   More actions

   Polish issue, but worth trying to address by 1.0 beta.
7. pnkfelix

   added this to the 1.0 beta milestone on Jan 29, 2015
8. pnkfelix

   added

   P-mediumMedium priorityMedium priority

   and removed

   I-nominated

   on Jan 29, 2015
9. nikomatsakis commented on Jan 29, 2015

   

   nikomatsakis

   on Jan 29, 2015

   Contributor

   More actions

   but it's always possible that it's just that we're doing a lot more hashing -- i.e., it's the caller's problem
10. jdm commented on Jan 30, 2015

    

    jdm

    on Jan 30, 2015

    Contributor

    More actions

    cc me
11. nrc commented on Jan 30, 2015

    

    nrc

    on Jan 30, 2015

    Member

    More actions

    I did a bunch more profiling. First off, normalisation and projection barely showed up in the profile, so I think #20304 is a red herring.

    Substs interning did, but because it was called a huge number of times, it's not that expensive for each call. I tried disabling interning, for rustdoc this led to OOMs. For libcore which also has a very high type checking time (relative to other phases) this only reduced type checking time by 6%, so I predict it won't be helpful in the rustdoc case.

    The majority of the time is coming from trait selection - SelectionContext::evalute_predicate_recursively is the overarching method in the profile. Winnowing in particular is taking ~75% of the time.

    So, I don't think caching normalisation and projection is worthwhile, at least here, it might be for other reasons. I need to look a bit closer at the code around selections. AIUI, only first phase is cached and I don't think winnowing is. I wonder if we could cache that too? I also want to check that caching is working as expected and we're not missing where we should hit.
12. sanxiyn commented on Feb 2, 2015

    

    sanxiyn

    on Feb 2, 2015

    Contributor

    More actions

    FYI, slowness is caused by trying to infer and check an excessive use of iterator chain.
13. nikomatsakis commented on Feb 2, 2015

    

    nikomatsakis

    on Feb 2, 2015

    Contributor

    More actions

    Interesting. That fits with @nick29581's profiles, for sure.
14. nikomatsakis commented on Feb 2, 2015

    

    nikomatsakis

    on Feb 2, 2015

    Contributor

    More actions

    we should make a standalone test case...
15. huonw commented on Feb 2, 2015

    

    huonw

    on Feb 2, 2015

    Contributor

    More actions

    It seems to be related to the equality constraint between the associated types:

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

    $ rustc slow-typeck.rs -Z time-passes --cfg equality | grep 'type checking'
    time: 0.219     type checking
    $ rustc slow-typeck.rs -Z time-passes | grep 'type checking'
    time: 0.014     type checking
    

    (The blow-up appears to be exponential.)
16. nrc commented on Feb 12, 2015

    

    nrc

    on Feb 12, 2015

    Member

    More actions

    Closing this - the rustdoc-specific perf issue has been fixed in #21864. I have opened #22204 for the general case.
17. nrc

    closed this as completedon Feb 12, 2015
18. lnicola

    added a commit that references this issue on Feb 23, 2026

    Merge pull request rust-lang#21694 from rust-lang/rustc-pull

    ...

    d8ffd91