Hacker News Reader

Comment by sischoel | Hacker News Reader

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

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.

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.

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

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.

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.

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

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.

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.

>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 ?

Not sure whether this proves turing completeness of the preprocessor or not(probably not) but Simon Tatham has a great(and somewhat disturbing) write-up[1] on creating arbitrary control structures using macros in C. He even goes as far as providing a library of helper macros for doing things like making gensyms, etc.

If nothing else, it does demonstrate that you can do a lot more in the preprocessor than you might think, and this is at least a significant subset of what true MP macros are used for in Lisp most of the time. Except much gnarlier...

[1] https://www.chiark.greenend.org.uk/~sgtatham/mp/

CPP needs to feed into itself (pipe stdout into stdin), if you want it to be turing-complete.

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.

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/HackGoo...

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

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.

There's some material on this under "superoptimizers", but I think if you want this then you should get an FPGA.

Reply on news.ycombinator.com