Polonius, borrow checking performance & progressive intelligence

Basically the inspiration for this topic is tiered JIT where you only expand effort when you need it rather than every where.

One of the slow downs for stabilizing Polonius from what I’ve read & listened to seems to be about making it work with minimal performance impact. I was wondering if there’s been any thought about progressive layers of borrow checkers where simple and fast algorithms can validate the more common simple cases but failing to validate with them triggers a check with the next tier about whether the code is still valid Rust. The most complicated code would compile more slowly but the much more common simple code would validate trivially. Of course, this is predicated on the assumption that the simpler borrow checker could produce an equivalent state update of the lifetime graph, but I think that’s likely true and not where the complexity lies.

The plan is exactly to run location-insensitive Polonius first as it is faster and only run location-sensitive Polonius when location-insensitive Polonius reports an error.

2 Likes

A related idea: Start code generation as soon as type checking is completed, defer borrow checking to another job. Make borrow checking jobs low priority, so that they will be executed when there is free core (for example in linking). So borrow checking will become almost free in a machine with many cores.

5 Likes

That doesn't help the very common cargo check case, though. Which I'd argue is more important.

Hmm, while I don't think that with the current pipelining this would be a good idea -- after all, codegen already doesn't block downstream crates -- it makes me wonder a different approach to pipelining that's willing to emit an rlib without having completed some of the checks yet.

If we have any checking passes that strictly do not modify things, maybe we could run that after emitting enough to let pipelined compilation continue. For example, we could check that all the item consts can be evaluated only after emitting the rlib -- it'd still fail compilation eventually if CTFE for them fails, but in the common case of dependencies that are going to pass anyway it could let pipelining kick off the next phase just that little bit sooner.

(Maybe even some coherence checks could be delayed like that? Obviously type inference can't be, though, since that's not a check that's a critical part of things like resolution.)

3 Likes

That's what we have in the -Zpolonius datalog implementation today: it only does a full analysis if the location-insensitive analysis says there are "possible errors".

I feel you described the spirit of it, but I'll slightly expand it for clarity and details, as we want a bit more with the -Zpolonius=next implementation: we want each level of detail to not only increase precision, but to also prune the tree for the next levels, so that the higher precision applies only on less data. (You can think of it as different "grades" or quality levels, and so I call this "graded borrow-checking")

I had prototypes of this in the datalog implementation, that's why we're hopeful about it -- and are currently discussing how to realize it in-tree. We know it is better, but don't yet know if it is enough :).

2 Likes