[chrisseaton]

No - you can express register allocation as an NP-hard problem if you want to, but you don’t have to and not all compilers do it like that. You don’t need an optimal register allocation - you get into diminishing returns very quickly.

[sischoel]

Yes, I hadn't thought about that before, but of course the difference here is that the Rust compiler cannot just produce a "good enough" result for pattern matching.

[chrisseaton]

Register allocation is a great example of over-theorisation. People found that register allocation can be expressed as graph colouring, so they doubled-down and worked really hard to solve that pure problem, but then it turned out you can just do a very simple linear allocation heuristic and the generated code is basically as fast as solving the NP-hard problem.

https://dl.acm.org/doi/abs/10.1145/330249.330250

[imtringued]

Well, the problem for the NP-hard algorithm is that the base line is already very efficient. It's like branch prediction. Even the dumbest predictors can be 90% efficient. The perfect solution doesn't have much room to be better. I'd say there are more microsecond level optimization problems left than on the nanosecond or millisecond level.

[kadoban]

Well, it probably _could_ do "good enough". If a set of matches gets too large/hairy it could just output a "here be dragons" warning and go ahead with compiling it, no?

That may not count as a correct Rust compiler though, I'm not 100% sure how that's defined, or if it is.