Hacker News new | ask | show | jobs
by loicd 1146 days ago
> Compilers already solve multiple NP-complete problems in the course of compilation after all, for example register allocation.

The NP-complete problem is optimal register allocation (through graph coloring). Register allocation in itself is not NP-complete. You can always use a suboptimal but fast algorithm because optimizations are optional. On the other hand, type checking is not optional, so having to solve a NP-complete problem for that would indeed be problematic.
2 comments
tzs 1146 days ago
> On the other hand, type checking is not optional, so having to solve a NP-complete problem for that would indeed be problematic.

Not necessarily. There are plenty of NP-complete problems that can be solved optimally fast enough to be useful for the instances that actually come up in real world applications.

For example the Traveling Salesman Problem (TSP) is NP-complete, but there are exact solvers that run in reasonable time for instances of a few hundred vertices. That's fine if you are say a delivery company trying to plan the day's itinerary for one of your delivery trucks.

link
samus 1146 days ago
A less precise borrow checker can usually still be satisfied by adding workarounds, at the cost of performance of course. Adding redundant reference counting or increasing the lifetime of data and the duration of critical regions make the program slower. In this sense, improving the borrow checker is analogous to adding new analyses and optimizations passes to a compiler.
link
loicd 1146 days ago
OK, I suppose I have to dig deeper into Rust to determine whether I really disagree with that, or maybe this is too vague. The question is: who applies your workarounds? If this is always the compiler, then I agree, but if the programmer has to do any work, then your analogy fails.
link
samus 1146 days ago
Yes, the programmer has to apply the safe workarounds. They always work, but improvements to the borrow checker's heuristics can make them redundant. Removing these workarounds increases performance. A certain minimum set of heuristics are part of the documented language spec by now, and this set is going to become larger with time. If a significant fraction of the ecosystem is affected by a split in heuristics coverage, then Gccrs will have to catch up.

In the PR dug out by a sibling commenter, the improvement to the compiler was indeed to apply the workaround that the programmer had to do. I believe that the churn of new heuristics is going to become smaller, as presumably most of the low-hanging fruits have been harvested by now.

link