Comment by phillmv | Hacker News Reader

Comment by phillmv | Hacker News Reader

Parent Full thread

I don't know, I always found the notion that humans will always be able to optimize better than machines to be somewhat... naïve. Is it an NP complete problem our own heuristics are currently better at estimating?

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?

> 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

Thanks for the link. That email was informative enough that I thought it deserved its own submission: http://news.ycombinator.com/item?id=2588696

There's a new formulation of register allocation that's computationally tractable: http://compilers.cs.ucla.edu/fernando/projects/puzzles/exper...

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.

Yes, though that doesn't mean that humans will be better at it.

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.

Reply on news.ycombinator.com