←back to thread

Why is the Rust compiler so slow?

(sharnoff.io)
302 points Bogdanp | 2 comments | 26 Jun 25 19:29 UTC | HN request time: 0s | source
Show context
WalterBright ◴[27 Jun 25 17:10 UTC] No.44398468[source]▶
I suspect that it is because the borrow checker needs to do data flow analysis. DFA is normally done in the optimizer, and we all know that optimized builds are quite a bit slower, and that is due to DFA.

DFA in the front end means slow.

replies(1): >>44398554 #
steveklabnik ◴[27 Jun 25 17:19 UTC] No.44398554[source]▶
As said many times in this thread already, the borrow checker is virtually never a significant amount of time spent while compiling.

Also, the article goes into great depth as to what is happening there, and the borrow checker never comes up.

replies(1): >>44399388 #
WalterBright ◴[27 Jun 25 19:07 UTC] No.44399388[source]▶
That makes me curious as to how Rust does the DFA. What I do is construct the data flow equations as bit vectors, which are then solved iteratively until a solution is converged on.

Doing this on the whole program eats a lot of memory.

replies(1): >>44399768 #
1. steveklabnik ◴[27 Jun 25 19:57 UTC] No.44399768{3}[source]▶
I'm not an expert on this part of the compiler, but what I can tell you is that Rust uses multiple forms of IR, and the IR that the borrow checker operates on (https://rustc-dev-guide.rust-lang.org/mir/index.html) already encodes control flow. So doing that construction, at least, is just a normal part of the compiler, and isn't part of the borrow checker itself.

However, in my understanding, it takes that IR, does build a borrow graph, computes liveliness, and then does inference. There's been a number of details in how this has changed over the years, but it's vaguely datalog shaped.

replies(1): >>44402041 #
2. WalterBright ◴[28 Jun 25 02:59 UTC] No.44402041[source]▶
Because there are cycles in the flow graph, I do not see how liveness can be computed in general without iteration and convergence on a solution.