* James Kanze, on 31.08.2010 12:11:
On Aug 30, 4:24 pm, "Alf P. Steinbach /Usenet"<alf.p.steinbach
(e-mail address removed)> wrote:
* James Kanze, on 30.08.2010 17:15:
[...]
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.)
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.
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.
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.
{