what is the right value about a = a++;

[Jens Gustedt]

Am 02/10/2012 05:24 AM, schrieb Shao Miller:

Is it realistic that an implementation might have a thread of execution
for each independent branch of evaluation, so that the evaluation order
of some expressions might be simultaneous?

thread of execution in a broad sense, certainly, such as done for
pipelining processors with out-of-order execution

compilers do reordering of statements all the time, and not imposing a
sequence point between two evaluations is giving the necessary slackness
to the compiler for doing so.

Jens

 

[James Kuyper]

I can't make that work. Your usage emphasises (explicitly) the idea of
pleasure being involved, and that is surely the difference Richard
Harter is pointing out. "What pleased them most" is about pleasure and
gratification, but "whatever they please" is about having "the will or
desire; to have the inclination or disposition; to think proper; to
choose" (though having pleasure in the result is not excluded, of
course).

I think that any interpretation of "whatever they please" that doesn't
connect to the concept of pleasure is somewhat odd, but it's not really
a problem for what I was saying. The key point of what I wrote was that
"whatever they please" is different from "what they thought was best";
the details of how they differ are less important than the fact of a
difference.

It's not exactly an unusual thing for people to have the will, desire,
inclination or disposition to do something other than what they think is
best. It's not even usual for people to actually choose to do something
other than what they think best.

 

[James Kuyper]

I agree with Ben; it doesn't work, though you might give it a try. If
you do, start with "whatever they chanced to do" or something similar.

Here's the re-write; it wasn't quite as simple as I implied, but it's
still trivial:

"What they thought was best" is not, in general, the same as "What
they pleased". For instance, some implementers might have been
pleased to insert warning messages that made fun of people
whose politics they disagreed with. But what they thought was best
probably didn't include losing that portion of their potential market
which would have been offended by such messages, nor that additional
share of their potential market that might have felt that such warning
messages showed insufficient professionalism.

I tried to come up with an example that more directly applies the
evaluation order of operands, but I had a hard time coming up with any
plausible examples where an implementor might have been pleased to do
something other than what they thought best.

That said, the point you made is quite valid. What I was getting at,
though, is that without the constraint of a standard or something
implementation choices have an element of caprice and arbitrariness.

I don't think that element is a big one. Implementors who pay attention
to the needs of their customers tend to find their choices significantly
constrained by those needs, and so long as they work within those
constraints, they tend to have more customers than those implementers
who let caprice and arbitrariness rule their designs.

 

[James Kuyper]

On 02/10/2012 11:35 AM, Kenneth Brody wrote:
....

Pre-ansi days were certainly "fun" (FSVO). ....
I also learned (the hard way) not to use bit-fields on things written to
disk, when we used a compiler which allocated bits in the opposite order.
(Does the current Standard require a certain order? ie: if you have
"unsigned int foo:1", is it required to be either at the MSB or LSB?)

No. It's not even required that different data types for the same
implementation use the bits in the same order on all types. Unsigned
char could use 1 ... 8, unsigned short could use 16 ... 1, unsigned
could use 1 32 2 31 ... 15 16, etc. I can't imagine any hardware being
built in a way that would make that a reasonable way to implement C, but
such an implementation could be conforming.

 

[Stephen Sprunk]

Note that this is still allowed under strict left-right, bottom-up evaluation.

My interpretation of "strict left-to-right" evaluation is equivalent to
this:

tmp1 = a++;
tmp2 = a++;
foo(tmp1, tmp2);

So, this would be a valid optimization:

foo(a, a+1);
a+=2;

In contrast, the above asm has the side effect of the first "a++"
expression occurring _after_ the evaluation of the second expressions,
like this:

foo(a, a);
a+=2;

Because a is not volatile, the code does not require two actual increments.
That is merely the abstract semantics.

Of course. However, when exactly each postincrement happens _in the
virtual machine_ does affect the value of the second argument to foo().

S

 

[Stephen Sprunk]

True, the as-if rule can be satisfied by the single "add 2" operation,
but the "side-effects must take place immediately" cannot.

And, making "a" volatile gives this code:

mov eax, DWORD PTR _a
mov ecx, DWORD PTR _a
mov edx, 1
add DWORD PTR _a, edx
add DWORD PTR _a, edx
push eax
push ecx
call _foo
add esp, 8

Now, the two increments are done separately, but the code was still
rearranged so that they still take place after grabbing the original
values of "a". Whether this is faster than moving one of the adds
between the two reads of "a", I don't know, nor do I have the time or
resources to investigate.

"Faster" is perhaps irrelevant in this case because _the result is
different_, which shows exactly why invoking undefined behavior can be
such a problem.

The above asm does this:

tmp1 = a;
tmp2 = a;
a = tmp1 + 1;
a = tmp2 + 1;
foo(tmp1, tmp2);

Note that, despite two increments, the final value of a is only _one_
greater than its initial value.

This would not be a valid optimization if there were a sequence point
between arguments, as proposed.

S

 

[Stephen Sprunk]

True; but the fact that different current compilers give different
results cannot be used to validly infer that the behavior is undefined.
The behavior could be implementation-defined, or simply unspecified, or
one of the compilers you're comparing could be non-conforming.

True, divergent behavior could have been classified several different
ways by the Standard. I was merely pointing out that divergent behavior
caused such classification, rather than the classification causing such
divergent behavior as you seemed to be saying.

Incidentally, it was made explicitly clear that "existing code is
important; existing implementations are not". I would presume that was
based upon the fact that, for any reasonably successful implementation
of C, the amount of code written for use on that implementation greatly
outweighed the amount of code required to implement it.

True. However, the importance of that statement comes from the fact
that a significant amount of "existing code" had come to _depend_ on the
behavior of a particular implementation. Therefore, such behavior would
need to remain valid for that implementation. The insides of a compiler
might need to change, and new features could be tacked on, but it
couldn't be done in a way that forced existing code to stop working, no
matter how ugly the code might be.

S

 

[Stephen Sprunk]

I tried to come up with an example that more directly applies the
evaluation order of operands, but I had a hard time coming up with any
plausible examples where an implementor might have been pleased to do
something other than what they thought best.

Some implementor might have been pleased to evaluate function arguments
left-to-right, for cultural reasons, but found it was "better" to
evaluate them right-to-left.

S

 

[Stephen Sprunk]

Then if they did whatever they thought was best then that was what
they pleased. I'm not sure what you think "whatever they pleased"
means.

There are a great many things that would please me but which are not the
"best" thing to do.

Whoa. The claim was about the cost of implementing varargs, something
only used in a rather small number of cases. For that matter, at the
time varargs was not standardized. Optimizing processing varargs was
and is a micro-optimization, then and now.

True, but it would be perverse to have right-to-left evaluation for
varargs calls but left-to-right evaluation for non-varargs calls.

In fact, a similar perversity actually exists in the wild: Win16/32 API
calls are evaluated left-to-right because the API specifies a "Pascal"
(push onto stack from left to right) calling convention, but non-API
calls will use a "C" (push onto stack from right to left) calling
convention. So, two consecutive function calls may have two different
orders of evaluation!

Granted. And it is also true that the generated code in the bodies of
functions also suffered both because the architectures were limited
and, quite bluntly, the quality of most implementations were limited.
Furthermore evaluating function arguments right to left rather than
left to right is an almost imperceptible micro-optimization when it is
an optimization at all.

Adding a few cycles to _every_ function call would add up; computers
back then were slow enough as it was.

IMNSHO that performance penalty is much more fantasy than reality. On
the other hand the cost of reworking all of those compilers was a very
real cost. Quite reasonably, nobody wanted to pay that price.

I'm sure that was factored in as well. Plus, there was a large base of
code that may have _depended_ on a particular order of evaluation. If
nothing else, it would have been impossible to prove there wasn't.

On the other hand there is a real benefit when all behaviours are well
defined, when all code is either legal or illegal, and what the code
is supposed to do can be determined by inspection of the code. The
qualility of C as a language would IMO be enhanced if most of these
"undefined behaviours" were compilation errors.

True, but that is a luxury of developing standards _before_ amassing a
huge codebase. That's not how C developed.

S

 

[James Kuyper]

On 07-Feb-12 16:00, James Kuyper wrote: ....

True, divergent behavior could have been classified several different
ways by the Standard. I was merely pointing out that divergent behavior
caused such classification, rather than the classification causing such
divergent behavior as you seemed to be saying.

I think it was Nick who made the comments you're referring to, not me.
And a more accurate summary of what he said would be that the
classification allows the divergent behavior, rather than causing it.

The standard has had a major impact on compiler diversity. I know
because I remember what it was like before standard C was commonplace.
The committee didn't bless all existing variations in C compilers; some
variations were allowed by using one of those classifications, but most
were disallowed, and the ones that were disallowed rather quickly
disappeared. Unlike C99, C90 was adopted rather quickly.

 

[Joe keane]

The efficient:

PUSH C
PUSH B
PUSH A

versus the conforming:

SUB SP,12
STOR [SP],A
STOR [SP+4],B
STOR [SP+8],C

(Note, of course, that it is possible that there are machines on which the
calculated-store is faster than push, and may improve speed even with the
added stack-adjust, in which case it is certainly free to generate such
code. The problem comes when you mandate it.)

I'm almost sure that the Pentium ran consecutive pushes two per cycle.

There is probably some window where this change was faster, but it seems
short-sighted; if the compiler guys had said 'we're going to use your
instructions like you said', i'm pretty sure that the hardware guys
would ensure that it's competitive.

 

[Kaz Kylheku]

defective. In general, I'm a big believer in the concept that not all
code needs to be portable - but this particular kind of non-portability
doesn't seem to have any value.

Precisely! It is a "gratuitous" nonportability that is not linked to
any operating system or hardware issue. Gee, let's arbitrarily make certain
expression combinations have unspecified or undefined behavior, even though
they contain valid operations on valid operands.

 

[Ben Bacarisse]

On 2/8/2012 8:41 PM, John Bode wrote:
[...]
The truth of the matter is, is that when, precisely, a side effect most
efficiently takes effect, is very platform-dependent, and can even vary from
expression to expression on a given platform.


Is this anything more than received wisdom? Does anyone have a
concrete example (read: generated machine code) showing *how*
rearranging evaluation order can make an operation more efficient?

I mean, I've parroted that line more than once, but I certainly can't
point to an example of where it makes a difference.

foo(a++,a++);

On my system, this code is generated:

mov eax, DWORD PTR _a
push eax
push eax
add eax, 2
mov DWORD PTR _a, eax
call _foo
add esp, 8

By delaying the post-increment, the code is more efficient than requiring
two separate increments.

Note that this is still allowed under strict left-right, bottom-up evaluation.

Not according to the "and all side-effects must take place
immediately" part of the argument. In that case, the second parameter
*must* be one more than the original value of a.

Because a is not volatile, the code does not require two actual increments.
That is merely the abstract semantics.

True, the as-if rule can be satisfied by the single "add 2" operation,
but the "side-effects must take place immediately" cannot.

I don't follow this reasoning. The as-if rule can be used to justify
removing the increments entirely (if a is not reference later, for
example) so I don't see why it can't be used to justify their happening
together.

<snip>

 

[Joshua Maurice]

Note that this is still allowed under strict left-right, bottom-up evaluation.

Because a is not volatile, the code does not require two actual increments.
That is merely the abstract semantics.

So this is really tangential to the debate. (Yes, rearranging computations is
important and crucial necessary for optimization.)

I'm sorry for potentially derailing this conversation, but this is one
of my pet peeves. You do know that volatile - apart from correct
signal handling and setjump longjump nonsense - is completely useless
in portable code, right? When you said "because a is not volatile",
you are immediately assuming several things about volatile which are
not true, and have never been true, and will not be true in C11. A
perfectly conforming implementation is free to basically ignore
volatile and compile it down as if it wasn't there. The semantics of
the C abstract machine do not specify what exactly a volatile write
"means". They just say that it's part of the visible behavior of the
abstract machine, while the standard does not define what that means.

As a matter of facts of current implementations, I have been told by
reliable people that volatile is insufficient alone to do MMIO on most
modern machines, rendering its original purpose moot. volatile is a
relic with no support from most compilers nowadays - apart from some
incredibly non-portable use in some kernel code, and with the advent
of C11, it should hopefully become extinct (again apart from setjump
longjump nonsense and legacy code).

 

[Kaz Kylheku]

Am 02/10/2012 05:24 AM, schrieb Shao Miller:

thread of execution in a broad sense, certainly, such as done for
pipelining processors with out-of-order execution

compilers do reordering of statements all the time, and not imposing a
sequence point between two evaluations is giving the necessary slackness
to the compiler for doing so.

That is false. A viable compiler must optimize across sequence points.
The necessary slackness comes from analyzing the data flows in the intermediate
graph structure representing the program.

 

[Stephen Sprunk]

Proof?

I've already provided one example.

In the majority of cases, C code is not well-written. The history of C
programming at large is riddled with crashing applications and operating
systems, and exploitable security holes in online systems.

I disagree, but perhaps my perspective is limited by where I've worked.

Thanks for the clueful suggestion, but, see, what I need to know first is
WHERE this is hiding in a large code base.

I agree. If C had a way to mark functions const/pure (as C++ does),
then it would be easy for compilers to flag a warning in cases where
unspecified order of evaluation might cause a problem; however, without
that ability, there would be far too many false positives for such a
warning to be useful.

S

 

[Kaz Kylheku]

Hence the existence in some implementations of "extern pascal".

Order of argument evaluation is not calling convention.

extern pascal was needed to conform to a calling convention.

 

[Phil Carmody]

You could say that to anyone who is working on the next standard.

Those who worked on C11 didn't want C99, and those who worked on C99
didn't want C90.


No, there are not. There are only outdated beliefs rooted in computer
science shamanism.

Tosh. What was being asked for was the removal of CSE elimination for a
start. Any compiler too dumb not to do CSE elimination is not one I'd
chose to use, and any language that forbids CSE elimination is one I
would have no interest in learning anything more about. This is not
shamanism, this is common sense.

Phil
--

I'd argue that there is much evidence for the existence of a God.

Pics or it didn't happen.
-- Tom (/. uid 822)

 

[Phil Carmody]

The efficient:

PUSH C
PUSH B
PUSH A

versus the conforming:

SUB SP,12
STOR [SP],A
STOR [SP+4],B
STOR [SP+8],C

(Note, of course, that it is possible that there are machines on which the
calculated-store is faster than push, and may improve speed even with the
added stack-adjust, in which case it is certainly free to generate such
code. The problem comes when you mandate it.)

I'm almost sure that the Pentium ran consecutive pushes two per cycle.

You remember correctly. push-after-push was a known often-used case
that was optimised for. The latter of course has an AGI, which was
very expensive on a Pentium. So from a 90's persective, the above
looks like H/W-optimised vs. S/W pessimised.

Phil
--

I'd argue that there is much evidence for the existence of a God.

Pics or it didn't happen.
-- Tom (/. uid 822)

 

[Kaz Kylheku]

Tosh. What was being asked for was the removal of CSE elimination for a
start. Any compiler too dumb not to do CSE elimination is not one I'd
chose to use, and any language that forbids CSE elimination is one I
would have no interest in learning anything more about. This is not
shamanism, this is common sense.

CSE elimination in C compilers is not rooted in unspecified evaluation order,
but in the freedom to optimize, so long as the externally visible behavior
agrees in some ways with the abstract behavior.

You don't have to evaluate a similar expression twice, if it makes no
difference (side-effect wise).

The following has to produce two x's, even now; though we don't know which
expression's x is printed first:

putchar('x') + putchar('x');

the putchar('x') common subexpression can't be (entirely) reduced to one
instance because there is an external function call which may have a side
effect (and does).