On 21.09.2010 19:41, Joshua Maurice wrote:
>
> Recent discussions on comp.lang.c++ have got me thinking:
>
> "Optimizing away an endless loop"
> http://groups.google.com/group/comp.lang.c++/browse_thread/thread/d2628464578bb118/6f5afbfaa43c49d2
>
> It talks about the following section from the draft
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3126.pdf
> 6.5 Iteration statements / 5
>
> Its language is vague and unhelpful. The most reasonable
> interpretation is that any loop which fulfills the 3 requirements but
> does not terminate causes the program to have undefined behavior. As
> such, it is a defect.
> [...]

What's the current status of this?

WRT to the recent thread of on clc++m [1], the most recent std text
apparently is:
<quote>
The implementation is allowed to assume that any thread will
eventually do one of the following:

       * terminate,
       * make a call to a library I/O function,
       * access or modify a volatile object, or
       * perform a synchronization operation or an atomic operation.

      [ Note: This is intended to allow compiler transformations, such
as removal of empty loops, even when termination cannot be proven.
end note ]
</quote>

John Regehr has posted a very nice article [2] describing how this
wording makes the following program UNDEFINED according to the current
std draft:

#include <iostream>

int fermat () {
 const int MAX = 1000;
 int a=1,b=1,c=1;
 while (1) {
   if (((a*a*a) == ((b*b*b)+(c*c*c)))) return 1;
   a++;
   if (a>MAX) {
     a=1;
     b++;
   }
   if (b>MAX) {
     b=1;
     c++;
   }
   if (c>MAX) {
     c=1;
   }
 }
 return 0;
}

int main () {
 using namespace std;
 if (fermat()) {
   cout << "Fermat's Last Theorem has been disproved.\n";
 } else {
   cout << "Fermat's Last Theorem has not been disproved.\n";
 }
 return 0;
}

(Note that I'm just quoting a slightly modified C++ version of his
prg-text here. I did not try to run that program.)


br,
Martin

[1]: http://groups.google.com/group/comp.lang.c++.moderated/msg/6d23e201268bcb4e?hl=en

[2]: http://blog.regehr.org/archives/161



--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Recent discussions on comp.lang.c++ have got me thinking:

"Optimizing away an endless loop"
http://groups.google.com/group/comp.lang.c++/browse_thread/thread/d2628464578bb118/6f5afbfaa43c49d2

It talks about the following section from the draft
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3126.pdf
6.5 Iteration statements / 5

Its language is vague and unhelpful. The most reasonable
interpretation is that any loop which fulfills the 3 requirements but
does not terminate causes the program to have undefined behavior. As
such, it is a defect.

This piece of the draft is discussed in some small detail here:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2052.htm

[quote]
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.
[/quote]

I'm going to assume that the above quote is the justification for
6.5 / 5 in the current draft, so I will begin with a rebuttal, and end
by showing that the disadvantages outweigh any possible advantages, if
any.

Implicit in the paper N2052 is that loops are not synchronization
primitives - a loop terminating or not terminating "shouldn't" (to
simply their argument) affect whether there is a race condition.
However, I believe that this is in error. A now-classic example (from
paper http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2338.html):
[quote]
switch (y) {
   case 0: x = 17; w = 1; break;
   case 1: x = 17; w = 3; break;
   case 2: w = 9; break;
   case 3: x = 17; w = 1; break;
   case 4: x = 17; w = 3; break;
   case 5: x = 17; w = 9; break;
   default: x = 17; w = 42; break;
}

and x is potentially shared, it is not acceptable to reduce code size
by transforming this to

tmp = x; x = 17;
switch (y) {
   case 0: w = 1; break;
   case 1: w = 3; break;
   case 2: x = tmp; w = 9; break;
   case 3: w = 1; break;
   case 4: w = 3; break;
   case 5: w = 9; break;
   default: w = 42; break;
}

Doing so would introduce a race if y were 2, and another thread were
concurrently updating x. Again the concurrent update might be lost as
a result of the spurious store.
[/quote]

In the above code, the "codepath of execution" is a "synchronization
primitive" insofaras an implementation may not introduce a speculative
write where one was not visible before. Following the exact same
reasoning, if we have a non-terminating loop, then the "codepath of
execution" never passes over a write past the end of the loop, so
introducing a write before the loop is introducing a race condition
just like N2338, both of which are disallowed. The onus is thus on
N2052 and other supporters of 6.5 / 5 to show that the benefits
outweigh the disadvantages.

So, N2052 takes a different approach. It makes the argument that 6.5 /
5 is consistent with the earlier standards (C++98 and C++03), and by
explicitly stating the exception of 6.5 / 5, it clears up any possible
ambiguity (and explicitly allows further optimization by conforming
implementations). This is incorrect.

--
First, let me take a step back. The goal of the standards committee is
to standardize existing practice, and perhaps more rarely to
standardize new practice. It is a common requirement for applications
written in C++ to be stable, memory leak free, and run forever. This
is a very large and very important subset of commercial C++ programs.

Let's take a quick look at what guarantees exist for a conforming
implementation on a non-terminating program. The relevant part appears
to be "1.9 Program execution".

"1.9 Program execution / 1" is the "as-if" rule. However, apart from
the usual "as-if" rule interpretation, it does say that a conforming
implementation is required to emulate the observed behavior of the
abstract machine.

"1.9 Program execution / 6" defines the observable behavior of the
abstract machine as the sequence of volatile reads, volatile writes,
and calls to library I/O functions. An attached note suggests that an
implementation can offer more I/O functions as an extension, and it
ought to treat those calls as "observable behavior" as well.

"1.9 Program execution / 11" gives the least requirements of an
implementation. In short:
1- requirements on the state of volatile objects
2- At program termination, data in files shall be in a conforming
state.
3- Sane requirements on interactive I/O shall be satisfied, and these
requirements are implementation-defined.

Let's take the example of a chat program with a client-server.
Ideally, the server (and the client) should be able to run forever.
While it is difficult for the C++ standard to cover such system
specific calls, it at least pays lip service to this with the note in
1.9 / 6. By that note, the network calls should be considered
"additional I/O library functions", and thus should network calls
should be considered "observable behavior". By any reasonable
interpretation, the network calls should also be "interactive I/O",
and thus they should fall under the requirements of 1.9 / 11, bullet
3. Thus a chat server which stays up forever has perfectly guaranteed
behavior, enough to guarantee that it works - at least the past C++
standards have attempted to provide as much guidance as it could on
this implementation-defined domain of interactive I/O in 1.9 / 11.
--

A crucial point in this argument of N2052 is that the earlier
standards give no guarantees of behavior to non-terminating programs.
>From this, the paper concludes that any program which does not
terminate necessarily has undefined behavior. However, I have shown
otherwise with my server-client chat server example - specifically the
"interactive I/O" guarantees of 1.9 / 11 does give guarantees to non-
terminating programs. Thus, the argument of N2052 that 6.5 / 5 is
consistent with past standardization is not true. The proposed
exception of 6.5 / 5 would be a break with past standardization.

However, let's see if the argument can survive this discovery of the
1.9 / 11 "interactive I/O" rule. Arguably, in my client-server chat
program example, the non-terminating loop would contain calls to I/O
library functions, so it would not run afoul of 6.5 / 5. However,
there are other real non-terminating programs out there which do
actually have a trivial "for (;;);" loop. They could be signal
driven.

Furthermore, as an entirely separate point, the practice of using
infinite loops for testing and in production systems is well accepted
by the community at large.

I see this exception of 6.5 / 5 as akin to the copy constructor
elision exceptions of "12.8 Copying class objects / 15". However,
there are important differences. The copy constructor elision rules
are "sensible", in terms that it's "reasonable" that copies "should
be" "equivalent". Moreover, the copy constructor elision exception is
narrowly tailored to only return values and function arguments.
Moreover, the rule generally results in a program which still has
defined behavior. The "non-terminating loop" rule of 6.5 / 5 is none
of that. It is not sensible; if I write an infinte loop, I expect an
infinite loop. This is qualitatively different than omitted a few
extra temporary objects when they're "not needed" copies. The rule is
not narrowly tailored: it could apply to any loop anywhere in the
program, and most insidiously, the exception will result in effective
undefined behavior for some programs where they were perfectly defined
before.

Finally, myself and others have yet to see a compelling use case where
this would be a great benefit for optimization.

So, we have a change which is a source level breaking change from past
standards, and it is a breaking change from well accepted practice. As
such, the onus rests on the proponents of this breaking change to show
that the benefits greatly outweigh the negatives. Myself and others do
not see this. We see a plurality of negatives: source level breaking
change, breaking change from well accepted practice, an entirely
nonsensical rule (when I write an infinite loop I mean an infinite
loop), and we see no tangible benefits besides a handwaved "it will
help optimizing compilers".

At the very least, even if this is a serious problem, it's too late to
"fix it" now.

Moreover, if the compiler is unable to prove that a loop terminates,
perhaps a compiler warning would suffice, along with a possible
annotation that the loop terminates? Perhaps this would be too
tiresome on the programmer, but I present it as at least a plausible
alternative to the present insanity.

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]