Hacker News Reader

Comment by torstenvl | Hacker News Reader

It's slow because the borrow checker is NP complete. LLVM may or may not generate slower code than GCC would for rustc, but I doubt it's anywhere close to the primary cause of the lack of snappy.

View on HN

You're wrong it's been debunked that the borrow checker is any appreciable part of the compile time - Steve Klabnik actually verified it on here somewhere.

Edit: found it

https://news.ycombinator.com/item?id=44391240

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.

I say “usually” because of course sometimes bugs happen and of course you can conduct degenerate stress tests. But outside of those edge cases, it’s not an issue. If it were, blog posts that talk about lowering compile times would be discussing avoiding the borrow checker to get better times, but they never do. It’s always other things.

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.

The post my original comment is on discusses doing this at length.

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

I am not aware of any. But in all the posts on this topic over the years, codegen always ends up being half the time. It’s why cargo check is built the way it is, and why it’s always faster than a full build. If non-codegen factors were significant with any regularity, you’d be seeing reports of check being super slow compared to build.

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.

cargo check can be slow but what I mean is relative to a full build. Large projects are going to be slow to build by virtue of being large.

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.

Yes, there's a -Ztime-passes, but it's nightly only (or stable with the bootstrap env var set)

My understanding is that -Ztime-passes isn't very accurate anymore, as it's not integrated into the query system well, or something.

Thanks, I'm pretty sure I was thinking of this whole discussion when I made my original comment :)

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.

There isn't a formal definition of how the borrow checking algorithm works, but if anyone is interested, [0] is a fairly detailed if not mathematically rigorous description of how the current non-lexical lifetime algorithm works.

The upcoming Polonius borrow checking algorithm was prototyped using Datalog, which is a logical programming language. So the source code of the prototype [1] effectively is a formal definition. However, I don't think that the version which is in the compiler now exactly matches this early prototype.

EDIT: to be clear, there is a polonius implementation in the rust compiler, but you need to use '-Zpolonius=next' flag on a nightly rust compiler to access it.

[0]: https://rust-lang.github.io/rfcs/2094-nll.html

[1]: https://github.com/rust-lang/polonius/tree/master

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.

> IRC the plan isn't to use Polonius instead of NLL, but rather use NLL and kick off Polonius for certain failure cases.

Indeed. Based on the last comment on the tracking issue [0], it looks like they have not figured out whether they will be able to optimize Polonius enough before stabilization, or if they will try non-lexical lifetimes first.

[0]: https://github.com/rust-lang/rust-project-goals/issues/118

Reply on news.ycombinator.com