Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > what is the right value about a = a++;

Reply
Thread Tools

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

 
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-08-2012
On 2012-02-07, Kenneth Brody <(E-Mail Removed)> wrote:
> On 2/7/2012 3:15 AM, Kaz Kylheku wrote:
>> On 2012-02-07, Barry Schwarz<(E-Mail Removed)> wrote:
>>> On Mon, 6 Feb 2012 02:33:24 -0800 (PST), lujnan<(E-Mail Removed)>
>>> wrote:
>>>
>>>> On Feb 6, 5:45 pm, bert<(E-Mail Removed)> wrote:
>>>>> On Monday, February 6, 2012 8:10:00 AM UTC, lujnan wrote:
>>>>>> b = a = a++;

> [...]
>> I don't want diagnostics; I want strict left to right evaluation order
>> of operands and subexpressions that complete their side effects before
>> yielding a value.

>
> So, what you are really saying, is you want to eliminate most of C's
> optimization abilities, by restricting the order in which the expression
> *must* be evaluated, and side effects *must* be completed?


I do not believe that this is where "C's optimization abilities" come from
at all.

(Many of the optimization abilities of some early compilers from circa 1980
may have come from that, however.)

Do not forget the "as if" principle. I would want the above in the abstract
semantics, not in the actual semantics, of course.

Remember, C already has some constraints on evaluation order, like sequence
points between statements. Do you believe that sequential statements defeat
optimization? Do you think that i++; i++ is slower than i += 2 because
it calls for i to be updated twice? (Assume non-volatile-qualified i.)
 
Reply With Quote
 
 
 
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-08-2012
On 2012-02-07, Richard Harter <(E-Mail Removed)> wrote:
> On Tue, 07 Feb 2012 15:12:53 -0500, Kenneth Brody
><(E-Mail Removed)> wrote:
>
>>On 2/7/2012 3:15 AM, Kaz Kylheku wrote:
>>> On 2012-02-07, Barry Schwarz<(E-Mail Removed)> wrote:
>>>> On Mon, 6 Feb 2012 02:33:24 -0800 (PST), lujnan<(E-Mail Removed)>
>>>> wrote:
>>>>
>>>>> On Feb 6, 5:45 pm, bert<(E-Mail Removed)> wrote:
>>>>>> On Monday, February 6, 2012 8:10:00 AM UTC, lujnan wrote:
>>>>>>> b = a = a++;

>>[...]
>>> I don't want diagnostics; I want strict left to right evaluation order
>>> of operands and subexpressions that complete their side effects before
>>> yielding a value.

>>
>>So, what you are really saying, is you want to eliminate most of C's
>>optimization abilities, by restricting the order in which the expression
>>*must* be evaluated, and side effects *must* be completed?

>
> Well, no, he isn't saying any such thing. You just made it up. The
> fact that evaluation order in C is left to the compilers has very
> little to do with optimization; it is a historical artifact that came
> from endorsing existing practice when the ANSI standard was put
> together. Existing practice then was that compiler writers could do
> evaluations in whatever they pleased and they did.


Exactly! Evaluation order could not have been standardized at the time
C was standardized for the first time, simply because it would have required
most compilers to change something. This is not the proper business of
a standard (to invent new stuff, that is). The proper business is to
identify the commonality in what is out there and codify it.

But, evidently, it IS now the business of C standardization to invent new crud.
So why don't they put a priority on tying loose ends left over from
the 1980's?

Before they started introducing crud like variable length arrays, they should
have revisited the behaviors that could not have been pinned down in 1989, and
tightened them up.

The problem is, I suspect, that some people have their egos invested in this
idiotic sequence point stuff. To throw it out the window would be a huge
backpedaling. In C99 they just about nearly put out an new informative annex
which introduced a formal model of sequence points, which polished this turd
into a foot-deep shine.
 
Reply With Quote
 
 
 
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-09-2012
On 2012-02-07, Stephen Sprunk <(E-Mail Removed)> wrote:
> On 07-Feb-12 15:50, Richard Harter wrote:
>> On Tue, 07 Feb 2012 15:12:53 -0500, Kenneth Brody
>> <(E-Mail Removed)> wrote:
>>> On 2/7/2012 3:15 AM, Kaz Kylheku wrote:
>>>> I don't want diagnostics; I want strict left to right evaluation order
>>>> of operands and subexpressions that complete their side effects before
>>>> yielding a value.
>>>
>>> So, what you are really saying, is you want to eliminate most of C's
>>> optimization abilities, by restricting the order in which the expression
>>> *must* be evaluated, and side effects *must* be completed?

>>
>> Well, no, he isn't saying any such thing. You just made it up. The
>> fact that evaluation order in C is left to the compilers has very
>> little to do with optimization; it is a historical artifact that came
>> from endorsing existing practice when the ANSI standard was put
>> together. Existing practice then was that compiler writers could do
>> evaluations in whatever they pleased and they did.

>
> No, they did evaluations in the order that made the most sense (i.e. had
> the best performance) for their particular implementation--and
> implementations vary.


Old compilers had hard-coded syntax-directed translation behaviors that were
convenient for the implementor. For instance a function call could be
handled as a single unit emitting some boiler-plate expansion.

> For instance, varargs is more straightforward to implement with
> right-to-left evaluation of arguments, at least with a stack-based
> calling convention.


You don't see that you're switching topics from "best performance" to
"straightforward to implement"?

The order matters only for arguments that have side effects. Something like
f(a,b,"foo",x+y) can be evaluated in any order, even if the abstract semantics
calls for strict left to right.

If there are side effects, the order is required so that the same result
is reproduced no matter what. The code generated by the compiler from
a straightforward expression like f(i++, i++) should be no slower
than from an explicit refactoring like
{ int temp0 = i++, temp1 = i++; f(temp0, temp1); }.

> Order of evaluation may not matter for
> register-based calling conventions, but if an implementation uses both,
> it makes sense to use the same order.


Speaking of stacks and registers, machine languages by and large well-defined
evaluation order, so it's laughable for a "higher level assembly" to screw this
up.

There have been some historic oddballs like early RISC processors that blindly
fetched instructions in sequence even though a branch is happening, requiring
the compiler or assembler to fill the delay slots sensibly or stick in NOPs.

It's the same theme theme like unspecified evaluation order in C: unsafe hack
for ease of implementation.
 
Reply With Quote
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-09-2012
On 2012-02-08, Stephen Sprunk <(E-Mail Removed)> wrote:
> On 07-Feb-12 22:49, Robert Wessel wrote:
>> On Tue, 07 Feb 2012 16:51:17 -0600, Stephen Sprunk
>> <(E-Mail Removed)> wrote:
>>> On 07-Feb-12 15:50, Richard Harter wrote:
>>>> Well, no, he isn't saying any such thing. You just made it up. The
>>>> fact that evaluation order in C is left to the compilers has very
>>>> little to do with optimization; it is a historical artifact that came
>>>> from endorsing existing practice when the ANSI standard was put
>>>> together. Existing practice then was that compiler writers could do
>>>> evaluations in whatever they pleased and they did.
>>>
>>> No, they did evaluations in the order that made the most sense (i.e. had
>>> the best performance) for their particular implementation--and
>>> implementations vary.
>>>
>>> For instance, varargs is more straightforward to implement with
>>> right-to-left evaluation of arguments, at least with a stack-based
>>> calling convention. Order of evaluation may not matter for
>>> register-based calling conventions, but if an implementation uses both,
>>> it makes sense to use the same order.

>>
>> Depends on which way your stack grows - with downward growth it's
>> usually easiest to evaluate varargs right-to-left, but for an upwards
>> growing stack left-to-right is usually easier.

>
> How would stack growth direction matter? What matters for varargs is
> that the first argument is on the top of the stack, regardless of which
> way it grows. If you push the arguments from right to left, the first
> argument ends up on top. You _could_ evaluate the arguments from left
> to right, store them in registers or elsewhere in memory, and then push
> from right to left, but why go through that extra effort?


Or you could wake up and realize that the stack can be indexed like an array,
unless you're working with a target language that really has only push and
pop, with no other access to the stack. (Good luck implementing local
variables efficiently, etc).

You can allocate the space for N arguments, and then store valuews into
that stack space in whatever order is convenient, while obeying
the abstract evaluation order (in those situations where it potentially
makes a difference).
 
Reply With Quote
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-09-2012
On 2012-02-08, Kenneth Brody <(E-Mail Removed)> wrote:
> On 2/7/2012 4:50 PM, Richard Harter wrote:
>> On Tue, 07 Feb 2012 15:12:53 -0500, Kenneth Brody
>> <(E-Mail Removed)> wrote:
>>
>>> On 2/7/2012 3:15 AM, Kaz Kylheku wrote:
>>>> On 2012-02-07, Barry Schwarz<(E-Mail Removed)> wrote:
>>>>> On Mon, 6 Feb 2012 02:33:24 -0800 (PST), lujnan<(E-Mail Removed)>
>>>>> wrote:
>>>>>
>>>>>> On Feb 6, 5:45 pm, bert<(E-Mail Removed)> wrote:
>>>>>>> On Monday, February 6, 2012 8:10:00 AM UTC, lujnan wrote:
>>>>>>>> b = a = a++;
>>> [...]
>>>> I don't want diagnostics; I want strict left to right evaluation order
>>>> of operands and subexpressions that complete their side effects before
>>>> yielding a value.
>>>
>>> So, what you are really saying, is you want to eliminate most of C's
>>> optimization abilities, by restricting the order in which the expression
>>> *must* be evaluated, and side effects *must* be completed?

>>
>> Well, no, he isn't saying any such thing. You just made it up. The
>> fact that evaluation order in C is left to the compilers has very
>> little to do with optimization; it is a historical artifact that came
>> from endorsing existing practice when the ANSI standard was put
>> together. Existing practice then was that compiler writers could do
>> evaluations in whatever they pleased and they did.

>
> Well, not having access to the Standards committee, I can only speculate.
> However, if evaluation order were the only thing at stake here, things would
> have been left as "unspecified" rather than "undefined".


Last I looked, the order is in fact unspecified. But then what is undefined
is the multiple uses of the same object.

So for instance f(g(), h()); is not undefined behavior, but unspecified.
We don't know whether g is called first or h, but there are only two
possibilities.

In /practice/ there is no difference.

Unspecified, undefined: it all translates to hidden bugs in code that are not
caught by your regression test suite---even if that code has 100% coverage!

> In the 30+ years of programming in C, I don't believe I've ever had the need
> to write code which depended on side-effects being completed in "the right
> order" within a single statement.


I.e. you have written plenty of code with multiple side effects, but you're
sure that you didn't botch it.

> Whether that's because I know that
> there's no such thing as "the right order", or because I never came across a
> scenario where that might be useful, I cannot say, but I'm leaning towards
> the latter.


I'm not so confident. After 30 years of coding, I'm still making coding
mistakes (even syntax!). I catch these with the help of the compiler, by
reviewing code, by test coverage, or sometimes with the help of other people.

These evaluation order issues fall into a category that is not caught
by tools, and not even by perfect test coverage, because a test case
could simply validate that the expected behavior is happening on the
given target machine and compiler.

I can't justify a belief that the mistakes I make are always, by good luck, in
categories that are caught by the compiler, or by test coverage.

Of course I haven't /knowingly/ stuffed multiple side effects into an
expression such that their order is critical to the correct outcome, for what
that is worth.
 
Reply With Quote
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-09-2012
On 2012-02-08, Edward A. Falk <(E-Mail Removed)> wrote:
> In article <(E-Mail Removed)>,
> Richard Harter <(E-Mail Removed)> wrote:
>>
>>Well, no, he isn't saying any such thing. You just made it up. The
>>fact that evaluation order in C is left to the compilers has very
>>little to do with optimization; it is a historical artifact that came
>>from endorsing existing practice when the ANSI standard was put
>>together.

>
> Perhaps, but it can still have a lot to do with optimization.
>
> Consider:
>
> b = (sqrt(sin(x)*cos(x))) * a;
>
> If the compiler can guess that a is very likely to be zero, and that the
> left side is very likely to be expensive, and has no side effects, then
> it can generate code that evaluates a first, and then decides whether
> or not to evaluate the left side.


Since a is not volatile and those transcendental functions have no side
effects, this evaluation order would be allowed even if the evaluation order
for A * B is that A is evaluated first.

Why don't we change this to:

b = sqrt(sin(x)*cos(x)) && a;

Or how about:

b = sqrt(sin(x)*cos(x)), a;

Both && and , have ordering properties today.

If a is zero, do you believe that the trigonometry has to be evaluated?

> I realize that this is a contrived example, but the bottom line is
> that C was intended to be a *fast* language, and not a *safe* language.


Fast to implement, sure.

> Why nail the compiler's foot to the floor if you don't have to.


So that you don't shoot through yours.
 
Reply With Quote
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-09-2012
On 2012-02-07, Stephen Sprunk <(E-Mail Removed)> wrote:
> On 07-Feb-12 11:21, Kaz Kylheku wrote:
>> On 2012-02-07, James Kuyper <(E-Mail Removed)> wrote:
>>> I can think of two plausible defined
>>> behaviors for a=a++. One is equivalent to a++, so why bother with the
>>> "a="? The other is equivalent to a = a, so why bother writing anything
>>> at all?

>>
>> One particular choice of behavior stands out: the simple, recursive rule:
>>
>> - evaluate each subexpression completely, includiing all of its side effects,
>> before evaluating the parent expression.
>>
>> - if an expression has several subexpressions, evaluate them left to right.

>
> Nice of you to dictate that people using systems that more efficiently
> evaluate sub-expressions from right to left should suffer performance
> degradation of all code, even in the majority of cases where the code is


Proof?

> well-written and therefore the order doesn't actually matter, simply
> because it doesn't suit your sensibilities.


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.

> If you /need/ to know that "foo(bar(), baz());" calls bar() before
> baz(), then just write "tmp=bar(); foo(tmp, baz());". There is no need


Thanks for the clueful suggestion, but, see, what I need to know first is
WHERE this is hiding in a large code base.
 
Reply With Quote
 
John Bode
Guest
Posts: n/a
 
      02-09-2012
On Feb 8, 2:39*pm, Kenneth Brody <(E-Mail Removed)> wrote:
> On 2/7/2012 4:50 PM, Richard Harter wrote:
>
>
>
> > On Tue, 07 Feb 2012 15:12:53 -0500, Kenneth Brody
> > <(E-Mail Removed)> *wrote:


[snip]

> Consider the fact that, in a "well behaved" program, the order of evaluation
> doesn't matter. *Consider, too, that an optimizer may change the order of
> evaluation to something more "efficient" on a given target platform.
>
> 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.
 
Reply With Quote
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-09-2012
On 2012-02-08, Edward A. Falk <(E-Mail Removed)> wrote:
> In article <(E-Mail Removed)>,
> lujnan <(E-Mail Removed)> wrote:
>>Why C Standards Committee does not constrain this case.

>
> Because it's a dumb case. You're not supposed to write that idiom,


You're only not "supposed" to write that only because the behavior isn't
standardized, so this is circular reasoning.

You were also not supposed to write this, prior to 1999:

struct foo x = { .member = 42 };

nor this:

{ int x[var]; }

C programmers obviously sometimes do what they are not supposed to, otherwise
we would not need outfits like the Computer Emergency Response Team (CERT).

You may be a perfect C programmer who never does what isn't supposed
to be done, but that's a sample of one, and highly biased.

I'm not such a programmer. All I can say is that I have never knowingly
broken the rules. I do not buy arguments that "I have never needed that
behavior to be well-defined" or "I have never made such mistakes".

I do not buy the argument that the language should be unsafe, and programming
should be done only by those who can avoid stepping on the mines. On a
project, it's good to have one such savant, but not the whole team.

Why should only programming language users be careful and responsible, but not
language designers?

> and pointless constraints are a bad thing in a system where performance
> is king.


The constraint only affects situations where expressions have interacting side
effects. All other code has the same meaning as without the constraints.
 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      02-09-2012
On 02/08/2012 08:41 PM, John Bode wrote:
> 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?


As a undergrad, I once had a summer job where I was responsible for
writing some hand-optimized assembler to replace two C subroutines that
had been found to be a bottleneck in a scientific calculation. I no
longer remember the concrete details you're asking for, but I do
remember the general strategies I used, and they all depended upon
rearranging the evaluation order.

On the machine I was writing for, there was one component that could
handle either a division or a sqrt() operation in parallel with
multiplications and additions. The main loop required one division,
followed by a sqrt(), followed by another division. Division and sqrt()
both took much longer than either a multiplication or an addition, so
one of the first things I did was rearrange evaluation so the division
started as early as possible, and was immediately followed by the
sqrt(), which was then followed by the second division, and I rearranged
things so that as many multiplications and additions as possible were
done between the start of the division and the completion of the sqrt().

Another key aspect of this machine was a component that could carry out
the register-based equivalent of fma() in three clock cycles, and could
be working on three different fma() operations at the same time, if they
were each started on a different clock cycle. Because the subroutine was
carrying out matrix multiplications, I could easily arrange to keep that
component busy almost full time, but doing so required rearranging the
order of evaluation extensively.

Finally, one of the key things I could do which the compiler was not
able to do, was to treat three different registers as the elements of a
3-component array. This helped to drastically reduce the number of slow
load and store operations, but it meant that a naive implementation of
the subroutine would have required three times as many registers as were
actually available. I dealt with this by rearranging the order of
evaluation so that the each register could be used to represent the
value of several different variables during the course of the
subroutine, by making sure that the periods of time during which the
register represented each variable didn't overlap. IIRC, if there had
been even a single additional register, I could have completely avoided
using RAM for any of the intermediate steps; as it was, I think there
was only one load and one store per pass through the main loop.

It was my first and last project writing in that assembly language. I
documented as accurately as I could precisely how I had designed it, but
I'm sure it was almost completely unmaintainable. My supervisor expected
me to spend the entire summer on it. I completed it in a couple of
weeks, and sped up the subroutine by a factor of 3.5, which disappointed
me - I'd been expecting a factor of 5. But the relevant subroutine was
going to be keeping hundreds of processors busy with a nearly 100% duty
cycle for several years, so that speed-up easily paid for the cost of my
salary. And most of it would have been impossible if I'd not been free
to rearrange the order of evaluation.

All of my rearrangements conformed to the as-if rule, however, so I'm
not sure they're directly relevant to this discussion. The real issue is
whether declaring certain kinds of behavior undefined makes it easier to
optimize code by mechanisms that would violate the as-if rule if the
behavior were defined. I believe this is the case, but I don't have any
anecdotes that demonstrate that fact.
--
James Kuyper
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Dynamic Menu Items is not right aligned with Right to Left documen =?Utf-8?B?QmlzaG95?= ASP .Net 0 12-28-2006 11:39 AM
Right-Click With Mouse and Toolba Buttonsr Don't Work Right Bigfoot It Is Computer Support 0 10-30-2006 06:08 PM
Tool to enable Right click on pages where Right click is disabled tsteinke@gmail.com Computer Support 4 08-28-2005 11:53 PM
Tool to right click image in windows explorer and rotate image right or left 90 degrees siliconpi Digital Photography 2 11-29-2004 12:56 PM
pass the right form input to the right control Tom ASP .Net 0 12-11-2003 03:07 AM



Advertisments