News for hackers. Stuff that matters.

A comment on Compiling Rust is NP-hard. Parent comment

Re:Compiling Rust is NP-hard by chrisseaton on Thursday July 08, 2021 @06:31AM (#27770236)
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

[ Parent | on HN ]
Re:Compiling Rust is NP-hard by imtringued on Thursday July 08, 2021 @11:53AM (#27773647)
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.
[ Parent | on HN ]