Large memory usage and long time on compiling large number of println

[upsuper]

Not sure whether it's a known bug.

I tried this code:

fn main() {
    println!("hello world!"); // repeat 16384 times
}

(To save you some time, you can download the file here directly rather than generating it yourself.)

I expected to see this happen: it should take reasonable amount of memory and reasonable time to compile.

Instead, this happened: on my machine, I saw it took up to 34GB memory and 2.5min of time just to compile this.

Meta

rustc --version --verbose:

rustc 1.52.1 (9bc8c42bb 2021-05-09)
binary: rustc
commit-hash: 9bc8c42bb2f19e745a63f3445f1ac248fb015e53
commit-date: 2021-05-09
host: x86_64-unknown-linux-gnu
release: 1.52.1
LLVM version: 12.0.0

[weiby3]

Another test, dbg! used more than 40G MEM.
test scripts:

echo 'fn main() {' > hw.rs
for i in {0..16384}
do
echo '    dbg!("Hello, world!");' >> hw.rs
done
echo '}' >> hw.rs
/usr/bin/time -f "%Uuser %Ssystem %Eelapsed %PCPU (%Xtext+%Ddata %Mmax)k\n%Iinputs+%Ooutputs (%Fmajor+%Rminor)pagefaults %Wswaps\nUsed %MKbytes Max Resident MEM" rustc hw.rs

log:

1044.19user 24.17system 18:08.63elapsed 98%CPU (0text+0data 39245668max)k
129736inputs+0outputs (2010major+17465633minor)pagefaults 0swaps
Used 39245668Kbytes Max Resident MEM

$ grep "Out of memory" /var/log/messages
Jun 12 19:58:32 centos kernel: Out of memory: Kill process 31123 (rustc) score 937 or sacrifice child

[oxalica]

I simplify the code to tons of &"foo", which is unexpectedly costly in both memory and time. (But not sure if it's the root cause of original code. The original code expands to &["hello"], and also have lifetime-generic function calls)

Generator script:

#!/usr/bin/env bash
exec >test.rs
echo 'fn main() {'
for i in $(seq 16384); do
    echo '&"foo";'
done
echo '}'

It costs 2.6GB memory and 50s to compile. While adding one more reference (&&"foo"; per line), it costs 4.3GB memory and 86s to compile.

For comparation, &&1i32; cost 300MB memory and 3.4s to compile.

[inquisitivecrystal]

@rustbot label I-compilemem I-compiletime T-compiler

[nbdd0121]

Profiling shows that 97% of the time is spent in mir_borrowck.

[nbdd0121]

Did some further analysis with perf, and get this call stack:

  Children      Self  Comma  Shared Object                        Symbol
-   97.02%     0.00%  rustc  librustc_driver-3894de7c87fd4580.so  [.] rustc_mir::borrow_check::do_mir_borrowck
   - 97.02% rustc_mir::borrow_check::do_mir_borrowck
      - 96.54% rustc_mir::borrow_check::nll::compute_regions
         - 95.54% rustc_mir::borrow_check::type_check::type_check
            - 95.38% <rustc_mir::borrow_check::type_check::TypeVerifier as rustc_middle::mir::visit::Visitor>::visit_body
               - 95.35% <rustc_mir::borrow_check::type_check::TypeVerifier as rustc_middle::mir::visit::Visitor>::visit_rvalue
                  - 95.26% <rustc_mir::borrow_check::type_check::TypeVerifier as rustc_middle::mir::visit::Visitor>::visit_constant
                       77.10% rustc_index::bit_set::HybridBitSet<T>::insert
                     + 6.18% <rustc_mir::borrow_check::type_check::TypeVerifier as rustc_middle::mir::visit::Visitor>::visit_body

Majority of the time is spent in <rustc_mir::borrow_check::type_check::TypeVerifier as rustc_middle::mir::visit::Visitor>::visit_constant, and a quite significant portion is in rustc_index::bit_set::HybridBitSet<T>::insert, presumably when updating liveness_constraints.

visit_constant is highly inlined, so I am not very confident about my analysis, but it seems to me that it's sanitize_promoted that uses majority of the time. There is an for live_region in liveness_constraints.rows(), perhaps means that the algorithm is O(N^2) for the MCVE above (N constants * N regions)? EDIT: looked again and it doesn't seem to be O(N^2) since swap_constraints means that each "promoted" has its own liveness_constraints.

I don't understand the code well enough to make any conclusions or make any changes, so perhaps someone more familiar with this code could give some hints.

[memoryruins]

#50994 uses 5,000 println!("hello world!");s to benchmark the compiler and compares debug/opt builds (though note the profiles are a few years old). Should the investigation here continue in that issue?

[nbdd0121]

#50994 uses 5,000 println!("hello world!");s to benchmark the compiler and compares debug/opt builds (though note the profiles are a few years old). Should the investigation here continue in that issue?

The example by @oxalica shows that this issue has nothing to do with println! but with references.

#50994 is related to LLVM performance issue while this one is related to borrow checking. Note that when that issue is posted, Rust does not yet have stable NLL, so it's certainly a different issue from this one.

[memoryruins]

Both issues were opened with the premise of benchmarking the compiler with the same println! test case. The other issue is not only about LLVM. Its debug profiles suggest something similar to @oxalica 's findings and your perf profile. As noted, that's happening in a different part of rustc now, which is relevant information to post on the other issue, but it does not mean the two issues are different. Edited for clarity.