Type sizes can get excessively large when chaining lots of operators #129
Description
Continuing discussion from davidlattimore/wild#1489.
When building the tests in the orx-parallel repo, the resulting binary with debug info is more than 3GB. Some of the types are more than 7MB in length.
I've identified one of the tests that is contributing significantly to the size. If I comment out all of the tests in computation_variants/tests and using/computation_variants/tests, then the test binary is 11MiB (or 22MB if I keep the sum tests). If I then restore fallible_option_collect_complete_success, the binary size increases to 1.3GB.
You can also check the length of the longest debug string (generally a type name):
readelf -p .debug_str target/debug/deps/orx_parallel-d0fbf8689c74b07f | wc -LThis shows 69K with just the sum tests and 7.5MB when fallible_option_collect_complete_success is included.
I experimented a bit with a cut-down version of the test.
use crate::*;
use alloc::format;
use alloc::string::{String, ToString};
use alloc::vec::Vec;
fn input<O: FromIterator<String>>(n: usize) -> O {
let elem = |x: usize| (x + 10).to_string();
(0..n).map(elem).collect()
}
#[test]
fn fallible_option_collect_complete_success() {
let n = 57;
let input = || input::<Vec<_>>(n);
let par = input()
.into_par()
.using_clone("XyZw".to_string())
.map(|_, x| (x != "xyz").then_some(x))
.into_fallible_option()
.filter(|_u_, x: &String| !x.ends_with('9'))
.flat_map(|_u, x| [format!("{x}?"), x])
.map(|_u, x| format!("{x}!"))
.filter_map(|_u, x| Some(x));
let output: Option<Vec<_>> = par.collect();
assert_eq!(output, Some(Vec::new()));
}This produces a maximum type name length of 6625949 bytes. If I remove the last filter_map call, then this drops to 1264398. If I also remove the last map call, then it drops to 240407 bytes. So it seems like many of these calls aren't just adding to the type name length, they're multiplying the type name length.
One way to investigate this further is by looking at the type names produced for a less extreme example.
I just tried the following standalone program:
use orx_parallel::*;
struct BarBar(i32);
fn main() {
let par = Vec::new()
.into_par()
.map(|x: i32| x + 5)
.filter_map(|x| Some(BarBar(x + 1)));
let output: Vec<_> = par.collect();
assert!(output.is_empty());
}You can then grep for the distinctive name BarBar in the strings and sort them by their length.
readelf -p .debug_str target/debug/prog1 | grep BarBar | cut -c 13- | awk '{print length " " $0}' | sort -n | awk '{print ""; print $0}' | lessThe longest type name I get there is 3.5K, which is still small enough that reading it isn't out of the questions.
I'm not sure how best to fix it. For the tests, the simplest option would be to not have quite such long chains of operators. It'd be a bit surprising if anyone actually used such a long chain in a real program. But there may be changes that could be made to orx-parallel itself that might reduce the blow-up. I'm not sure what they'd be though.