hitting type_length_limit with relatively few operations

[winstonewert]

I'm running into the type_length_limit when using rayon.

As a simplified instance:

    Vec::<Result<(),()>>::new()
        .into_par_iter()
        .map(|x| x)
        .map(|x| x)
        .map(|x| x)
        .map(|x| x)
        .map(|x| x)
        .map(|x| x)
        .collect::<Result<(), ()>>();

It looks like there is some sort of exponential growth in type names for each additional operation.

Initially I just increased the type length limit, but this seems to result in very slow compiles.

[cuviper]

Have you manually set a lower limit to begin with? The default is 1048576 (= 2²⁰ = 1M), and your simplified instance is accepted on the playground without trouble:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e5b29846cab15818ee5d8c1e9922927e

I gave a talk a PDXRust recently, and at one point I noted a similar situation of really long symbols. I didn't actually exceed type_length_limit with that one either, "only" ~133K, but it probably wouldn't take much to tip it over the edge.
https://gist.github.com/cuviper/99a38550061f1e3513dfe797639ba3ef

[winstonewert]

No, I haven't set a lower limit. After looking around a bit, the issue is that I'm using a different version of Rayon than the playground.

Playground uses:

rayon = "=1.0.3"
rayon-core = "=1.4.1"

I'm on

rayon = "1.1.0"

[winstonewert]

Bisected to this commit:

dd70530

[cuviper]

Oh, I guess playground doesn't update too often. Indeed that fails for me locally with the latest rayon.

error: reached the type-length limit while instantiating `<rayon::vec::SliceDrain<std::res...(), std::result::Result<(), !>>>`
     |
     = note: consider adding a `#![type_length_limit="1400241"]` attribute to your crate

I'm not certain what affected this, but I suspect it was the map consume_iter change in #631, as this would add additional caller and type depth. (edit: matching what you just bisected, thanks!)

[winstonewert]

Also, how did you get the full typename in your case? That mgiht be helpful for the purpose of identifying where I'm inadvertently bloating my types.

[cuviper]

I used cargo rustc -- --emit llvm-ir, which will generate target/debug/deps/*.ll files. The type strings will be in a block at the top of those files.

[cuviper]

Your bisection specifically identified WhileSomeFolder::consume_iter. The closure there will have some Self::consume_iter::<I>::{closure} type, where Self has all of those type parameters expanded. But the closure itself only really needs to be parameterized by the Item type.

So I think we could get some type separation by moving such code into standalone generic functions. Something like (untested):

fn while_some_take_while<T>(full: &AtomicBool) -> impl Fn(&Option<T>) -> bool {
    move |x| // same take-while condition
}

If that helps, we can audit for other eligible cases like this. It will be more cumbersome to write closures this way, but probably beneficial in general to avoid explosion of monomorphization.

[cuviper]

Tested, this does let your example pass:

diff --git a/src/iter/while_some.rs b/src/iter/while_some.rs
index 94ccdb323291..7cea469d7f76 100644
--- a/src/iter/while_some.rs
+++ b/src/iter/while_some.rs
@@ -126,16 +126,9 @@ where
     where
         I: IntoIterator<Item = Option<T>>,
     {
-        let full = self.full;
         self.base = self.base.consume_iter(
             iter.into_iter()
-                .take_while(|x| match *x {
-                    Some(_) => !full.load(Ordering::Relaxed),
-                    None => {
-                        full.store(true, Ordering::Relaxed);
-                        false
-                    }
-                })
+                .take_while(take_while_some(self.full))
                 .map(Option::unwrap),
         );
         self
@@ -149,3 +142,13 @@ where
         self.full.load(Ordering::Relaxed) || self.base.full()
     }
 }
+
+fn take_while_some<T>(full: &AtomicBool) -> impl Fn(&Option<T>) -> bool + '_ {
+    move |x| match *x {
+        Some(_) => !full.load(Ordering::Relaxed),
+        None => {
+            full.store(true, Ordering::Relaxed);
+            false
+        }
+    }
+}

[winstonewert]

In case anyone hits this issue and wants to diagnose what's contributing to their large types, they are free try to super hacky no-guarantees python script I wrote:

https://gist.github.com/winstonewert/08e628102fa169ac9454563585d633fc

With that I've found that I have the same basic problem in a bunch of places in my code. I've got a closure in a function that is generic over a ParallelIterator. By removing a few of these closures, I've got my type names much smaller and compiles times way down.

[winstonewert]

Ideally, the rust compiler would be smart enough to realise that the closure does not actually need to be monomorphized over all of the parameters of the function where it is defined. Is it worth bringing up to the rust compiler team?

[cuviper]

Ideally, the rust compiler would be smart enough to realise that the closure does not actually need to be monomorphized over all of the parameters of the function where it is defined.

I was also considering something like that -- in further digging, I'm seeing large types come from the closure in std::iter::Map::try_fold too. We could potentially reduce that genericity in the standard library with tricks like I'm trying in #673, but closures lose a lot of their ergonomics if this is something frequently needed.

Is it worth bringing up to the rust compiler team?

We can start by asking the team intersection, rayon ∩ rustc -- @nikomatsakis ?

[cuviper]

Here's an example of how the standard library could change for Map:

diff --git a/src/libcore/iter/adapters/mod.rs b/src/libcore/iter/adapters/mod.rs
index c2edcd22f953..71d46d704864 100644
--- a/src/libcore/iter/adapters/mod.rs
+++ b/src/libcore/iter/adapters/mod.rs
@@ -561,6 +561,13 @@ impl<I: fmt::Debug, F> fmt::Debug for Map<I, F> {
     }
 }
 
+fn map_fold<T, B, Acc, R>(
+    mut f: impl FnMut(T) -> B,
+    mut g: impl FnMut(Acc, B) -> R,
+) -> impl FnMut(Acc, T) -> R {
+    move |acc, elt| g(acc, f(elt))
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
     type Item = B;
@@ -575,18 +582,16 @@ impl<B, I: Iterator, F> Iterator for Map<I, F> where F: FnMut(I::Item) -> B {
         self.iter.size_hint()
     }
 
-    fn try_fold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
+    fn try_fold<Acc, G, R>(&mut self, init: Acc, g: G) -> R where
         Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
     {
-        let f = &mut self.f;
-        self.iter.try_fold(init, move |acc, elt| g(acc, f(elt)))
+        self.iter.try_fold(init, map_fold(&mut self.f, g))
     }
 
-    fn fold<Acc, G>(self, init: Acc, mut g: G) -> Acc
+    fn fold<Acc, G>(self, init: Acc, g: G) -> Acc
         where G: FnMut(Acc, Self::Item) -> Acc,
     {
-        let mut f = self.f;
-        self.iter.fold(init, move |acc, elt| g(acc, f(elt)))
+        self.iter.fold(init, map_fold(self.f, g))
     }
 }
 
@@ -599,18 +604,16 @@ impl<B, I: DoubleEndedIterator, F> DoubleEndedIterator for Map<I, F> where
         self.iter.next_back().map(&mut self.f)
     }
 
-    fn try_rfold<Acc, G, R>(&mut self, init: Acc, mut g: G) -> R where
+    fn try_rfold<Acc, G, R>(&mut self, init: Acc, g: G) -> R where
         Self: Sized, G: FnMut(Acc, Self::Item) -> R, R: Try<Ok=Acc>
     {
-        let f = &mut self.f;
-        self.iter.try_rfold(init, move |acc, elt| g(acc, f(elt)))
+        self.iter.try_rfold(init, map_fold(&mut self.f, g))
     }
 
-    fn rfold<Acc, G>(self, init: Acc, mut g: G) -> Acc
+    fn rfold<Acc, G>(self, init: Acc, g: G) -> Acc
         where G: FnMut(Acc, Self::Item) -> Acc,
     {
-        let mut f = self.f;
-        self.iter.rfold(init, move |acc, elt| g(acc, f(elt)))
+        self.iter.rfold(init, map_fold(self.f, g))
     }
 }

That one change seems to help a bit, but we're still very big here. Still, I think I'll send that as a PR to rust and see what the libs team thinks about it.