rust-lang / rust-lang/rust

Exponential time complexity for parser combinator with RPITIT

Open
#132,991 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

C-bug E-needs-mcve F-return_position_impl_trait_in_trait I-compiletime T-compiler
Dominant language
Rust
Stars
119k
Forks
16.1k
PR metrics pending

Description

The egglog parser was recently rewritten from a generated parser to a parser combinator. One commit changed the map combinator from a free function to a trait method (RPIT -> RPITIT), which caused a massive compile-time regression https://github.com/egraphs-good/egglog/issues/468, going from a few seconds to 40s+.

Adding a single no-op map increases compile time to 3m30s+

More info in the repo: https://github.com/DaniPopes/egglog-rpitit-repro

@rustbot label +I-compiletime +F-return_position_impl_trait_in_trait

Meta

rustc --version --verbose:

rustc 1.84.0-nightly (f7273e004 2024-11-12)
binary: rustc
commit-hash: f7273e0044ad8f35ad27282e4ab776af50b61a54
commit-date: 2024-11-12
host: x86_64-unknown-linux-gnu
release: 1.84.0-nightly
LLVM version: 19.1.3
Copy of README.md

Massive compile time difference between RPITIT "map" closure and a manually defined Map struct that implements the traits.

Extracted from egglog @ ca52ac13cb3c0bbacc8e7cc540789521d1019bd2. Issue: https://github.com/egraphs-good/egglog/issues/468.

Note that unboxed closures etc is not required, as seen in https://github.com/egraphs-good/egglog/pull/470 this can be fixed on stable by changing the definition but I opted to use the nightly feature to make the diff smaller.
It can also be fixed by moving map outside of the trait.

Reproduce:

# Takes 48s
time cargo clean && cargo build

# Takes 0.2s
git restore . && git apply fix.patch
time cargo clean && cargo build

# Takes 3m30s+ for a single extra no-op map
git restore . && git apply worse.patch
time cargo clean && cargo build

On nightly:

rustc -Vv
rustc 1.84.0-nightly (f7273e004 2024-11-12)
binary: rustc
commit-hash: f7273e0044ad8f35ad27282e4ab776af50b61a54
commit-date: 2024-11-12
host: x86_64-unknown-linux-gnu
release: 1.84.0-nightly
LLVM version: 19.1.3

On stable (with RUSTC_BOOTSTRAP=1):

rustc +stable -Vv
rustc 1.82.0 (f6e511eec 2024-10-15)
binary: rustc
commit-hash: f6e511eec7342f59a25f7c0534f1dbea00d01b14
commit-date: 2024-10-15
host: x86_64-unknown-linux-gnu
release: 1.82.0
LLVM version: 19.1.1

Output of cargo rustc -- -Ztime-passes:

time:   0.000; rss:   83MB ->   87MB (   +4MB)  setup_global_ctxt
time:   0.006; rss:   87MB ->  117MB (  +31MB)  expand_crate
time:   0.006; rss:   87MB ->  117MB (  +31MB)  macro_expand_crate
time:   0.003; rss:  117MB ->  125MB (   +7MB)  late_resolve_crate
time:   0.003; rss:  117MB ->  125MB (   +7MB)  resolve_crate
time:   0.005; rss:  125MB ->  131MB (   +6MB)  looking_for_entry_point
time:   0.005; rss:  125MB ->  131MB (   +6MB)  unused_lib_feature_checking
time:   0.006; rss:  125MB ->  131MB (   +6MB)  misc_checking_1
time:   0.020; rss:  131MB ->  169MB (  +38MB)  coherence_checking
time:   0.064; rss:  131MB ->  192MB (  +61MB)  type_check_crate
time:   0.026; rss:  192MB ->  199MB (   +7MB)  MIR_borrow_checking
time:  43.618; rss:  199MB ->  208MB (   +9MB)  MIR_effect_checking
time:   0.004; rss:  208MB ->  208MB (   +0MB)  privacy_checking_modules
time:   0.003; rss:  208MB ->  208MB (   +0MB)  lint_checking
time:   0.000; rss:  208MB ->  208MB (   +0MB)  check_lint_expectations
time:   0.005; rss:  208MB ->  208MB (   +1MB)  misc_checking_3
time:   0.002; rss:  208MB ->  210MB (   +1MB)  monomorphization_collector_graph_walk
time:   0.000; rss:  212MB ->  219MB (   +8MB)  write_allocator_module
time:   0.003; rss:  219MB ->  227MB (   +8MB)  compile_first_CGU_batch
time:   0.006; rss:  219MB ->  247MB (  +28MB)  codegen_to_LLVM_IR
time:   0.011; rss:  208MB ->  247MB (  +39MB)  codegen_crate
time:   0.000; rss:  247MB ->  246MB (   -1MB)  check_dirty_clean
time:   0.000; rss:  246MB ->  246MB (   +0MB)  incr_comp_persist_dep_graph
time:   0.005; rss:  227MB ->  246MB (  +19MB)  LLVM_passes
time:   0.002; rss:  246MB ->  243MB (   -3MB)  encode_query_results
time:   0.002; rss:  246MB ->  243MB (   -3MB)  incr_comp_serialize_result_cache
time:   0.002; rss:  246MB ->  243MB (   -3MB)  incr_comp_persist_result_cache
time:   0.002; rss:  247MB ->  243MB (   -4MB)  serialize_dep_graph
time:   0.003; rss:  243MB ->  202MB (  -41MB)  free_global_ctxt
time:   0.031; rss:  202MB ->  202MB (   +0MB)  run_linker
time:   0.031; rss:  202MB ->  202MB (   +0MB)  link_binary
time:   0.031; rss:  202MB ->  202MB (   +0MB)  link_crate
time:   0.032; rss:  202MB ->  202MB (   +0MB)  link
time:  43.784; rss:   31MB ->  147MB ( +116MB)  total

samply profile: https://share.firefox.dev/3O7AzuO

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the linked egglog-rpitit-repro repository and run the documented cargo clean && cargo build comparisons for the base, fixed, and worse patches. Use the reported -Ztime-passes output, especially MIR_effect_checking, and the linked samply profile to investigate the RPITIT map regression. Done means the excessive compile-time growth is explained and resolved without the reported multi-minute build.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers, performance
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.