exponential blowup when rerunning due to changed provisional results

[lcnr]

@petervdonovan provided the following minimization on zulip.

pub trait MapsTmf<E> {
    type Tmf;
}

pub struct BoundedNat;
pub struct Pair<L, R>(std::marker::PhantomData<(L, R)>);

pub trait Heap: Sized
+ MapsTmf<BoundedNat>
+ MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>
+ MapsTmf<Pair<Self::LeftOperand, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>
+ MapsTmf<Pair<Self::RightOperand, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>
+ MapsTmf<Pair<Self::Nat, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>
+ MapsTmf<Pair<Self::F, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>
+ MapsTmf<Pair<Self::Plus, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>
+ MapsTmf<Pair<Self::Sum, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>
+ MapsTmf<Pair<<Self as MapsTmf<BoundedNat>>::Tmf, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>
+ MapsTmf<Pair<<Self as MapsTmf<Pair<Self::LeftOperand, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>
+ MapsTmf<Pair<<Self as MapsTmf<Pair<Self::RightOperand, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>
+ MapsTmf<Pair<<Self as MapsTmf<Pair<Self::Nat, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>
+ MapsTmf<Pair<<Self as MapsTmf<Pair<Self::F, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>
+ MapsTmf<Pair<<Self as MapsTmf<Pair<Self::Plus, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>
+ MapsTmf<Pair<<Self as MapsTmf<Pair<Self::Sum, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>
+ MapsTmf<Pair<<Self as MapsTmf<Pair<<Self as MapsTmf<BoundedNat>>::Tmf, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>
+ MapsTmf<<Self as MapsTmf<Pair<<Self as MapsTmf<Pair<Self::Nat, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>>::Tmf>
+ MapsTmf<<Self as MapsTmf<Pair<<Self as MapsTmf<Pair<Self::F, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>>::Tmf>
+ MapsTmf<<Self as MapsTmf<Pair<<Self as MapsTmf<Pair<Self::Plus, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>>::Tmf>
+ MapsTmf<Pair<<Self as MapsTmf<<Self as MapsTmf<Pair<<Self as MapsTmf<Pair<Self::Nat, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>>::Tmf>>::Tmf, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>
+ MapsTmf<Pair<<Self as MapsTmf<<Self as MapsTmf<Pair<<Self as MapsTmf<Pair<Self::F, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>>::Tmf, <Self as MapsTmf<BoundedNat>>::Tmf>>>::Tmf>>::Tmf, <Self as MapsTmf<<Self as MapsTmf<BoundedNat>>::Tmf>>::Tmf>>
{
    // to trigger the perf issue, we do need multiple associated types involved
    // i.e., replacing all of them with Nat makes the issue go away
    type Plus;
    type LeftOperand;
    type RightOperand;
    type F;
    type Sum;
    type Nat;
}

[petervdonovan]

To clarify, I don't have special reasons to believe this is related to the diesel issue, other than that it is an example in which performance scaling is very bad when using -Znext-solver=globally.

[lcnr]

notes:

• the above hang is due to an exponential amount of reruns when handling trait solver cycles
• this is different from the slowdown in diesel which is does not have many such reruns

[lcnr]

This issue, and the related hang in rayon (#109) could likely be fixed by adding some sort of "red-green tracking" to the search graph:

as in, when rerunning, instead of rerunning the whole subgraph, iteratively rerun the cyclic leaves and eagerly return if this part ends up with the same result.

Gonna look into this before stabilization

[lcnr]

trait MapsTmf<L, R> {
    type Tmf;
}
struct A;
struct B;
struct C;
struct D;
struct E;
struct F;
struct G;
struct H;

fn foo<T>()
where
    T: MapsTmf<A, A>,
    T: MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>,
    T: MapsTmf<B, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>,
    T: MapsTmf<C, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>,
    T: MapsTmf<D, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>,
    T: MapsTmf<E, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>,
    T: MapsTmf<F, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>,
    T: MapsTmf<G, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>,
    T: MapsTmf<H, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>,
    T: MapsTmf<<T as MapsTmf<B, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>>::Tmf, <T as MapsTmf<A, A>>::Tmf>,
    T: MapsTmf<<T as MapsTmf<C, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>>::Tmf, <T as MapsTmf<A, A>>::Tmf>,
    T: MapsTmf<<T as MapsTmf<D, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>>::Tmf, <T as MapsTmf<A, A>>::Tmf>,
    T: MapsTmf<<T as MapsTmf<E, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>>::Tmf, <T as MapsTmf<A, A>>::Tmf>,
    T: MapsTmf<<T as MapsTmf<F, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>>::Tmf, <T as MapsTmf<A, A>>::Tmf>,
    T: MapsTmf<<T as MapsTmf<G, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>>::Tmf, <T as MapsTmf<A, A>>::Tmf>,
    T: MapsTmf<<T as MapsTmf<H, <T as MapsTmf<A, <T as MapsTmf<A, A>>::Tmf>>::Tmf>>::Tmf, <T as MapsTmf<A, A>>::Tmf>,
{
}

each additional struct + pair of where-clauses results in a 4x perf cost