Typechecking memory use

[asajeffrey]

Typechecking the rust library at https://github.com/asajeffrey/wasm/tree/typechecking-blowup uses more than 10G of memory. The program uses a lot of nested generic traits and lifetime polymorphism. The timing details are:

$ multirust run nightly cargo rustc -- -Z time-passes
   Compiling wasm v0.0.1 (file:///home/ajeffrey/github/asajeffrey/wasm)
time: 0.001; rss: 49MB  parsing
time: 0.000; rss: 49MB  configuration 1
time: 0.000; rss: 49MB  recursion limit
time: 0.000; rss: 49MB  gated macro checking
time: 0.000; rss: 49MB  crate injection
time: 0.003; rss: 54MB  macro loading
time: 0.000; rss: 54MB  plugin loading
time: 0.000; rss: 54MB  plugin registration
time: 0.025; rss: 56MB  expansion
time: 0.001; rss: 56MB  complete gated feature checking 1
time: 0.007; rss: 56MB  configuration 2
time: 0.000; rss: 56MB  gated configuration checking
time: 0.003; rss: 56MB  maybe building test harness
time: 0.003; rss: 56MB  prelude injection
time: 0.000; rss: 56MB  checking that all macro invocations are gone
time: 0.000; rss: 56MB  checking for inline asm in case the target doesn't support it
time: 0.000; rss: 56MB  complete gated feature checking 2
time: 0.000; rss: 56MB  const fn bodies and arguments
time: 0.002; rss: 56MB  assigning node ids
time: 0.003; rss: 62MB  lowering ast -> hir
time: 0.001; rss: 62MB  indexing hir
time: 0.000; rss: 62MB  attribute checking
time: 0.002; rss: 62MB  early lint checks
time: 0.001; rss: 60MB  external crate/lib resolution
time: 0.000; rss: 60MB  language item collection
time: 0.005; rss: 68MB  resolution
time: 0.000; rss: 68MB  lifetime resolution
time: 0.000; rss: 68MB  looking for entry point
time: 0.000; rss: 68MB  looking for plugin registrar
time: 0.001; rss: 69MB  region resolution
time: 0.000; rss: 69MB  loop checking
time: 0.000; rss: 69MB  static item recursion checking
time: 0.003; rss: 71MB  type collecting
time: 0.000; rss: 71MB  variance inference
time: 0.027; rss: 89MB  coherence checking
time: 0.014; rss: 89MB  wf checking
time: 0.004; rss: 89MB  item-types checking

at which point the process starts using large amounts of time and memory.

The same behaviour happens with nightly-2015-12-01, so this is not part of the recent rewrite of typechecking.

Discussed on irc with @eddyb, @Manishearth and @aturon.

[nikomatsakis]

cc me

[nikomatsakis]

On IRC, @asajeffrey posted this self-contained example that exhibits the same phenomena:

pub trait Upcast<T> {
    fn upcast(self) -> T;
}

impl<S1, S2, T1, T2> Upcast<(T1, T2)> for (S1,S2)
    where S1: Upcast<T1>,
          S2: Upcast<T2>,
{
    fn upcast(self) -> (T1, T2) { (self.0.upcast(), self.1.upcast()) }
}

impl Upcast<()> for ()
{
    fn upcast(self) -> () { () }
}

pub trait ToStatic {
    type Static: 'static;
    fn to_static(self) -> Self::Static where Self: Sized;
}

impl<T, U> ToStatic for (T, U)
    where T: ToStatic,
          U: ToStatic
{
    type Static = (T::Static, U::Static);
    fn to_static(self) -> Self::Static { (self.0.to_static(), self.1.to_static()) }
}

impl ToStatic for ()
{
    type Static = ();
    fn to_static(self) -> () { () }
}


trait Factory {
    type Output;
    fn build(&self) -> Self::Output;
}

impl<S,T> Factory for (S, T)
    where S: Factory,
          T: Factory,
          S::Output: ToStatic,
          <S::Output as ToStatic>::Static: Upcast<S::Output>,
{
    type Output = (S::Output, T::Output);
    fn build(&self) -> Self::Output { (self.0.build().to_static().upcast(), self.1.build()) }
}

impl Factory for () {
    type Output = ();
    fn build(&self) -> Self::Output { () }
}

fn main() {
    // Any more parens and it triggers the playpen timeout!
    let it = ((((((),()),()),()),()),());
    it.build();
}

[asajeffrey]

You beat me to it :) https://play.rust-lang.org/?gist=5183e32b3f0fcdfccf61

[asajeffrey]

There is a work-around for this example: https://play.rust-lang.org/?gist=ed22452c4eda71821a6d

[asajeffrey]

Sad to say the work-around doesn't scale up completely. The problem is the interaction between this issue and #30867 (comment).

The work-around for this issue is to make what were type parameters into associated types, the work-around for #30867 (comment) is to turn what were associated types into type parameters. There is a tension here.

[asajeffrey]

Chaining iterators has a similar problem: https://play.rust-lang.org/?gist=a0c05fbf5c43234fb7c3

[asajeffrey]

A possible work-around for chaining iterators is to distinguish between top-down and bottom-up iterators: https://play.rust-lang.org/?gist=8532619e7f8bae0ffbef

[asajeffrey]

Separating out the projection for the iterator from iterator function itself seems to do the trick... https://play.rust-lang.org/?gist=1cf9886dd074e073cd6a

[asajeffrey]

I implemented the work-around for parsell. The trick was to separate out bottom-up computation of associated types from their top-down use as type parameters. You can see this, for example, in http://asajeffrey.github.io/parsell/target/doc/parsell/trait.StatefulInfer.html which used to be one trait, but is now given as the union of a trait for bottom-up calculation of an Output associated type http://asajeffrey.github.io/parsell/target/doc/parsell/trait.HasOutput.html, and a trait for top-down use of that type http://asajeffrey.github.io/parsell/target/doc/parsell/trait.Stateful.html.

It's a bit round-about, but it does the job of reducing type-checking space/time.

[asajeffrey]

The work-around took the compile time for https://github.com/asajeffrey/wasm/tree/9297d84654c74d24f1f8cc0ff96e468a39c12bb2 down from 10G to about 200M. It compiles in about 45 sec, which isn't perfect but is a lot better than never terminating, which is what was happening before.

[nikomatsakis]

As part of some work towards lazy normalization, I added a cache to the associated type projection machinery. This achieved a 10x improvement on the test case that @asajeffrey posted a little while back (with two levels of parens added):

lunch-box. time rustc --stage0 ~/tmp/issue-31849.rs

real    0m6.787s
user    0m6.538s
sys     0m0.236s
lunch-box. time rustc --stage2 ~/tmp/issue-31849.rs

real    0m0.663s
user    0m0.601s
sys     0m0.064s