Re:BareMetal is a 64-bit OS for x86-64 based computers
by haberman on Thursday May 26, 2011 @11:54AM
(#2588170)
> Is it an NP complete problem our own heuristics are currently better at estimating?
Some of the important problems are NP-complete (like register allocation). Another problem is that compilers aren't that good at telling fast-paths from slow-paths (and keeping everything in registers for the fast paths). For more info see this message from the author of LuaJIT: http://article.gmane.org/gmane.comp.lang.lua.general/75426
Re:BareMetal is a 64-bit OS for x86-64 based computers
by kragen on Thursday May 26, 2011 @03:58PM
(#2589188)
There's a new formulation of register allocation that's computationally tractable: http://compilers.cs.ucla.edu/fernando/projects/puzzles/exper...
Re:BareMetal is a 64-bit OS for x86-64 based computers
by BrandonM on Thursday May 26, 2011 @01:48PM
(#2588699)
Thanks for the link. That email was informative enough that I thought it deserved its own submission: http://news.ycombinator.com/item?id=2588696
Re:BareMetal is a 64-bit OS for x86-64 based computers
by Bootvis on Thursday May 26, 2011 @03:09PM
(#2589031)
I think the problem is that optimization is AI-complete. Without a lot of context about what your program is doing under what circumstances the problem is not solvable. You need to know when and how a specific code path is run.
Re:BareMetal is a 64-bit OS for x86-64 based computers
by eru on Thursday May 26, 2011 @09:40PM
(#2590133)
Yes, though that doesn't mean that humans will be better at it.
Re:BareMetal is a 64-bit OS for x86-64 based computers
by Bootvis on Friday May 27, 2011 @05:49PM
(#2593203)
Agreed, I guess that when we have build smarter compilers a Centaur approach would work best (like in chess). The computer can do a whole lot by bruteforce and smart algorithms and the human uses his knowledge of the context to steer it in the right direction.
Unfortunately we're not their yet.
No one has performed controlled studies on these things - maybe they had some crummy bottlenecks, used some language feature that their compiler couldn't optimize away, maybe the benchmarks they use to determine performance are trivial (which is very often the case), etc.
Not to mention that most of an operating system's time, post boot is spent doing... what? Having the scheduler swap processes in and out? If you're running a single program that fits inside ram... it's totally fucking pointless, there's nothing left to optimize.
I have a better question. These guys are clearly smart. What the hell are they still doing in Atwood, Ontario?