Comment by WalterBright
6 months ago
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.
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.
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.
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.
1 reply →