Very slow `EverInitializedPlaces` analysis on async fn with many awaits

[diondokter]

I have a tool that generates code and for debugging purposes that has a function that summarizes the state of the whole thing. So that's an async function with potentially a lot of awaits.

I posted in this issue first: #138828 (comment)
But then was advised to open a new issue. And after that I was able to reduce it much further.

I tried this code:
https://gist.github.com/diondokter/ec4659f8b80b3f92643138606df5fa93#file-repro-rs
(Very long so in a gist)
rustc +nightly compile_time_explosion.rs --edition 2024 -Ztime-passes

I expected to see this happen: relatively normal compile times

What happens instead is that this takes 21 seconds.

...
time:   0.000; rss:   33MB ->   32MB (   -1MB)  drop_ast
time:   0.000; rss:   32MB ->   32MB (   +0MB)  looking_for_entry_point
time:   0.000; rss:   32MB ->   32MB (   +0MB)  looking_for_derive_registrar
time:   0.000; rss:   33MB ->   33MB (   +0MB)  unused_lib_feature_checking
time:   0.003; rss:   32MB ->   33MB (   +1MB)  misc_checking_1
time:  21.327; rss:   33MB ->   93MB (  +60MB)  coherence_checking
time:   0.000; rss:   93MB ->   93MB (   +0MB)  emit_ast_lowering_delayed_lints
time:  21.328; rss:   33MB ->   93MB (  +60MB)  type_check_crate
time:   0.506; rss:   93MB ->  100MB (   +7MB)  MIR_borrow_checking
time:   0.000; rss:  100MB ->  100MB (   +0MB)  layout_testing
time:   0.000; rss:  100MB ->  100MB (   +0MB)  abi_testing
time:   0.000; rss:  100MB ->  100MB (   +0MB)  crate_lints
time:   0.003; rss:  100MB ->  101MB (   +0MB)  module_lints
...

The coherence checking also seems to be quadratic or something.
This is the compile time changes in my tool:

num awaits	num awaits %	time	time %
1000	100%	59s	100%
1100	110%	75s	127%
1200	120%	99s	170%

[Dirbaio]

perf flamegraph

it's check_well_formed -> check_opaque -> type_of_opaque -> mir_borrowck

[lqd]

Fun fact, this is not coherence -- due to queries, don't use -Ztime-passes to pinpoint where the compiler spends its time, but -Zself-profile -- but from move/init in borrowck.

It's from the EverInitializedPlaces dataflow analysis to be precise, and the dataflow framework in general, which becomes slow on some CFG shapes. It's actually one of the slowest parts of borrowck (though it's not about checking borrows), and this is not even the worst case I ever saw: it takes 40s in hsc.

The good news is I have (I think/hope :3) a fix in flight which turns that 40s outlier into 100ms, and your 23s case into 23ms.

It's not really borrowck's fault but I'll still mark it as such, we don't have a label for dataflow issues AFAICT.
@rustbot label -A-coherence +A-borrow-checker

[diondokter]

Ah, that's good to know! The perf issue that was reported to me mentioned it was taking 3 minutes. But they didn't share their code, so I don't know exactly how many awaits they have

[rockboynton]

✋🏻 reporter here

I count 1364 await points in the generated code that took ~3 minutes to compile

[lqd]

(To be clear, it's not related to the awaits per se -- the hsc case I mentioned doesn't use any -- but to the numbers of locals, move paths, init paths, and CFG shape)

Compilation times in general depend on the size of the function. So a way to improve the compiler speed for your tool could be to generate multiple smaller functions instead of a big one, if at all possible.