Personal computing discussed
Moderators: renee, Flying Fox, morphine
morphine wrote:He was joking, man.
Shining Arcanine wrote:Also, talking about optimization is a misnomer when discussing compilers, because having something be optimal means that it cannot become better and what a compiler does is implement heuristics that are known to make code better in general. Doing complete optimization is a NP-complete problem and unless P = NP, I can guarentee that you will die long before you can compile a program (e.g. Windows) and receive truly optimized output from the compiler.
bitvector wrote:Shining Arcanine wrote:Also, talking about optimization is a misnomer when discussing compilers, because having something be optimal means that it cannot become better and what a compiler does is implement heuristics that are known to make code better in general. Doing complete optimization is a NP-complete problem and unless P = NP, I can guarentee that you will die long before you can compile a program (e.g. Windows) and receive truly optimized output from the compiler.
No, "complete optimization" of arbitrary programs -- in the sense of "it cannot become better" -- is undecidable (Andrew Appel explains in his compiler textbook at the top of this page). It's jokingly referred to as the "full employment theorem for compiler writers".
Shining Arcanine wrote:Once you start talking about solving undecidable problems in general, you no longer are talking about things that are possible. In the case of compilers, doing true optimization by solving the halting problem in general means obtaining a level of performance that is beyond the best that can be achieved, which is not optimal by definition. If the question of whether or not you can have a better solution is undecidable, then you have the optimal solution.
bitvector wrote:There's a difference between mathematically undefined and undecidable.Shining Arcanine wrote:Once you start talking about solving undecidable problems in general, you no longer are talking about things that are possible. In the case of compilers, doing true optimization by solving the halting problem in general means obtaining a level of performance that is beyond the best that can be achieved, which is not optimal by definition. If the question of whether or not you can have a better solution is undecidable, then you have the optimal solution.
"Then you have the optimal solution"? That's just silly. You're trying to redefine terms to skate around the undecidable part (by saying that you've reached your definition of "optimal" once the question of "does a better solution exist?" becomes undecidable), but that doesn't work. The question of whether or not you can have a better solution is always undecidable, because you can't, in general, take two programs and determine if one has identical behavior to the other. But just because you can't algorithmically decide which one is better doesn't mean the concept is mathematically undefined.
Now you're playing redefinition games, but you were the one who defined "optimal" as "it cannot become better" and then said that "complete optimization is a NP-complete problem."
tfp wrote:or anything in the real world in general.
SA wrote:As for undecidability, if you wrote a program that solved the halting problem and asked it to evaluate a program that was designed to never terminate if the first program says yes and terminate if the first program says no, it would never terminate.
SA wrote:That is what would usually happen if you wrote an optimizing compiler that used a general solution to the halting problem.
SA wrote:Having an infinite loop is wrong, so you cannot do that.
SA wrote:If there is no method by which a decision on the existence of a better solution exists, then as far as any human being is concerned, there is no better solution.
Shining Arcanine wrote:That's great. And had you originally said that, I wouldn't have taken issue with that particular statement.Allocation of registers is modeled as graph coloring and graph coloring is NP-Complete. Therefore the calculation is NP-Complete.
bitvector wrote:But everything else you said in the quoted reply reads like gibberish. The words you used have meaning, but they don't make much sense when read in the order you supplied them.
tfp wrote:Your argument that compilers can't be continually optimized makes little sense. Intel for CPU and AMD/Nvidia for graphics come out with optimizations with every release of the compiler/driver. This happens with JVMs as well. Some of them are in the compiler itself while others are in libraries.
The idea that there is a max level of optimization are all well and good but that has nothing to do with how software releases work or anything in the real world in general. Improvements are incremental and things are "improved" over time. Sometimes it's just better code is implemented, other times it's improvements in tech that push the optimizations. Things like FPU, MMX, SSE (X), on board memory controlers (impacting pre-fetching added by the compiler), branch prediction improvements causes changes in the compiler. That's why there is a P4 flag on intels compilers vs shorter pipeline processors, HW designs have different compiler optimizations...
bitvector wrote:Shining Arcanine wrote:That's great. And had you originally said that, I wouldn't have taken issue with that particular statement.Allocation of registers is modeled as graph coloring and graph coloring is NP-Complete. Therefore the calculation is NP-Complete.
But everything else you said in the quoted reply reads like gibberish. The words you used have meaning, but they don't make much sense when read in the order you supplied them.
Shining Arcanine wrote:People's mental frameworks seem to be so different from mine that anything more than a sentence or two does not translate and is interpreted as gibberish. If you have any suggestions on how I can be more clear, I would be happy to hear about them. Please private message them to me to avoid polluting the thread.
Crayon Shin Chan wrote:This thread is still alive! for a while I thought the participants had given up...
Shining Arcanine wrote:Wikipedia calls it the P versus NP problem:
Your argument that compilers can't be continually optimized makes little sense. Intel for CPU and AMD/Nvidia for graphics come out with optimizations with every release of the compiler/driver. This happens with JVMs as well. Some of them are in the compiler itself while others are in libraries.
Meadows wrote:Shining Arcanine wrote:People's mental frameworks seem to be so different from mine that anything more than a sentence or two does not translate and is interpreted as gibberish. If you have any suggestions on how I can be more clear, I would be happy to hear about them. Please private message them to me to avoid polluting the thread.
Please read every single post Glorious ever made before commenting further, to avoid polluting the thread.
jihadjoe wrote:
bitvector wrote:Shining Arcanine wrote:Wikipedia calls it the P versus NP problem:
Oy. I'll put in my vote for the lock, morphine. It's clear he's going to continue to repeat the same misinformation (in an infinite loop which, if you believe the implication's of SA's blather, can be detected by brute forcing 3-SAT).
SA wrote:Run this on a GPU and >95% of the floating point calculations will disappear from the CPU. That is how it is meant to be played.
Shining Arcanine wrote:If you want to talk about misinformation, talk about the thread title. People keep posting with the assumptions that I wrote the thread title, that the thread has anything to do with its title and that the thread title encapsulates everything said in the thread in a manner that makes them experts on the actual thread contents.
TheEmrys wrote:Foul! You carried the anti-fpu flag throughout the first 4 pages of discussion on server-grade cpu's, and then play the "I didn't write the topic" card.
Shining Arcanine wrote:... to avoid polluting the thread.
Glorious wrote:Lock the thread from the mod panel, it's the only way to be sure.
Shining Arcanine wrote:Run this on a GPU and >95% of the floating point calculations will disappear from the CPU. That is how it is meant to be played.
I.S.T. wrote:Glorious wrote:Lock the thread from the mod panel, it's the only way to be sure.
**** that. Nuke from orbit. THAT is the only way to be sure.