Nonlinear compile time blow-up with deeply nested types

[sfackler]

Compiling the postgres-tokio crate at sfackler/rust-postgres@d27518b goes from 5 seconds to 45 seconds on nightly if the two .boxed() calls in the middle of this call chain are removed: https://github.com/sfackler/rust-postgres/blob/d27518ba76d76ccaa59b3ccd63e981bd8bd0ef33/postgres-tokio/src/lib.rs#L342-L408.

Looks like 15 seconds is spent in translation item collection, and 39 seconds is spent in translation:

time: 0.004	parsing
time: 0.005	recursion limit
time: 0.000	crate injection
time: 0.001	plugin loading
time: 0.000	plugin registration
time: 0.238	expansion
time: 0.000	maybe building test harness
time: 0.000	maybe creating a macro crate
time: 0.000	checking for inline asm in case the target doesn't support it
time: 0.000	complete gated feature checking
time: 0.008	early lint checks
time: 0.000	AST validation
time: 0.005	name resolution
time: 0.004	lowering ast -> hir
time: 0.002	indexing hir
time: 0.000	attribute checking
time: 0.001	language item collection
time: 0.001	lifetime resolution
time: 0.000	looking for entry point
time: 0.000	looking for plugin registrar
time: 0.001	region resolution
time: 0.000	loop checking
time: 0.000	static item recursion checking
time: 0.005	compute_incremental_hashes_map
time: 0.000	load_dep_graph
time: 0.000	stability index
time: 0.001	stability checking
time: 0.011	type collecting
time: 0.000	variance inference
time: 0.000	impl wf inference
time: 0.021	coherence checking
time: 0.008	wf checking
time: 0.003	item-types checking
time: 0.500	item-bodies checking
time: 0.000	drop-impl checking
time: 0.003	const checking
time: 0.001	privacy checking
time: 0.000	intrinsic checking
time: 0.000	effect checking
time: 0.001	match checking
time: 0.000	liveness checking
time: 0.002	rvalue checking
time: 0.014	MIR dump
  time: 0.001	SimplifyCfg
  time: 0.002	QualifyAndPromoteConstants
  time: 0.002	TypeckMir
  time: 0.000	SimplifyBranches
  time: 0.001	SimplifyCfg
time: 0.006	MIR cleanup and validation
time: 0.006	borrow checking
time: 0.000	reachability checking
time: 0.000	death checking
time: 0.000	unused lib feature checking
time: 1.366	lint checking
time: 0.000	resolving dependency formats
  time: 0.000	NoLandingPads
  time: 0.001	SimplifyCfg
  time: 0.001	EraseRegions
  time: 0.000	AddCallGuards
  time: 0.008	ElaborateDrops
  time: 0.000	NoLandingPads
  time: 0.001	SimplifyCfg
  time: 0.001	InstCombine
  time: 0.000	Deaggregator
  time: 0.000	CopyPropagation
  time: 0.001	SimplifyLocals
  time: 0.000	AddCallGuards
  time: 0.000	PreTrans
time: 0.015	MIR optimisations
  time: 0.001	write metadata
  time: 15.086	translation item collection
  time: 0.020	codegen unit partitioning
  time: 0.022	internalize symbols
time: 39.376	translation
time: 0.000	assert dep graph
time: 0.000	serialize dep graph
  time: 0.089	llvm function passes [0]
  time: 0.037	llvm module passes [0]
  time: 2.148	codegen passes [0]
  time: 0.001	codegen passes [0]
time: 2.432	LLVM passes
time: 0.000	serialize work products
time: 0.084	linking

Things are significantly worse on 1.13 - 2 minutes in translation!

Some discussion in IRC: https://botbot.me/mozilla/rust-internals/2016-12-22/?msg=78294648&page=1

cc @aturon

---

UPDATE: #40280 was closed as a duplicate of this. It had the following sample code:

let &(first, B, C, D, E, F, G, H) = self;
let iter = first.buffers_list();
let iter = iter.chain(B.buffers_list());
let iter = iter.chain(C.buffers_list());
let iter = iter.chain(D.buffers_list());
let iter = iter.chain(E.buffers_list());
let iter = iter.chain(F.buffers_list());
let iter = iter.chain(G.buffers_list());
let iter = iter.chain(H.buffers_list());
Box::new(iter)

--nmatsakis

[nikomatsakis]

Things are significantly worse on 1.13 - 2 minutes in translation!

This may be the effect of the projection cache.

[aturon]

cc @alexcrichton This is obviously a show-stopper for futures.

[nikomatsakis]

I can do some profiling. I've had some plans for improving collection/trans that I think may be related. One question to try and answer is what %age of this is just "we are making more code" vs "we are wasting time doing things in trait selection that could be cached". I have observed the latter from time to time and had some thoughts on how to fix it.

[alexcrichton]

I've also seen this before, with tokio-socks5 as well. Removing just a handful of the trait objects in that file makes the compile time of the crate shoot from 2.34s to 89.52s (!!)

[dwrensha]

Here's a simple example of something that takes a very long time to compile:

future::ok::<(),()>(()).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(())).and_then(|()| Ok(()));

[nikomatsakis]

Closed #40280 as a duplicate, moved some example code into the issue header.

[vorner]

Just a stupid question ‒ the „translation item collection“, which is one of the two culprits here, is listed in the „MIR optimisations“. Does it really have to happen at all on non-optimised debug build?

[bluss]

It's natural to read it that way, but the headers are actual after their group, so it's part of translation

[vorner]

This seems to be hard enough to take some time fixing. So I thought of a workaround, if someone is also interested. It uses the trick with placing trait objects to split the chains of modifiers, but only on testing/debug builds where the compilation speed matters, while it keeps the complex but hopefully faster concrete types in release build:

This one is for streams (that's what I needed), but can obviously work for futures or other things as well:

#[cfg(debug_assertions)]
fn test_boxed<T, E, S>(s: S) -> Box<Stream<Item = T, Error = E>>
    where S: Stream<Item = T, Error = E> + 'static
{
    Box::new(s)
}
#[cfg(not(debug_assertions))]
fn test_boxed<S>(s: S) -> S {
    s
}

(I didn't find any better config option than the debug_assertions, but I hope that one is good enough)