Very bad performance of cargo check on generic code

[maia-s]

I'm writing a parser crate. Yesterday as I fixed some code I ran into a serious performance issue with type checking in the rust compiler. The code linked below takes 50 seconds to run cargo check on my Macbook Pro (M2 Pro).

I've tried to make a minimal reproduction by reducing the code a lot and simplifying it a little. It's still a little big at 575 lines (sorry), but the problematic code is at the start. The function at the beginning is a test function from my crate that tests functionality of combining certain parsers. This function is responsible for the slowness. The two trait implementations following that are traits that implement the functionality that is tested by that function, that I wrote yesterday. The rest of the code is dependencies.

I have a function that tests the same thing with simpler kind of parser that lacks the State associated type (not included). That one compiles in a fraction of a second.

I've hosted the example code on the rust playground, but compile fails there (I assume it times out). To reproduce, make a new library crate, copy the code to lib.rs and run cargo check to see the problem. (The compiled code doesn't work because everything is stubbed out. The issue is the time to check/compile)

Here's the code:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=1c6bb86548e817430c28ce83d51bc65d

% cargo clean && cargo check
     Removed 14 files, 2.9MiB total
    Checking parse v0.0.2 (/Users/maia/Dev/parse)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 50.10s

% cargo clean && cargo +nightly check
     Removed 13 files, 3.4MiB total
    Checking parse v0.0.2 (/Users/maia/Dev/parse)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 52.29s

rustc --version --verbose:

% rustc --version --verbose
rustc 1.78.0 (9b00956e5 2024-04-29)
binary: rustc
commit-hash: 9b00956e56009bab2aa15d7bff10916599e3d6d6
commit-date: 2024-04-29
host: aarch64-apple-darwin
release: 1.78.0
LLVM version: 18.1.2

% cargo +nightly rustc -- --version --verbose
   Compiling parse v0.0.2 (/Users/maia/Dev/parse)
rustc 1.80.0-nightly (c987ad527 2024-05-01)
binary: rustc
commit-hash: c987ad527540e8f1565f57c31204bde33f63df76
commit-date: 2024-05-01
host: aarch64-apple-darwin
release: 1.80.0-nightly
LLVM version: 18.1.4
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.01s

[workingjubilee]

List<TH, TT, SequenceTag>

just confirming my scan of the code here:

this is an HList, right?

[maia-s]

It's the same concept, but my own implementation of it. (I didn't know about the frunk crate before this, and the full type in my crate is a little expanded compared to that)

[workingjubilee]

Yes, that's absolutely fine, I just wanted to confirm my hunch about this being a recursive typechecking case (IIRC we don't necessarily cache certain typechecking results, and I dimly remember something about not being certain such caching would be sound in the current solver).

[maia-s]

I should explain how it works

Parsers combined with the + operator (dubbed parser sequences) are represented as the List type with the SequenceTag tag, like for example List<ParserA, List<ParserB, (), SequenceTag>, SequenceTag> for a list created from ParserA + ParserB. Parser sequences produce a list of outputs, so the previous example parser would output the type List<OutputA, List<OutputB, ()>> (with no tag) if no parsers were discarded.

When parsers are part of a sequence, they can either output something (KEEP_YES) or be discarded (KEEP_NO). Discarded outputs are not part of the final output. For example, in the parser List<ParserA, List<ParserB, List<ParserC, (), SequenceTag>, SequenceTag>, SequenceTag>, if ParserB is a discarding parser, the output woud be List<OutputA, List<OutputC, ()>>. In addition, if a sequence results in a one-element list, the list is flattened to a single value, so if a sequence parser results in List<Output, ()>, the final output type is just Output

In addition to this, parsers can either be resumable or not. The two problematic trait implementations at the top of the example code are examples of resumable parsers. When a resumable parser succeeds parsing with a resumable status, that parser can be resumed. If a parser later on in a sequence fails, the sequence parser will rewind to the nearest resumable parser and resume parsing from there. Resumable parsers have the State associated type that contains the state of the parser (in a sequence, this is a list with the SequenceStateTag tag). The state can be finalized to get the parser output, so it has an associated output type. Type-wise, this all means that states in sequence parsers have to account for discards in their associated output type.

[maia-s]

I reduced compile time by 15 seconds by putting char().opt() into a variable and using that throughout the example function. I also set the input type to &str ahead of time, which saves about two seconds

(It still takes 30 seconds with those changes)