Where clauses increase compilation time and memory use dramatically. #26325

Closed
paholg opened this Issue Jun 15, 2015 · 9 comments

Comments

Projects
None yet
9 participants
@paholg

paholg commented Jun 15, 2015

When implementing a trait with a member function (vs. one without), the compiler requires more information and takes much longer to compile.

Consider the following two implementations of addition over Peano numbers as types:

First, using std::ops::Add: http://is.gd/7tO1cK

Second, using a custom trait for addition, AddPeano, that has only an associated type and no member functions: http://is.gd/byhqSn

The key difference is here:

Using AddPeano,

impl<Lhs: Peano + AddPeano<Rhs>, Rhs: Peano> AddPeano<Rhs> for Succ<Lhs> {
    type Output = Succ<<Lhs as AddPeano<Rhs>>::Output>;
}

Using std::ops::Add,

impl<Lhs: Peano + Add<Rhs>, Rhs: Peano> Add<Rhs> for Succ<Lhs> where <Lhs as Add<Rhs>>::Output: Peano {
    type Output = Succ<<Lhs as Add<Rhs>>::Output>;
    fn add(self, rhs: Rhs) -> Self::Output { unreachable!() }
}

Without the where clause, the compiler gives the error

error: the trait `Peano` is not implemented for the type `<Lhs as core::ops::Add<Rhs>>::Output`

In main() for both of those examples, the Add traits are used for successive doubling until the number 32 is reached. Using AddPeano, playpen finishes in moments, whereas using Add it triggers playpen's timeout and fails to compile.

I have had similar results locally ... even using up 8 GB of ram in the case of the std::ops version while the version without a function would compile virtually instantly.

@Aatch

This comment has been minimized.

Show comment
Hide comment
@Aatch

Aatch Jun 16, 2015

Contributor

It actually has nothing to do with the presence/absence of a method, this compiles in a similar amount of time: https://play.rust-lang.org/?gist=d9c18a3c48d6c0584579&version=nightly

It's the where clause, which, yes, is required in this case, but only due to the method returning Self::Output. I've updated the title of the issue to better reflect this.

Contributor

Aatch commented Jun 16, 2015

It actually has nothing to do with the presence/absence of a method, this compiles in a similar amount of time: https://play.rust-lang.org/?gist=d9c18a3c48d6c0584579&version=nightly

It's the where clause, which, yes, is required in this case, but only due to the method returning Self::Output. I've updated the title of the issue to better reflect this.

@Aatch Aatch changed the title from The compiler requires more information and can take much longer to compile when implementing a trait with a member function vs. one without. to Where clauses increase compilation time and memory use dramatically. Jun 16, 2015

@Aatch Aatch added the I-slow label Jun 16, 2015

@paholg

This comment has been minimized.

Show comment
Hide comment
@paholg

paholg Jun 16, 2015

@Aatch I didn't think to specifically test whether it was the added information in the where clause or the function that made it slower, but that makes sense.

The big question to me is why does the function having output type Self::Output cause the compiler to be confused and require the statement in the where clause?

In the AddPeano example, we still do Succ<<Lhs as AddPeano<Rhs>>::Output>, so <Lhs as AddPeano<Rhs>>::Output must still impl Peano, but the compiler is able to infer that it does.

Similarly, here is another example that I've just stumbled across:

trait Marker {}
struct Bob;
impl Marker for Bob {}

trait DoNothing {
    type Output;
}
impl DoNothing for Bob {
    type Output = Bob;
}
struct Dude<M: Marker>(M);

// Conflicting implementation with this line uncommented,
// Marker not implemented for <Bob as DoNothing>::Output error with it commented
impl Marker for <Bob as DoNothing>::Output {}

const b: Dude<<Bob as DoNothing>::Output> = Dude(Bob);

fn main() {
}

The compiler is able to check that <Bob as DoNothing>::Output implements Marker, but it is seemingly unable to infer it.

paholg commented Jun 16, 2015

@Aatch I didn't think to specifically test whether it was the added information in the where clause or the function that made it slower, but that makes sense.

The big question to me is why does the function having output type Self::Output cause the compiler to be confused and require the statement in the where clause?

In the AddPeano example, we still do Succ<<Lhs as AddPeano<Rhs>>::Output>, so <Lhs as AddPeano<Rhs>>::Output must still impl Peano, but the compiler is able to infer that it does.

Similarly, here is another example that I've just stumbled across:

trait Marker {}
struct Bob;
impl Marker for Bob {}

trait DoNothing {
    type Output;
}
impl DoNothing for Bob {
    type Output = Bob;
}
struct Dude<M: Marker>(M);

// Conflicting implementation with this line uncommented,
// Marker not implemented for <Bob as DoNothing>::Output error with it commented
impl Marker for <Bob as DoNothing>::Output {}

const b: Dude<<Bob as DoNothing>::Output> = Dude(Bob);

fn main() {
}

The compiler is able to check that <Bob as DoNothing>::Output implements Marker, but it is seemingly unable to infer it.

@arielb1

This comment has been minimized.

Show comment
Hide comment
@arielb1

arielb1 Jun 16, 2015

Contributor

@paholg

The where clause is supposed to always be needed. It isn't needed when you don't have a method because of a bug.

Your last example is another (separate) bug.

Contributor

arielb1 commented Jun 16, 2015

@paholg

The where clause is supposed to always be needed. It isn't needed when you don't have a method because of a bug.

Your last example is another (separate) bug.

@jroesch

This comment has been minimized.

Show comment
Hide comment
@jroesch

jroesch Jun 23, 2015

Member

The final example no longer compiles. When you write programs in the type system the type checker has to execute said programs via type checking so it is expected that it would impact compilation performance. Overall we have a lot of room for optimization in the where clause implementation but I'm not sure if this issue has a directly actionable solution.

Member

jroesch commented Jun 23, 2015

The final example no longer compiles. When you write programs in the type system the type checker has to execute said programs via type checking so it is expected that it would impact compilation performance. Overall we have a lot of room for optimization in the where clause implementation but I'm not sure if this issue has a directly actionable solution.

@paholg paholg referenced this issue in paholg/typenum Oct 7, 2015

Closed

Performance is still a problem #20

@llogiq

This comment has been minimized.

Show comment
Hide comment
@llogiq

llogiq Oct 8, 2015

Contributor

This is really hurting us freaks who try to implement any type-level shenanigans – I believe this also affects compile times for others in the wild.

I'm not sure if this issue has a directly actionable solution.

Currently having those where clauses in the code means compilation time is growing exponentially with the number of types used. I'm not completely privvy to the details of the type checker implementation, but I'm quite certain the search space could use a good bit of pruning.

Contributor

llogiq commented Oct 8, 2015

This is really hurting us freaks who try to implement any type-level shenanigans – I believe this also affects compile times for others in the wild.

I'm not sure if this issue has a directly actionable solution.

Currently having those where clauses in the code means compilation time is growing exponentially with the number of types used. I'm not completely privvy to the details of the type checker implementation, but I'm quite certain the search space could use a good bit of pruning.

@DemiMarie

This comment has been minimized.

Show comment
Hide comment
@DemiMarie

DemiMarie Oct 11, 2015

Contributor

If Rust is anything like ML, then typechecking is EXP-complete and provably intractable in the worst case. However, this involves cases where types turn out to be exponentially large and so probably does not apply here.

Contributor

DemiMarie commented Oct 11, 2015

If Rust is anything like ML, then typechecking is EXP-complete and provably intractable in the worst case. However, this involves cases where types turn out to be exponentially large and so probably does not apply here.

@jonas-schievink

This comment has been minimized.

Show comment
Hide comment
@jonas-schievink

jonas-schievink Oct 11, 2015

Contributor

Adding the same where-clause to the AddPeano example reproduces the same behaviour. However, if the where-clause is something like where Lhs: Peano, Rhs: Peano, Succ<Lhs>: Peano, Succ<Rhs>: Peano (ie no projections), it still typechecks fast. Maybe #20304 would solve this?

Contributor

jonas-schievink commented Oct 11, 2015

Adding the same where-clause to the AddPeano example reproduces the same behaviour. However, if the where-clause is something like where Lhs: Peano, Rhs: Peano, Succ<Lhs>: Peano, Succ<Rhs>: Peano (ie no projections), it still typechecks fast. Maybe #20304 would solve this?

@brson

This comment has been minimized.

Show comment
Hide comment
@brson

brson Mar 23, 2017

Contributor

This hasn't been updated in a long time. Anybody have new numbers?

Contributor

brson commented Mar 23, 2017

This hasn't been updated in a long time. Anybody have new numbers?

@brson brson added the P-low label Mar 23, 2017

@paholg

This comment has been minimized.

Show comment
Hide comment
@paholg

paholg Mar 24, 2017

It seems fixed; the example that used to timeout and gobble ram now has no problems compiling.

paholg commented Mar 24, 2017

It seems fixed; the example that used to timeout and gobble ram now has no problems compiling.

@paholg paholg closed this Mar 24, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment