4 ms·

Warp uses a lot of generics, which can produce extremely deep and long types. In turn, these cause a particular compile stage to take a long time (> 40 seconds)

Warp uses a lot of generics, which can produce extremely deep and long types. In turn, these cause a particular compile stage to take a long time (> 40 seconds). Boxing disguises/splits the chain by taking a pointer to a trait object, which doesn't require the same depth of checks. (This is especially important if the algorithm is superlinear, which is implied but not stated in the article.)

Smaug123 5y ago
(The underlying issue is https://github.com/rust-lang/rust/issues/91598 https://github.com/rust-lang/rust/issues/91598.)
estebank 5y ago
The problem is not the length of the types, but rather the number of "obligations" introduced by each type. If you have Foo<Bar<Baz>>, and each one of those types has a single trait bound, the resulting type now has >3 obligations to evaluate (> because you also have Sized and WF checks for them as well). The deeper the type depth, the more potential obligations you end up with, which have in some cases can have exponential evaluation. We have caching in place to only evaluate a given obligation once, but it can't always kick in. I'm sure there are still things we can improve there, though.
- lordnacho 5y ago
  Still not sure I get it. If I box a generic, why does the time to evaluate the bounds change?
  - estebank 5y ago
    If you have T and box it, a new type Box<T> is created. The compiler not only has to do typeck to make sure that you're using Box<T> in both sides of an assignment, it also has to evaluate the bound on Box (in this case it's only that it is Well-Formed, an internal concept, because Box accepts unsized types, struct Box<A: ?Sized>), but also evaluate all the bounds on T. If T: Foo, and the type you used for T is Bar<X: Qux>, then by the time rustc actually has to confirm the type Box<Bar<X>> is correct, it has to check that Bar<X>: Foo and X: Qux, but you never wrote those close to the Box, these flow from other definitions. Multiply for every type with an explicit or implicit where clause (T: Foo, where <A as B>::C: D, associated types, etc.).
    - estebank 5y ago
      Another thing: you can also coherce a type to Box<dyn Trait>, which has the side effect of erasing any obligations not directly mentioned by Trait, which is why one of the solutions to the perf regression (or bad compilation times in general), is to use trait objects more often.

Smaug123 5y ago

(The underlying issue is https://github.com/rust-lang/rust/issues/91598 https://github.com/rust-lang/rust/issues/91598.)

estebank 5y ago

The problem is not the length of the types, but rather the number of "obligations" introduced by each type. If you have Foo<Bar<Baz>>, and each one of those types has a single trait bound, the resulting type now has >3 obligations to evaluate (> because you also have Sized and WF checks for them as well). The deeper the type depth, the more potential obligations you end up with, which have in some cases can have exponential evaluation. We have caching in place to only evaluate a given obligation once, but it can't always kick in. I'm sure there are still things we can improve there, though.

lordnacho 5y ago
Still not sure I get it. If I box a generic, why does the time to evaluate the bounds change?
- estebank 5y ago
  If you have T and box it, a new type Box<T> is created. The compiler not only has to do typeck to make sure that you're using Box<T> in both sides of an assignment, it also has to evaluate the bound on Box (in this case it's only that it is Well-Formed, an internal concept, because Box accepts unsized types, struct Box<A: ?Sized>), but also evaluate all the bounds on T. If T: Foo, and the type you used for T is Bar<X: Qux>, then by the time rustc actually has to confirm the type Box<Bar<X>> is correct, it has to check that Bar<X>: Foo and X: Qux, but you never wrote those close to the Box, these flow from other definitions. Multiply for every type with an explicit or implicit where clause (T: Foo, where <A as B>::C: D, associated types, etc.).
  - estebank 5y ago
    Another thing: you can also coherce a type to Box<dyn Trait>, which has the side effect of erasing any obligations not directly mentioned by Trait, which is why one of the solutions to the perf regression (or bad compilation times in general), is to use trait objects more often.