Slow compilation

[dragostis]

Using nested tuples in this example leads to painfully long compile times:

use rayon::prelude::*;

fn main() {
    let vec0 = vec![];
    let vec1 = vec![];
    let vec2 = vec![];
    let vec3 = vec![];
    let vec4 = vec![];
    let vec5 = vec![];
    let vec6 = vec![];
    let vec7 = vec![];
    
    (vec0,
    (vec1,
    (vec2,
    (vec3,
    (vec4,
    (vec5,
    (vec6,
    (vec7)))))))).par_extend((1u32..10).into_par_iter().map(|n| (n, (n, (n, (n, (n, (n, (n, n)))))))));
}

[cuviper]

This is kind of impressive! Running nightly-2021-10-01 on my Ryzen 3800X, with cached dependencies, cargo check for this example code takes only 0.36s, while cargo build takes 13.55s.

So I ran cargo +nightly rustc -- -Cno-prepopulate-passes --emit=llvm-ir to see what we're feeding LLVM, and this took 1m 06s to produce a 3.7G file! There are 3.3 million lines in there, the longest having 67K characters thanks to some monster type names. Getting bitcode with --emit=llvm-bc is only 27.02s for a 274M file.

The debug binary is also large at 245M, but most of that is debuginfo. The actual text+data is about 12M.

[cuviper]

I've reduced it somewhat in rayon-rs/rayon#887:

That 8-way unzip is now only 1.5GB with lines up to 17K characters.
Compile time drops from 12.8s to 7.7s debug, 32.1s to 26.9s release.

I'm not sure if there's anything the compiler could do though -- there's just a lot of code to expand here.

In ParallelExtend<T> for Vec<T> in particular, there's a condition on opt_len for two different implementation paths, writing directly for indexed inputs or using intermediate collections otherwise. The indexed case is important for both memory use and performance, but we can't do that for every type of iterator. When nesting unzip-like behavior, that branch means we'll get basically exponential code generation for everything that depends on the iterator type.

Specialization might avoid that, but in the meantime maybe we could add a par_extend_indexed method for statically-known cases like your example. I'm not sure what that will look like for tuple extends yet.

[dragostis]

Thank you for looking into this and writing a patch to improve things.

The par_extend_indexed solution you mentioned, how would that work?

[cuviper]

If you look at the current implementation that matches opt_len, the suggested par_extend_indexed would just be the Some(len) side of that. That None side is probably getting optimized away in LLVM right now, if opt_len gets inlined and it can see when an iterator is always Some, but that's still a heap of code that gets generated first, especially with nested unzips.

I took a look though, and I don't see how to do indexed unzip in rayon's design. The Producer has to create a normal iterator for serial processing after all the parallel splits, but I don't see any way to do that for separate parts of unzipped tuples. It only works for unzip_into_vecs because we know that code never calls with_producer, but we don't know that for generic ParExtend.