Optimizing away an endless loop

  • Thread starter Johannes Schaub (litb)
  • Start date
J

Johannes Schaub (litb)

Hello all, i need some advice. Is it actually true that a C++0x
implementation can print "Hello" for the following snippet?

#include <iostream>

int main() {
while(1)
/* do nothing */;

std::cout << "Hello" << std::endl;
}

C++0x seems to allow an implementation to assume that the above infinite
loop terminates, which to me seems to mean that it can entirely ignore that
this loop never wants to stop.

Why is this the way it is? Doesn't it harm a lot of programs?
 
J

Johannes Schaub (litb)

Johannes said:
Hello all, i need some advice. Is it actually true that a C++0x
implementation can print "Hello" for the following snippet?

#include <iostream>

int main() {
while(1)
/* do nothing */;

std::cout << "Hello" << std::endl;
}

C++0x seems to allow an implementation to assume that the above infinite
loop terminates, which to me seems to mean that it can entirely ignore
that this loop never wants to stop.

Why is this the way it is? Doesn't it harm a lot of programs?

Actually, the behavior of the above program turns out to be undefined,
according to the C++0x draft as explained by
http://blog.regehr.org/archives/161 :

`Unfortunately, the words "undefined behavior" are not used. However,
anytime the standard says "the compiler may assume P," it is implied that a
program which has the property not-P has undefined semantics.`

I asked the same question on Stackoverflow, and they came to the conclusion
that this allows better optimizations for the compiler.
 
J

Joshua Maurice

Actually, the behavior of the above program turns out to be undefined,
according to the C++0x draft as explained byhttp://blog.regehr.org/archives/161:

`Unfortunately, the words "undefined behavior" are not used.  However,
anytime the standard says "the compiler may assume P," it is implied that a
program which has the property not-P has undefined semantics.`

I asked the same question on Stackoverflow, and they came to the conclusion
that this allows better optimizations for the compiler.

As I understand this rule, it should read: "infinite loops without
volatile reads and writes, and without io library calls, and without
any other 'side effects', cause the program to have undefined
behavior."

Could you link to that thread on Stackoverflow? I am most curious what
sort of optimizations benefit from the rule. At first glance, this
just seems horribly retarded.
 
J

Johannes Schaub (litb)

Joshua said:
As I understand this rule, it should read: "infinite loops without
volatile reads and writes, and without io library calls, and without
any other 'side effects', cause the program to have undefined
behavior."

Could you link to that thread on Stackoverflow? I am most curious what
sort of optimizations benefit from the rule. At first glance, this
just seems horribly retarded.

It's over here: http://stackoverflow.com/questions/3592557/optimizing-away-
a-while1-in-c0x
 
J

Joshua Maurice


The only legitimate optimization I took away from that link is auto-
parallelization of a single thread. From my limited understanding,
this is not common. I would expect that the overhead of mutexes and
condition variables would cause the compiler to pessimize code as
often as it optimizes code through auto-parallelization of a single
thread. Am I correct?

Presumably there are other good optimizations which are allowed,
right? What are they? Can you give a very specific example? It has
been claimed that several major compiles "do this" already. What
exactly do they do?
 
K

Kenneth 'Bessarion' Boyd

Hello all, i need some advice. Is it actually true that a C++0x
implementation can print "Hello" for the following snippet?

#include <iostream>

int main() {
  while(1)
    /* do nothing */;

  std::cout << "Hello" << std::endl;

}

C++0x seems to allow an implementation to assume that the above infinite
loop terminates, which to me seems to mean that it can entirely ignore that
this loop never wants to stop.

Yes, it's one of the few documented optimizations that are explicitly
allowed to violate observable behavior. I don't have a copy of C++03
on hand to verify, but this optimization wasn't explicitly allowed in C
++98. (Copy construction/assignment is another such observable
behavior violating optimization, but that dates back to at least C+
+98.)
Why is this the way it is? Doesn't it harm a lot of programs?

It's moderately bad for automated proofs, and causes a risk of
problems for embedded systems with low-quality compilers (they have to
guess whether an infinite loop is intentional, and keep the
intentional infinite loops.) These explicitly allowed wrong code
executables do suppress bugs in normal programs targeting a hosted
environment, so I suppose they're useful that way.

The comp.std.c thread analyzes the problems pretty well, but has
little motivation to name use cases where these wrong-code executables
are actually useful.

Note that it's formally valid [without regard to the standards, from
first principles] to optimize source code *dominated* by a loop as if
the loop always terminates. This was already allowed by the as-if
rule, thus irrelevant to why the standard is being changed.

The allowed change in the vernacularly observable behavior of whether
the program terminates, is caused by actually deleting the loop. [I'm
fuzzy as to whether the return code from main actually counts as
observable behavior.]
 
J

James Kanze

As I understand this rule, it should read: "infinite loops
without volatile reads and writes, and without io library
calls, and without any other 'side effects', cause the program
to have undefined behavior."
Could you link to that thread on Stackoverflow? I am most
curious what sort of optimizations benefit from the rule. At
first glance, this just seems horribly retarded.

The most obvious case is something like:

while (complicatedExpression)
;
doSomething();

If the compiler can prove that complicatedExpression doesn't
have any side effects, it can drop the loop (with the current
conditions). Without the undefined behavior for loops that
never terminate, it can only drop the loop if it can prove that
the loop terminates---a much more difficult requirement.

Whether this is an important optimization, one worth introducing
undefined behavior for, is another question. I'm on the side of
making it defined.
 
A

Alf P. Steinbach /Usenet

* James Kanze, on 29.08.2010 21:30:
The most obvious case is something like:

while (complicatedExpression)
;
doSomething();

If the compiler can prove that complicatedExpression doesn't
have any side effects, it can drop the loop (with the current
conditions). Without the undefined behavior for loops that
never terminate, it can only drop the loop if it can prove that
the loop terminates---a much more difficult requirement.

It's not an optimization.

It's a direct introduction, by the compiler, of a second bug /hiding/ the
original bug.

By allowing this rewriting rule in the standard one has introduced sufficiently
vague idiot's semantics so that the transformation can be formally regarded as
preserving semantics and thus, that it can formally be regarded as an
optimization, but it's still pure idiot's wordplay. Someone needs a real hard
kick in the ass. Or on the other side of the body at about the same elevation.

Whether this is an important optimization, one worth introducing
undefined behavior for, is another question. I'm on the side of
making it defined.

I agree, and more (see above). <g>


Cheers,

- Alf
 
J

Joshua Maurice

The most obvious case is something like:

   while (complicatedExpression)
       ;
   doSomething();

If the compiler can prove that complicatedExpression doesn't
have any side effects, it can drop the loop (with the current
conditions).  Without the undefined behavior for loops that
never terminate, it can only drop the loop if it can prove that
the loop terminates---a much more difficult requirement.

Whether this is an important optimization, one worth introducing
undefined behavior for, is another question.  I'm on the side of
making it defined.

Agreed entirely.

Sure it's a hard problem, but I can't imagine it's that common. Surely
the compiler could be configured to issue a warning, and that would be
a far better outcome than silently breaking some well established
existing code, and being quite counter-intuitive.
 
A

Alf P. Steinbach /Usenet

* Joshua Maurice, on 30.08.2010 02:47:
Agreed entirely.

Sure it's a hard problem, but I can't imagine it's that common.

Note that no-one has presented an example of actual optimization.

That's because it's impossible to present such an example, because the purported
"optimization" is *not* an optimization, it's just an idiocy.

For James' purported example above, if the compiler can prove that the condition
expression has no side effects and depends on nothing external, then it's proved
that the expression is constant, and what the value is, and so it's already
proved whether the loop terminates or not. So there's no need for undefined for
loops that nver termiante, in this purported (but not actual) examples.

There's nothing "hard" about it, at all: its *trivial*.

It's just some academics' intellectual masturbation. Presumably they're doing it
just for the lulz (making fools of the C++ standardization committee). And I
really hope someone gives them some corporeal punishment, or spit on 'em.

Surely
the compiler could be configured to issue a warning, and that would be
a far better outcome than silently breaking some well established
existing code, and being quite counter-intuitive.

Even better, not waste time on the analyzis.

Infinite loops will show up in testing.

But then, current C++ compilers are some orders of *magnitude* slower than
necessary, so it doesn't really matter...


Cheers & hth.,

- Alf
 
J

Joshua Maurice

* Joshua Maurice, on 30.08.2010 02:47:






Note that no-one has presented an example of actual optimization.

That's because it's impossible to present such an example, because the purported
"optimization" is *not* an optimization, it's just an idiocy.

For James' purported example above, if the compiler can prove that the condition
expression has no side effects and depends on nothing external, then it's proved
that the expression is constant, and what the value is, and so it's already
proved whether the loop terminates or not. So there's no need for undefined for
loops that nver termiante, in this purported (but not actual) examples.

There's nothing "hard" about it, at all: its *trivial*.

I wouldn't say that...

Let's take a simple pseudocode example:
for all 4-tuples (A, B, C, N) over (positive Natural Numbers)^4,
with N > 2
if (pow(A, N) == pow(B, N) + pow(C, N))
break;
print "hello world!"

Here, we're basically exhaustively testing whether Fermat's Last
Theorem is true by testing all possible couterexamples, one at a
time.

The loop can be shown to be free of "side effects", including volatile
reads and writes, io lib calls, synchronization, etc. If the loop does
terminate, then the entire loop should be optimized away. If the loop
does not terminate, then an infinite loop of some variety should
remain.

As a compiler, there's basically no way for it to determine whether
the loop terminates or not. It may terminate. It may not. (We have the
benefit of knowing that it does, but only because of some particularly
new and advanced math.)

I see some benefit in allowing a compiler to auto-parallelize the
print "hello world!" with the earlier calculation if the calculation
can be shown to terminate and does not affect the print (such as this
example). I even see some benefit requiring all loops to terminate to
facilitate this "optimization".

However, my gut reaction is that the penalties far outweigh the
benefits. This breaks past sane conforming code, this is particularly
counter-intuitive, and I have yet to see any real world examples which
would actually benefit from this.

Moreover, even if there was such a real world example, a compiler
issuing a warning that it found an infinite loop would be far
preferable to it silently removing the loop entirely.
 
J

Joshua Maurice

As a compiler, there's basically no way for it to determine whether
the loop terminates or not. It may terminate. It may not. (We have the
benefit of knowing that it does, but only because of some particularly
new and advanced math.)

.... I really need to review posts before posting... That should read
"We have the benefit of knowing that the loop does \not\ terminate".
 
A

Alf P. Steinbach /Usenet

* Joshua Maurice, on 30.08.2010 08:53:
I wouldn't say that...

Well, it *is* trivial.

Completely and utterly trivial.

Any complexity is just intellectual masturbation, which you can safely dismiss.

Let's take a simple pseudocode example:
for all 4-tuples (A, B, C, N) over (positive Natural Numbers)^4,
with N> 2
if (pow(A, N) == pow(B, N) + pow(C, N))
break;
print "hello world!"

Here, we're basically exhaustively testing whether Fermat's Last
Theorem is true by testing all possible couterexamples, one at a
time.

Yes, I've seen that example (it was referred to earlier in the thread).

It's a good example.

Because as a case for "optimization" it's pure idiocy.

The loop can be shown to be free of "side effects", including volatile
reads and writes, io lib calls, synchronization, etc. If the loop does
terminate, then the entire loop should be optimized away. If the loop
does not terminate, then an infinite loop of some variety should
remain.

Of course the loop "should" not be optimized away.

That produces an /incorrect result/.

Who tricked you into believing that producing an incorrect result is optimization?

As a compiler, there's basically no way for it to determine whether
the loop terminates or not. It may terminate. It may not. (We have the
benefit of knowing that it does, but only because of some particularly
new and advanced math.)

I see some benefit in allowing a compiler to auto-parallelize the
print "hello world!" with the earlier calculation if the calculation
can be shown to terminate and does not affect the print (such as this
example). I even see some benefit requiring all loops to terminate to
facilitate this "optimization".

You need flogging, definitely, when you think it's *beneficial* to screw up the
programmer's intent so as to produce an /incorrect result/ for correct code.

Producing an incorrect result for correct code is not optimization, except
pedantically-formally with the aforementioned masturbation in the picture
(redefining the semantics as sufficiently wooly to be able to call it
optimization in a very formal but meaningless sense).

Just repeating, in case it's not sunk in yet: it's *not* optimization.

However, my gut reaction is that the penalties far outweigh the
benefits.

Oh, I was perhaps too hasty, perhaps some milder punishment. ;-)

This breaks past sane conforming code, this is particularly
counter-intuitive, and I have yet to see any real world examples which
would actually benefit from this.

Moreover, even if there was such a real world example, a compiler
issuing a warning that it found an infinite loop would be far
preferable to it silently removing the loop entirely.

Yes.

And one saving time by not even attempting the analyzis, better still...


Cheers & hth.,

- Alf
 
A

Alf P. Steinbach /Usenet

* Joshua Maurice, on 30.08.2010 08:55:
... I really need to review posts before posting... That should read
"We have the benefit of knowing that the loop does \not\ terminate".

Perhaps. Note that Wilkes' proof dependended on a conjecture. Most see that as
merely a shortcut that in principle could be replaced with good hard math, but
essentially, while thoroughly impressive work, he did nothing more than reduce
the problem to that smaller conjecture, a /single/ protuberance out of ballon.


Cheers & hth.,

- Alf
 
J

Joshua Maurice

* Joshua Maurice, on 30.08.2010 08:53:


Yes, I've seen that example (it was referred to earlier in the thread).

It's a good example.

Because as a case for "optimization" it's pure idiocy.


Of course the loop "should" not be optimized away.

That produces an /incorrect result/.

Who tricked you into believing that producing an incorrect result is optimization?

Hmmm? Let's be clear here. If the loop has no side effects, and it
will eventually terminate, then it is an optimization under the as-if
rule to remove it. That's all I've claimed thus far into the post.
You need flogging, definitely, when you think it's *beneficial* to screw up the
programmer's intent so as to produce an /incorrect result/ for correct code.

Producing an incorrect result for correct code is not optimization, except
pedantically-formally with the aforementioned masturbation in the picture
(redefining the semantics as sufficiently wooly to be able to call it
optimization in a very formal but meaningless sense).

Just repeating, in case it's not sunk in yet: it's *not* optimization.

I don't want to get into a pedantic argument over definition.

Suffice to say, I see this as analogous to the copy constructor
elision rules which I tend to like.

Arguably, the copy constructor elision rules "screw up the
programmer's intent [...] to produce an /incorrect result/ for correct
code". I also think that this particular thing in this particular case
is a good thing.

However, unlike the copy constructor elision rules, 1- there is code
already out there which would break under this new infinite loops
rule, 2- I think that the copy constructor elision rules are a lot
more intuitive than this new infinite loops rule, and 3- I think that
the copy constructor elision rules actually have a tangible benefit as
opposed to this new infinite loops rule.

That is, I err on the side of caution when introducing allowances such
as the copy constructor elision rule. I have seen compelling arguments
for the copy constructor elision rule, but I have yet to see anything
near that level of rigor for this new infinite loops rule.
 
K

Kai-Uwe Bux

[Discussion triggered by:]
Here, we're basically exhaustively testing whether Fermat's Last
Theorem is true by testing all possible couterexamples, one at a
time.
* Joshua Maurice, on 30.08.2010 08:55:

Perhaps. Note that Wilkes' proof dependended on a conjecture. Most see
that as merely a shortcut that in principle could be replaced with good
hard math, but essentially, while thoroughly impressive work, he did
nothing more than reduce the problem to that smaller conjecture,

I am not sure what you are talking about here; but the reduction of Fermat's
problem to the Shimura-Taniyama-Weil conjecture was known before (by work of
Serre and Ribet following a suggestion of Frey). What Wiles and Taylor did,
was to prove the particular _part_ of the Shimura-Taniyama-Weil conjecture
needed in the reduction. Taken together, there is a complete proof of
Fermat's statement although the full statement of the Shimura-Taniyama-Weil
conjecture remained open at the time. However in 2001, the full Shimura-
Taniyama-Weil conjecture has been turned into a theorem by Breuil, Conrad,
Diamond, and Taylor.
a /single/ protuberance out of ballon.

???


Best

Kai-Uwe Bux
 
A

Alf P. Steinbach /Usenet

* Joshua Maurice, on 30.08.2010 09:23:
Hmmm? Let's be clear here. If the loop has no side effects, and it
will eventually terminate, then it is an optimization under the as-if
rule to remove it. That's all I've claimed thus far into the post.

No, you claimed that "if the loop does terminate, then the entire loop should be
optimized away".

"should" is very different from "can".

It implies that the compiler should determine whether the loop terminates, and
further, if that proves to be impossible in general (as it is), that the
semantics need to be woolified sufficiently so that the loop can be optimized
away in all cases where it does terminate plus some.

I don't want to get into a pedantic argument over definition.

Well why are you making those pedantic arguments then.

It's *not* an optimization.

No matter the amount of wooly rules introduced.

Suffice to say, I see this as analogous to the copy constructor
elision rules which I tend to like.

It's not analogous; see below.

Arguably, the copy constructor elision rules "screw up the
programmer's intent [...] to produce an /incorrect result/ for correct
code".

No.

Copy constructors were from the outset defined as special, because they do a
very special and limited job, and a copy constructor call elision does not
violate those semantics: it gets the same job done more efficiently, that's all.

A loop can do anything; elision of a loop in general changes the code's effect
so as to produce /incorrect results/.

I also think that this particular thing in this particular case
is a good thing.

Copy constructor elision = good thing, yes.

The corresponding thing for a loop would be a new loop construct like
'perhaps_loop_while' or a loop attribute '[[tentative]]', whatever, with the
semantics that a provably infinite such loop can be elided.

I don't think anyone would actually use that idiot's constructs, do you?

However, unlike the copy constructor elision rules, 1- there is code
already out there which would break under this new infinite loops
rule, 2- I think that the copy constructor elision rules are a lot
more intuitive than this new infinite loops rule, and 3- I think that
the copy constructor elision rules actually have a tangible benefit as
opposed to this new infinite loops rule.

That is, I err on the side of caution when introducing allowances such
as the copy constructor elision rule. I have seen compelling arguments
for the copy constructor elision rule, but I have yet to see anything
near that level of rigor for this new infinite loops rule.

Yes.

You won't see the rigor either, since it's utterly meaningless sabotage.

Whoever proposed this, making fools of the committee?


Cheers,

- Alf
 
J

Johannes Schaub (litb)

Johannes said:
Hello all, i need some advice. Is it actually true that a C++0x
implementation can print "Hello" for the following snippet?

#include <iostream>

int main() {
while(1)
/* do nothing */;

std::cout << "Hello" << std::endl;
}

C++0x seems to allow an implementation to assume that the above infinite
loop terminates, which to me seems to mean that it can entirely ignore
that this loop never wants to stop.

Why is this the way it is? Doesn't it harm a lot of programs?

Also, here is another thought I have:

int a = -1;
for(;;) {
if(a > 100) break;
a++;
}

int *p = new int[a];


This loop *does* terminate, does not access volatile objects, does not call
i/o functions, sync or atomic operations. Yet, the implementation may assume
it terminates. If an implementation is thus free of optimizating it away,
would it not make this program UB?

I don't see how this example is different from the print example above. Both
examples have code after the loop that depend on the loop. Yet the rationale
that the UB is only risen because the loop would not terminate is disproven
by this. Can someone show please what paragraph makes these both examples
different?
 
J

James Kanze

* Joshua Maurice, on 30.08.2010 02:47:

[...]
Note that no-one has presented an example of actual optimization.
That's because it's impossible to present such an example,
because the purported "optimization" is *not* an optimization,
it's just an idiocy.
For James' purported example above, if the compiler can prove
that the condition expression has no side effects and depends
on nothing external,

Who said anything about depending on nothing external? And "no
side effects" means in the sense of the C++ language: no IO and
no accesses to volatile variables. The effect of one
calculation can still affect the next one. Something like:

inline int f(int in)
{
return in % 2 == 0 ? in / 2 : n * 2;
}

int i;
std::cin >> i;
while (i != 0) {
i = f(i);
}
std::cout << "Whatever" << std::endl;

fits the bill, for example. (Note that if i is not initially
zero, the loop never terminates. I would *not* expect an
optimizer to be able to recognize this.)
 
A

Alf P. Steinbach /Usenet

* James Kanze, on 30.08.2010 17:15:
* Joshua Maurice, on 30.08.2010 02:47:
[...]
Sure it's a hard problem, but I can't imagine it's that common.
Note that no-one has presented an example of actual optimization.
That's because it's impossible to present such an example,
because the purported "optimization" is *not* an optimization,
it's just an idiocy.
For James' purported example above, if the compiler can prove
that the condition expression has no side effects and depends
on nothing external,

Who said anything about depending on nothing external? And "no
side effects" means in the sense of the C++ language: no IO and
no accesses to volatile variables. The effect of one
calculation can still affect the next one. Something like:

inline int f(int in)
{
return in % 2 == 0 ? in / 2 : n * 2;
}

int i;
std::cin>> i;
while (i != 0) {
i = f(i);
}
std::cout<< "Whatever"<< std::endl;

fits the bill, for example. (Note that if i is not initially
zero, the loop never terminates. I would *not* expect an
optimizer to be able to recognize this.)

Is this meant to be an example of something that can be "optimized" by removing
the loop?


Cheers,

- Alf
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top