Optimizing away an endless loop
Johannes Schaub (litb)
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?
Johannes Schaub (litb)
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.
William Ahern
<snip>
> 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?
There was a long thread in comp.std.c on what sounds like a similar change
to the C1X specification. Here's the thread
http://groups.google.com/group/comp.std.c/browse_thread/thread/bc57eedf030cd192
Joshua Maurice
wrote:
> Johannes Schaub (litb) wrote:
> > 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,
>
> `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.
Johannes Schaub (litb)
It's over here: http://stackoverflow.com/questions/3592557/optimizing-away-
a-while1-in-c0x
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?
Kenneth 'Bessarion' Boyd
wrote:
> 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.]
James Kanze
> > > #include <iostream>
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.
--
James Kanze
Alf P. Steinbach /Usenet
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
--
blog at <url: http://alfps.wordpress.com>
Joshua Maurice
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.
Alf P. Steinbach /Usenet
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.,
Joshua Maurice
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.
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".
Alf P. Steinbach /Usenet
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...
Alf P. Steinbach /Usenet
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.
Joshua Maurice
+use...@gmail.com> wrote:
> * Joshua Maurice, on 30.08.2010 08:53:
> > 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?
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.
> > 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.
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.
Kai-Uwe Bux
> Here, we're basically exhaustively testing whether Fermat's Last
> Theorem is true by testing all possible couterexamples, one at a
> time.
Alf P. Steinbach /Usenet wrote:
> * Joshua Maurice, on 30.08.2010 08:55:
>> On Aug 29, 11:53 pm, Joshua Maurice<joshuamaur...@gmail.com> wrote:
>>> 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".
>
> 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
Alf P. Steinbach /Usenet
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.
>
>>> 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.
>
> 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,
Johannes Schaub (litb)
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?
James Kanze
[...]
> > 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.)
--
James Kanze
Alf P. Steinbach /Usenet
Is this meant to be an example of something that can be "optimized" by removing
the loop?
Cheers,
Joshua Maurice
wrote:
I think there is a difference. I forget the exact phrasing, but I
don't think anyone is talking about optimizing that loop. I think
we're only talking about removing loops which have no side effects ala
the C++ standard definition /and/ for which no one after the loop
depends on objects modified in the loop.
Joshua Maurice
No no no. When I said that all loops
1- which terminate,
2- which have zero visible side effects to the abstract machine of the
C++ standard,
3- and which do not write to objects read outside the loop,
should be optimized into nothing.
In this context, should is like a moral imperative. It denotes a
desired outcome. Obviously the desired outcome is impossible. I stated
this explicitly immediately following this claim in my first post.
"Should" in that context does not imply 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.
This is just as silly as saying "Compilers should optimize all tail
recursive functions into their iterative methods" implies "If a
compiler cannot prove that a function is not equivalent to a tail
recursive function, then it should replace the function with return
42".
I think because I don't agree with you entirely, you immediately cast
me into the opponent's camp, which is largely false.
Copy constructor elision changes the semantics of the program. Suppose
you had an instance counting thing in a copy constructor, and you
wrote logic to trigger whenever the number of copies became X, then
copy constructor elision would break your program. Copy constructor
elision is a very narrow allowance for the compilers to translate
source not equivalently to the naive way. However, we live with it
because it "jives" with our intuition: we're just talking about making
a couple less copies, and all copies "should be" are equivalent,
right?
I think that it's a little less intuitive for a complete beginner to
try and sell him that "all loops should terminate" as opposed to
"copies of objects made by the copy constructor should be equivalent",
but I don't think we're talking entirely different kinds here, just
matter of degree.
However, I basically agree with your recommendations that this is a
really bad idea to standardize, and I definitely do not want my
compiler to do this. (If it is a big problem, I would want my compiler
to issue a warning, though.)
James Kanze
[...]
> > 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?
According to the wording in the current standard, the compiler
could remove the loop, regardless of the input. (How important
it is, I don't know. It's a very artificial example.)
--
James Kanze
James Kanze
wrote:
> > #include <iostream>
No. In fact, an implementation is free to optimize it away; a
good optimizing compiler will produce the same code here as if
you'd just written:
int *p = new int[101];
> I don't see how this example is different from the print example above.
The loop terminates.
> 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?
It's not in the standard; it's in the proposed draft C++0x:
§6.5/5 in N3000 (which isn't the very latest, but is relatively
recent):
A loop that, outside of the for-init-statement in the
case of a for statement,
-- makes no calls to library I/O functions, and
-- does not access or modify volatile objects, and
-- performs no synchronization operations (1.10) or
atomic operations (Clause 29)
may be assumed by the implementation to terminate. [
Note: This is intended to allow compiler
transformations, such as removal of empty loops, even
when termination cannot be proven. —end note ]
The wording is pretty vague: there's no mention of undefined
behavior, for example. I'd say that there is no undefined
behavior, but that the standard allows alternate semantics
(which may result in undefined behavior if you haven't provided
for them).
--
James Kanze
Alf P. Steinbach /Usenet
Well it doesn't make the program faster (to see that, try to calculate how much
faster you think it makes it). So it's not an optimization on that count. And it
makes the program produce an /incorrect result/, contrary to the intent of
infinitely looping, which also means that it's not an optimization.
In short, it's not an optimization, and the importance is about how much damage
it does, not about any benefit (there's none), so I say it's pretty important.
So, no optimization example has been shown.
And it cannot be shown, because this is just inane damage to the language.
Nobody of non-negative IQ would use 'perhaps_loop_while' if they had any choice,
but, our disagreement isn't over that, but merely over whether one should
pretend that whoever proposed this idiocy wasn't actively pulling one over, i.e.
pretending that there is some likeness to actual optimization.
Cheers & hth.,
James Kanze
Removing the loop makes the program inifinitely faster, for some
input. The results are incorrect, I agree, but apparently, the
standard gives the compiler the explicit right to do this.
[...]
> And it cannot be shown, because this is just inane damage to
> the language.
I tend to agree, but since the proposed standard allows it...
> Nobody of non-negative IQ would use 'perhaps_loop_while' if
> they had any choice, but, our disagreement isn't over that,
> but merely over whether one should pretend that whoever
> proposed this idiocy wasn't actively pulling one over, i.e.
> pretending that there is some likeness to actual optimization.
The actual question is whether someone might use a
perhaps_loop_while, and what the consequences are, according to
the standard. In fact, if I understand correctly, the standard
has also invalidated true infinite loops, which are used in some
specific types of programs.
--
James Kanze
Kai-Uwe Bux
> Johannes Schaub (litb) wrote:
>
>> 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.
Ok, so now I start to wonder what the provision actually means. It reads
thus:
A loop that, outside of the for-init-statement in the case of a for
statement,
? makes no calls to library I/O functions, and
? does not access or modify volatile objects, and
? performs no synchronization operations (1.10) or atomic operations
(Clause 29)
may be assumed by the implementation to terminate.
Now, this "may be assumed" allows the compiler to make a possibly false
assumption. As pointed out above, if the assumption is wrong, the behavior
is undefined. I wonder what happens if the assumption is true for some but
possibly not all inputs. Is the compiler allowed to make the (false)
assumption that the loop _always_ terminates? In this case, we would have
undefined behavior even for those values where the loop happens to
terminate.
Also, what happens if we just cannot proof that a loop terminates? Does that
mean, we cannot argue that the program is well-defined?
Example:
#include <iostream>
int main ( void ) {
unsigned long long n;
unsigned long long m = 0;
std::cin >> n;
while ( n != 1 ) {
++ m;
if ( n % 2 ) {
n = 3*n + 1;
} else {
n /= 2;
}
}
std::cout << m << "\n";
}
// end of file
If the 3n+1 conjecture should be false, we may see undefined behavior; or: a
proof that the above is well-defined entails a proof of the 3n+1 conjecture.
So, if this program prints something, does the result mean anything? or do I
have to make m volatile?
Best
Kai-Uwe Bux
Armen Tsirunyan
> 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.
>
+1 for Alf :)
This is absolutely outrageous. If compilers DO actually perform this
"optimization"
the nazis will once again ride on dinosaurs.
I myself have used empty loops to test things, like, OK, let's put an
empty loop here and see if the program ends, so I'll see if the code
reaches that particular branch... I think I am not the only person
done so who has and is willing to so under the rule of 0x
Joshua Maurice
I found a paper on the committee's website, which at least gives a
slightly more rational explanation for this proposed new rule.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2052.htm
>>>>
Semantics of some non-terminating loops
Concern has been expressed about whether it is safe and legal for a
compiler to optimize based on the assumption that a loop will
terminate. The canonical example:
for (T * p = q; p != 0; p = p->next)
++count;
x = 42;
Is it valid for the compiler to move the assignment to x above the
loop? If the loop terminates, clearly yes, because the overall effect
of the code doesn't change, and, in the absence of synchronization,
there is no guarantee that the assignment to x will not be visible to
a different thread before any assignments to count. But what if the
loop doesn't terminate? For example, may a user assume that a non-
terminating loop effects synchronization, and may therefore be used to
prevent a data race? Clearly, a loop that contains any explicit
synchronizations must be assumed to interact with a different thread,
and a loop that contains a volatile access or a call to an I/O
function must be assumed to interact with the environment, so
optimization opportunities for such a loop are already limited. But
what about a simple loop, as above?
If such a loop does not terminate, then clearly neither the loop
itself nor any code following the loop can have any observable
behavior. Moreover, as the "least requirements" refer to data written
to files "at program termination", the presence of a non-terminating
loop may even nullify observable behavior preceding entry to the loop
(for example, because of buffered output). For these reasons, there
are problems with concluding that a strictly-conforming program can
contain any non-terminating loop. We therefore conclude that a
compiler is free to assume that a simple loop will terminate, and to
optimize based on that assumption.
<<<<
I believe the mandate should be to standardize existing practice, and
in limited cases standardize currently nonexistent practice.
The quote is a very standardeze-y argument. It proceeds from the very
limited guarantees of the standard that the contents of file are only
guaranteed at the end of the execution. However, that is bogus. A lot
of us have seen servers for which these limited guarantees result in
an unworkable model. We need a long lived process which writes to a
file, and we need a guarantee that the file has X contents after a
flush (transactions, recovery, other programs reading the file, the
file is a pipe or socket, etc.). So, from this very shaky and false
foundation, the paper goes on to conclude that any C++ program which
does not terminate has no defined behavior. Again, this is just silly.
It's definitely not standardizing existing practice, and it's
definitely not standardizing any useful practice either. Instead, it's
the result of rules lawyering of the worst kind.
Maybe it's time to increase the guarantees given to the abstract
machine to machine current practice? Then again, I've seen enough
discussions about file flushes not actually working, either because
the OS caches it in memory despite your instructions, and most evilly
because there's a hardware cache in the hard drive unit itself which
caches it despite a request to flush, so this isn't trivial.
It is an interesting take on it. I didn't quite see the argument until
I read that paper. To quote the paper above:
> For example, may a user assume that a non-terminating loop effects synchronization, and may therefore be used to prevent a data race?
My answer is a resounding "yes". In the committee papers discussing
threading and race conditions, there are examples which describe how
an implementation may not introduce a load on a branch of a switch
where there was none before. In that same line of thought, an
implementation may not introduce a new load by moving a load from
after to before a (potentially) infinite loop, any more than it could
move a load out of an "if (false)" branch or introduce a load which
was not there before in a branch of a switch. Moreover, the semantics
of the abstract machine should be changed to accommodate standard and
well accepted practice of programs which are meant to run for years or
forever, such as servers of all varieties.
As a preemptive reply to the other arguments I've heard before: it
might result in more efficient code to introduce a new load in a
switch statement branch, but that can introduce a race condition, so
an implementation may not do it. It changes the semantics of the
program as written. Equivalently, an infinite loop has well defined
semantics, and they are used in practice and are well accepted, and
moving loads before the loop can introduce race conditions and change
the semantics of the program. Any lost "optimization opportunities"
are dwarfed by having a sane programming language without a multitude
of "exceptions" such as copy constructor elision and return value
optimization. I'm happy with the current exception of "copy
constructed objects, in certain situations, might be elided, so they
should be equivalent". I am not happy with "sometimes, the
implementation might introduce a race condition", and I would
definitely not be happy trying to debug that in a complex piece of
software.
cpp4ever
What can I say? I'm gob-smacked that Alf would appear to be the first
person to find this compiler suggestion insane, or at least the mental
aberration of people who should know better.
Alf, can I be second in line after yourself to deliver that ass kicking?
Regards
cpp4ever