4 ms·

NP-completeness is not a problem at all. Compilers already solve multiple NP-complete problems in the course of compilation after all, for example register allo

by samus 4y ago

NP-completeness is not a problem at all. Compilers already solve multiple NP-complete problems in the course of compilation after all, for example register allocation. They require heuristics to be solved in a reasonable time, but the upside is that there is no gold standard since there are pathological cases for any heuristic. Presumably, a representative set of crates from the ecosystem will be chosen to find performance issues. The underspecified part should not be a deal breaker, even though it's certainly a difficulty. But it will also be an opportunity to spot suboptimal implementation choices in rustc. Exposing these will improve the language as a whole.

loicd 4y 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.
- samus 4y 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.
  - loicd 4y 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.
    - samus 4y 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.
- tzs 4y 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.
j16sdiz 4y ago
> The underspecified part should not be a deal breaker, even though it's certainly a difficulty. But it will also be an opportunity to spot suboptimal implementation choices in rustc. Exposing these will improve the language as a whole. but... we don't want same sourcecode compile with one compiler implementation, but not the other... right? When I say "under-specified", I meant something like this: https://github.com/rust-lang/rust/pull/105300/ https://github.com/rust-lang/rust/pull/105300/ quote> I claim it's more correct as well because it fixes #104639. There is no spec. Just a bunch of implementation-defined behavior. Without a spec, this would be a forever catching up game. It is not easy to come up with a spec -- the implement is filled with heuristics because the intrinsic NP-completeness.
- deleted 4y ago
  [deleted]
- tialaramex 4y ago
  > we don't want same sourcecode compile with one compiler implementation, but not the other... right? It's not ideal, but I can live with it so long as when I write a program which compiles it has the desired behaviour. That's the problem in C++ and to a lesser extent C which ultimately falls out of this same constraint. In C++ it's easy to write programs which compiler A and compiler B will both compile but they have different results and neither of them is wrong. I have no use for this whatsoever. If some Rust compilers say my program is unacceptable, and others build it correctly, obviously that's not brilliant news but I can choose whether to fix the program to be acceptable to more compilers, or not worry - the results at least are correct.
- samus 4y ago
  Specifying the heuristics would actually impede future implementations. Even if they would be willing to engage in spending more computational effort on proving that a controversial block of code is type-safe. And it's always possible that a smart PhD student comes up with a better heuristics for certain kinds of programs. Implementations accepting different sets of inputs is certainly annoying, but acceptable as long as they are erring on the side of caution. We definitely don't want code to compile which is actually not type-safe. At a quick glance, the PR can be understood as automating a workaround that programmers had to do by themselves before. > This PR (similarly, and building on top of #104765) allows RPITs and async fns to untangle their lifetime bounds to figure out the set of lifetimes that actually get caputed instead of falling back to a larger one or even 'static. For most cases it was was already possible for users to manually reorder their lifetimes to make their code compile, this PR just makes that automatic, as the order of generic params and bounds should not matter.

by samus 4y ago

loicd 4y 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.

samus 4y 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.
- loicd 4y 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.
  - samus 4y 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.
tzs 4y 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.

j16sdiz 4y ago

> The underspecified part should not be a deal breaker, even though it's certainly a difficulty. But it will also be an opportunity to spot suboptimal implementation choices in rustc. Exposing these will improve the language as a whole. but... we don't want same sourcecode compile with one compiler implementation, but not the other... right? When I say "under-specified", I meant something like this: https://github.com/rust-lang/rust/pull/105300/ https://github.com/rust-lang/rust/pull/105300/ quote> I claim it's more correct as well because it fixes #104639. There is no spec. Just a bunch of implementation-defined behavior. Without a spec, this would be a forever catching up game. It is not easy to come up with a spec -- the implement is filled with heuristics because the intrinsic NP-completeness.

deleted 4y ago
[deleted]
tialaramex 4y ago
> we don't want same sourcecode compile with one compiler implementation, but not the other... right? It's not ideal, but I can live with it so long as when I write a program which compiles it has the desired behaviour. That's the problem in C++ and to a lesser extent C which ultimately falls out of this same constraint. In C++ it's easy to write programs which compiler A and compiler B will both compile but they have different results and neither of them is wrong. I have no use for this whatsoever. If some Rust compilers say my program is unacceptable, and others build it correctly, obviously that's not brilliant news but I can choose whether to fix the program to be acceptable to more compilers, or not worry - the results at least are correct.
samus 4y ago
Specifying the heuristics would actually impede future implementations. Even if they would be willing to engage in spending more computational effort on proving that a controversial block of code is type-safe. And it's always possible that a smart PhD student comes up with a better heuristics for certain kinds of programs. Implementations accepting different sets of inputs is certainly annoying, but acceptable as long as they are erring on the side of caution. We definitely don't want code to compile which is actually not type-safe. At a quick glance, the PR can be understood as automating a workaround that programmers had to do by themselves before. > This PR (similarly, and building on top of #104765) allows RPITs and async fns to untangle their lifetime bounds to figure out the set of lifetimes that actually get caputed instead of falling back to a larger one or even 'static. For most cases it was was already possible for users to manually reorder their lifetimes to make their code compile, this PR just makes that automatic, as the order of generic params and bounds should not matter.