[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.