4 ms·

While this is an interesting result, isn't basically every compiler NP-hard, because of register allocation?

by sischoel 5y ago

srl 5y ago
Compilers don't guarantee (or try to find) the absolute optimal allocation, right?
- WJW 5y ago
  This depends on the compiler of course. Most will not because it is not worth it, but I expect that there is at least one compiler out there with the option to exhaustively search the allocation space for that very last nanosecond of runtime optimization. Probably inside an HFT firm somewhere.
  - astrange 5y ago
    There's some material on this under "superoptimizers", but I think if you want this then you should get an FPGA.
chrisseaton 5y ago
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 5y ago
  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.
  - kadoban 5y ago
    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.
  - chrisseaton 5y ago
    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 https://dl.acm.org/doi/abs/10.1145/330249.330250
    - imtringued 5y ago
      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.
antientropic 5y ago
Or worse than NP-hard: C++ template instantiation and the C preprocessor are Turing complete. (Except that I believe C++ requires some fixed limit on the maximum instantiation depth, but even so it's still exponential complexity.)
- rocqua 5y ago
  I believe you can encode paradoxes in C++ templating. Something about two specializations which are mutually impossible because they reference eachother. So you can say: A is of type T <=> B is not of type T B is of type T <=> A is not of type T Where <=> is if and only if. In which case it is paradoxical to say that A is of type T. But also paradoxical to say that A is not of type T.
  - MauranKilom 5y ago
    Note that "a template for which no valid instantiation is possible" is actually ill-formed, no diagnostic required. That said, it's not clear to me what part of "you can write uninstantiable templates" is surprising, so I'm probably not understanding correctly. Maybe you could find the C++ code you're talking about? I would be interested.
- Banana699 5y ago
  >the C preprocessor are Turing complete That's surprising, the C preprocessor is pretty crippled. It's creator intentionally made it so people won't abuse it to create full blown mini languages. Did you get things mixed up or is there actually a way the c preprocessor can be turing-complete ?
  - namibj 5y ago
    CPP needs to feed into itself (pipe stdout into stdin), if you want it to be turing-complete.
    - gpderetta 5y ago
      I believe that while you can't encode an infinite tape, you can very easily define an arbitrarily large tape, so, while not technically Turing complete, it is close enough.
adrianN 5y ago
If you do a SSA transform of your program the register graphs are chordal. It turns you that coloring chordal graphs is easy: http://web.cs.ucla.edu/~palsberg/course/cs232/papers/HackGoos-ipl06.pdf http://web.cs.ucla.edu/~palsberg/course/cs232/papers/HackGoo...

While this is an interesting result, isn't basically every compiler NP-hard, because of register allocation?

srl 5y ago

Compilers don't guarantee (or try to find) the absolute optimal allocation, right?

WJW 5y ago
This depends on the compiler of course. Most will not because it is not worth it, but I expect that there is at least one compiler out there with the option to exhaustively search the allocation space for that very last nanosecond of runtime optimization. Probably inside an HFT firm somewhere.
- astrange 5y ago
  There's some material on this under "superoptimizers", but I think if you want this then you should get an FPGA.

chrisseaton 5y ago

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 5y ago
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.
- kadoban 5y ago
  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.
- chrisseaton 5y ago
  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 https://dl.acm.org/doi/abs/10.1145/330249.330250
  - imtringued 5y ago
    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.

antientropic 5y ago

Or worse than NP-hard: C++ template instantiation and the C preprocessor are Turing complete. (Except that I believe C++ requires some fixed limit on the maximum instantiation depth, but even so it's still exponential complexity.)

rocqua 5y ago
I believe you can encode paradoxes in C++ templating. Something about two specializations which are mutually impossible because they reference eachother. So you can say: A is of type T <=> B is not of type T B is of type T <=> A is not of type T Where <=> is if and only if. In which case it is paradoxical to say that A is of type T. But also paradoxical to say that A is not of type T.
- MauranKilom 5y ago
  Note that "a template for which no valid instantiation is possible" is actually ill-formed, no diagnostic required. That said, it's not clear to me what part of "you can write uninstantiable templates" is surprising, so I'm probably not understanding correctly. Maybe you could find the C++ code you're talking about? I would be interested.
Banana699 5y ago
>the C preprocessor are Turing complete That's surprising, the C preprocessor is pretty crippled. It's creator intentionally made it so people won't abuse it to create full blown mini languages. Did you get things mixed up or is there actually a way the c preprocessor can be turing-complete ?
- namibj 5y ago
  CPP needs to feed into itself (pipe stdout into stdin), if you want it to be turing-complete.
  - gpderetta 5y ago
    I believe that while you can't encode an infinite tape, you can very easily define an arbitrarily large tape, so, while not technically Turing complete, it is close enough.

adrianN 5y ago

If you do a SSA transform of your program the register graphs are chordal. It turns you that coloring chordal graphs is easy: http://web.cs.ucla.edu/~palsberg/course/cs232/papers/HackGoos-ipl06.pdf http://web.cs.ucla.edu/~palsberg/course/cs232/papers/HackGoo...