resurrectedcyb

Joined 1 year ago

Karma

Submissions

Member since

Jul 7

Recent submissions

That project had 'cargo check' take 15-20 minutes, though it might not have been indicative, the submitter posted an update about how it was fixed.

This may be a better example.

https://github.com/rust-lang/rust/issues/132064

>cargo check with 1.82: 6m 19s

>cargo check with 1.81: 1m 22s

It may be difficult to fix.

https://github.com/rust-lang/rust/issues/132064#issuecomment...

>Triage notes (AFAIUI): #132625 is merged, but the compile time is not fully clawed back as #132625 is a compromise between (full) soundness and performance in favor of a full revert (full revert would bring back more soundness problems AFAICT)

Update: They fixed it, but another issue surfaced, possibly related, as I read the comments.

Comment · 1 year ago

Interesting. The change to sets of loans is interesting. Datalog, related to Prolog, is not a language family I have a lot of experience with, only a smidgen. They use some kind of solving as I recall, and are great at certain types of problems and explorative programming. Analyzing the performance of them is not always easy, but they are also often used for problems that already are exponential.

I read something curious.

https://users.rust-lang.org/t/polonius-is-more-ergonomic-tha...

>I recommend watching the video @nerditation linked. I believe Amanda mentioned somewhere that Polonius is 5000x slower than the existing borrow-checker; IIRC the plan isn't to use Polonius instead of NLL, but rather use NLL and kick off Polonius for certain failure cases.

That slowdown might be temporary, as it is optimized over time, if I had to guess, since otherwise there might then be two solvers in compilers for Rust. It would be line with some other languages if the worst-case complexity class is something exponential.

Comment · 1 year ago

I have actually seen a few posts here and there of 'cargo check' being slow. I have also heard of complaints of rust-analyzer being slow, though rust-analyzer may be doing more than just 'cargo check'.

https://www.reddit.com/r/rust/comments/1daip72/rust_checkrun...

May not be indicative, not sure what crate the author was using.

Comment · 1 year ago

Is there any tool for Rust that does profiling that detects what part of compilation time is caused by what? Like, a tool that reports:

- Parsing: x ms

- Type checking: y ms

- LLVM IR generation: z ms

And have there been any statistics done on that across open-source projects, like mean, median, percentiles and so on?

I am asking because it should depend a lot on each project what is costly in compile time, making it more difficult to analyse. And I am also curious about how many projects are covered by "edge cases", if it is 1%, 0.1%, 0.01%, and so on.

Comment · 1 year ago

I do not know if the borrow checker and Rust's type system have been formalized. There are stacked borrows and tree borrows, and other languages experimenting with features similar to borrow checking, but without formal algorithms like Algorithm W or J for Hindley-Milner, or formalizations like of Hindley-Milner and problems like typability for them, I am not sure how one can prove the complexity class of the borrow checking problem nor a specific algorithm, like https://link.springer.com/chapter/10.1007/3-540-52590-4_50 does for ML.

I could imagine you being correct about the borrow checking typability problem being NP-complete. Or an even worse complexity class. Typability in ML is EXPTIME-complete, a larger set than NP-complete https://en.wikipedia.org/wiki/EXPTIME https://dl.acm.org/doi/10.1145/96709.96748 .

I also am not sure how to figure out if the complexity class of some kind of borrow checking has something to do with the exponential compile times of some practical Rust projects after they upgraded compiler version, for instance in https://github.com/rust-lang/rust/issues/75992 .

It would be good if there was a formal description of at least one borrow checking algorithm as well as the borrow checking "problem", and maybe also analysis of the complexity class of the problem.

Comment · 1 year ago

I don't see that debunking it. Instead, it says "usually". That means that it depends on the project.

There is definitely Rust code that takes exponential time to compile, borrow checker or not.

https://play.rust-lang.org/?version=stable&mode=release&edit...

https://github.com/rust-lang/rust/issues/75992

Some people used async in ways that surfaced these problems. Upgraded rustc, then the project took forever to compile.