TR Forums

He was joking, man.

morphine wrote:

He was joking, man.

While parts of my post applies to each of the two posts, I seem to be too tired, as I thought that both posts were the same when I was writing that out. :/

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

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

When the general case of a problem has the property of undecidability, the answer to a specific instance of that problem can be yes, no or null. In the third case, the answer is both at once, much like the value of sin(x) as x goes to infinity, which is not a single value, but the entire range from -1 to 1. Another example of this concept is the sum of the series ...-1, 1, -1, 1..., which is also undecidable because the value is -1, 0 and 1 at the same time.

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.

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

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

Allocation of registers is modeled as graph coloring and graph coloring is NP-Complete. Therefore the calculation is NP-Complete.

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. That is what would usually happen if you wrote an optimizing compiler that used a general solution to the halting problem. Having an infinite loop is wrong, so you cannot do that. 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.

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

tfp wrote:

or anything in the real world in general.

In any world. SA is great at spewing out terms and half-correct assumptions, but don't let that fool you into thinking he has a solid grasp of the theory. He doesn't. Not at all.

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.

That's not the halting problem, so the only thing you've demonstrated is you don't know what you're taking about.

What you are doing is this:

If A says B is true, then B is false
If A says B is false, B is true.

But how does B know what A says without breaking sequence? In the halting problem, program B is an arbitrary program that functions on a finite input being evaluated by program A on a turing machine. What you are saying is the output of A when evaluating B and its finite input is then also, retroactively, the input for B. Say what? What kind of turing machine can do that? Do you even know what one is?

This is like saying,given that time travel is real, you can be your own grandfather! Whee! Look at me! I've proven, errm, something, about your whole "family tree" model thingie!

What you're saying is not even wrong. Because you don't understand what you're saying. You seem to think this is some sort of solution, in reality, it's a malformed piece of the proof that there isn't a solution.

SA wrote:

That is what would usually happen if you wrote an optimizing compiler that used a general solution to the halting problem.

Dude, what kind of source code CHANGES ITSELF when it's being compiled? Is it self-aware? This is why you can't have a compiler that has a 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.

You can certainly make that decision, you just can't know with certainty that you made it correctly. Just because that's the best decision you can make doesn't mean that some other "human being" can't prove that decision wrong.

You were saying that a completely optimizing compiler was a computable problem. Uh, no, it isn't. Not even an impossibly hard one. It's undecidable. Try hard to optimize or not try at all, you'll never know with certainty if someone can make a better solution than you or not.

Shining Arcanine wrote:

Allocation of registers is modeled as graph coloring and graph coloring is NP-Complete. Therefore the calculation is NP-Complete.

That's great. And had you originally said that, I wouldn't have taken issue with that particular statement.

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.

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.

Best I can tell is that he's completely garbling one of the ways the proof for why the halting problem is undecidable is commonly presented. The proposition that the halting problem is solvable allows you to construct paradoxical situations. It appears that he has completely misunderstood this, as he seems to think you can know that the inherent paradox he presents will not terminate. But, of course, the whole point is that we can't know, because it's a fricking paradox. That's why the halting problem is undecidable: even if you treat it as "solved" you still can't actually decide anything! There are situations in which you can say "Yes" and you can say "No" with absolutely equal validity.

Like in the time travel analogy, rather loosely, if you fathered your own father, who's the dad?

SA has somehow interpreted this into infinite loops don't count (despite being one of the core building blocks of the basic proof), we can know it'll never terminate, and that if the halting problem is undecidable optimization by "humans" is impossible.


Oy vey.

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

Any new processor that differs from an existing processor in either its ISA or its performance characteristics in theory requires changes to how compilers generate code in order to generate optimal code, but no compiler exists that attempts to provide such a guarantee, which is why there has always been room for improvement. The phrase "compiler optimizations" is a misnomer, because the concept of optimization leaves no room for improvement:

http://en.wikipedia.org/wiki/Optimization_(mathematics)

The global performance maximum that can be obtained by compiling a program for a specific microprocessor is logically fixed when the processor is designed. Getting to it is an incredibly difficult problem, into which decades of research has been invested. Wikipedia calls it the P versus NP problem:

http://en.wikipedia.org/wiki/P_versus_NP_problem

The consequence is that anything more than a simple program cannot be compiled in your lifetime with the guarantee that it cannot be made better for a specific processor. If P versus NP was solved and the solution involved P = NP, then this issue could be overcome.

bitvector wrote:

Shining Arcanine wrote:

Allocation of registers is modeled as graph coloring and graph coloring is NP-Complete. Therefore the calculation is NP-Complete.

That's great. And had you originally said that, I wouldn't have taken issue with that particular statement.

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.

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.

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.

This thread is still alive! for a while I thought the participants had given up...

Crayon Shin Chan wrote:

This thread is still alive! for a while I thought the participants had given up...

Not for much longer. The lock is looming closer and closer.

Apparently you need a good FPU to run Crysis! =P


From: PhysX87: Software Deficiency by David Kanter

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

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.

Yeah, but he wrote most of a complier for a Computer Science class... surely that puts him on par with Intel.

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.

Pretty sure he's blocked Glorious for.... too much truth? I don't know.

Lock the thread from the mod panel, it's the only way to be sure.

jihadjoe wrote:

Apparently you need a good FPU to run Crysis! =P


From: PhysX87: Software Deficiency by David Kanter

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.

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

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.

As for repeating myself, the thread would be offtopic if I did not. This was originally part of a thread that talked about Bulldozer's floating point unit capabilities and anything beyond the existential question of the necessity of floating point units is off topic. If you want to talk about something else, make a new thread.

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.

/facepalm.

Actually, that article heavily suggests that since Nvidia sandbagged CPU physx by having it use a single thread with the x87 FPU, it's highly probable that there isn't any real point to GPU physx at all.

Let alone that people might want to play the game online, for which we'd need servers.

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.

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.

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.

Not to mention that I warned him, right after his first post in this thread, that if he didn't stop with the nonsense we'd jump all over him.

As everyone can see, it went unheeded. Too bad.

Shining Arcanine wrote:

... to avoid polluting the thread.

I haven't laughed that hard in months! Thanks SA!

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.

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.

The idea that you can completely replace all CPU based floating point code on a GPU is quite frankly ridiculous. GPUs are giant Floating Point parallel processors, each small core designed to do a simple task and do it as quickly as possible. So for highly parallel operations that are each simple, GPUs are great. For more complex tasks that are not easily paralleled, especially if it's really branchy code etc. then these GPUs are not optimal for the job. These situations CPUs are much more desirable as they are built to cope with branchy code (well except for Netburst) and other situations that doesn't fit with the model of a GPU. There could also be situations where the overhead of having to marshal instructions over to a separate co-processor, (which is what a GPU is) would defeat the object, especially if there's only a few operations to be performed. The only way around this would be to have the GPU's instruction set built into that of the CPU, kinda like a Super AVX.

Emulating FP instructions using integers in a high speed environment is also a non-starter, no matter how fast you make the algorithm, it will never be anywhere near as fast as designing it in hardware.

That's my 2 cents

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.

True, a simple lock would still leave all this nonsense publicly available. At least we can point to it in future SA threads and... well, no, it's not like it would do any good then either. Nuke from orbit and build an new TR forum server. Would it be improper to vote for the ba..aaa..aaaah..ahh well never mind.

Due to apparently popular request and since the fun is over, I'm locking this