Benefit of not defining the order of execution

[somenath]

Hi All,

In case of relational and logical operator the order of execution is
not defined except for && and || which is left to right.
What could be the reason for not defining the order of execution?
What benefit it provides ? is it the speed?


Regards,
Somenath

 

[Guest]

In case of relational and logical operator the order of execution is
not defined except for && and || which is left to right.
What could be the reason for not defining the order of execution?
What benefit it provides ? is it the speed?

it generally gives the compiler writer the freedom
to re-arrange operations. This can help with optimsation.

consider
printf ("%d %d", n m);

may be easier to implement if the arguments are evaluated
and pushed onto the stack if m is done before m.

Microsoft used to allow options so that a function
call was either "C style" or "Pascal style". Pascal
style was a bit quicker but couldn't handle varargs

 

[Bartc]

Hi All,

In case of relational and logical operator the order of execution is
not defined except for && and || which is left to right.
What could be the reason for not defining the order of execution?
What benefit it provides ? is it the speed?

I didn't know of such a rule but maybe code like the following was often
used:

char a[...]

if (i<sizeof(a) && a...)...

This would break if the operands of && could be in any order.

 

[James Kuyper]

I didn't know of such a rule ...

There is no such rule. As he said, the order of execution is NOT defined
- the is no explicit statement to that effect. It is implicitly not
defined, by the absence of a specification of what the order should be.
Furthermore, it's clear that this lack of specification is not
accidental, because the rules for sequence points do impose a partial
order, just not a complete order. There's sequence points associated
with || and && (and also ?: and the comma operator).

... but maybe code like the following was often
used:

char a[...]

if (i<sizeof(a) && a...)...

This would break if the operands of && could be in any order.

He wasn't asking why the order of execution is specified for && and ||.
He was asking whe the order of execution is NOT specified for the other
operators.

 

[Richard]

Hi All,

In case of relational and logical operator the order of execution is
not defined except for && and || which is left to right.
What could be the reason for not defining the order of execution?
What benefit it provides ? is it the speed?

I didn't know of such a rule but maybe code like the following was
often used:

char a[...]

if (i<sizeof(a) && a...)...

This would break if the operands of && could be in any order.

Exactly and why there is no such rule.

Possibly some lazy evaluation language might reorder the execution based
on hints of how expensive the evaluations are.

 

[Guest]

I didn't know of such a rule but maybe code like the following was
often used:

char a[...]

if (i<sizeof(a) && a...)...

This would break if the operands of && could be in any order.

note a isn't even evaluated if the first test fails.
So it's got to evaluate the first one first.

if ((i<sizeof(a) & a...)...

is under no such constraint. It must (ok, since neither
appears to have a side effect the as-if rule applies)
evaluate both sides and can do so in any order.

Exactly and why there is no such rule.

Possibly some lazy evaluation language might reorder the execution based
on hints of how expensive the evaluations are.

consider this

if (f() && g())

it must evaluate f and it might not evaluate g.
Some languages (eg Pascal) insist on evaluating
both f and g. The original example would break in Pascal


--
Nick Keighley

"Een schip op het strand is een baken in zee.
[A ship on the beach is a lighthouse to the sea.]"
- Dutch Proverb

 

[Richard]

In case of relational and logical operator the order of execution is
not defined except for && and || which is left to right.
What could be the reason for not defining the order of execution?
What benefit it provides ? is it the speed?

I didn't know of such a rule but maybe code like the following was
often used:

char a[...]

if (i<sizeof(a) && a...)...

This would break if the operands of && could be in any order.

note a isn't even evaluated if the first test fails.
So it's got to evaluate the first one first.

if ((i<sizeof(a) & a...)...

is under no such constraint. It must (ok, since neither
appears to have a side effect the as-if rule applies)
evaluate both sides and can do so in any order.

Exactly and why there is no such rule.

Possibly some lazy evaluation language might reorder the execution based
on hints of how expensive the evaluations are.

consider this

if (f() && g())

it must evaluate f and it might not evaluate g.

Maybe it wasnt clear in the context - I was referring to the ability to
reorder.

Some languages (eg Pascal) insist on evaluating
both f and g. The original example would break in Pascal

I was referring to the potential reordering in other languages and one
reason might be hinted performance impact for thunks in something like
Haskell.

*might*.

Frankly I don't like the idea of reordering for any reason. The
programmer should have control of this powerful left to right ordering.

 

[CBFalconer]

.... snip ...

Microsoft used to allow options so that a function call was
either "C style" or "Pascal style". Pascal style was a bit
quicker but couldn't handle varargs

It can if you add a rule that a final hidden parameter specifies
the count of arguments, or the bytes of arguments.

 

[CBFalconer]

.... snip ...

consider this

if (f() && g())

it must evaluate f and it might not evaluate g.
Some languages (eg Pascal) insist on evaluating
both f and g. The original example would break in Pascal

Pascal doesn't have two forms of AND, so you just have to write it
differently. Try:

IF f() THEN
IF g() THEN BEGIN
(* whatever *) END;

 

[Phil Carmody]

There is no such rule. As he said, the order of execution is NOT
defined - the is no explicit statement to that effect. It is
implicitly not defined

No, it's _explicitly_ "unspecified".

Phil

 

[Guest]

(e-mail address removed) wrote:



Pascal doesn't have two forms of AND, so you just have to write it
differently.  Try:

    IF f() THEN
       IF g() THEN BEGIN
          (* whatever *) END;

I know

 

[James Kuyper]

No, it's _explicitly_ "unspecified".

That statement would have been more helpful with a citation. I went
looking for the explicit specification before posting that message. You
forced me to look again, and this time I found it, in exactly the place
where I had looked earlier, expecting to find it, and somehow managed
not to see it.

6.5p3: "Except as specified later (for the function-call (), &&, ||, ?:,
and comma operators),the order of evaluation of subexpressions and the
order in which side effects take place are both unspecified."

Sorry for the confusion. I'm pretty sure I was awake when I wrote that
message, but perhaps I wasn't. :-}

 

[somenath]

That statement would have been more helpful with a citation. I went
looking for the explicit specification before posting that message. You
forced me to look again, and this time I found it, in exactly the place
where I had looked earlier, expecting to find it, and somehow managed
not to see it.

6.5p3: "Except as specified later (for the function-call (), &&, ||, ?:,
and comma operators),the order of evaluation of subexpressions and the
order in which side effects take place are both unspecified."

But why it is designed like that ? What are the benefits we get out of
it?

 

[James Kuyper]

But why it is designed like that ? What are the benefits we get out of
it?

Because it opens up opportunities for implementations to optimize our
code by rearranging the order of evaluation.

 

[Bartc]

But why it is designed like that ? What are the benefits we get out of
it?

Maybe it was done either way before the language was standardised, and it
was easier for the Standard to continue allowing left/right, right/left, or
arbitrary order of evaluation.

What would be the benefits of restricting the order to say left then right?

 

[Kenny McCormack]

Maybe it was done either way before the language was standardised, and it
was easier for the Standard to continue allowing left/right, right/left, or
arbitrary order of evaluation.

Right. The real reason for this (and, in fact, for many, if not most,
of the decisions made by the standards writers) is to codify existing
practice. I.e., there has to be a pretty good reason (not that there
aren't, in many cases, said very good reasons) to forbid something that
is already common practice.

What would be the benefits of restricting the order to say left then right?

More deterministic code, obviously. Obviouly, all other things being
equal, it is better to reduce the amount of UB in the language. Or, to
put this more positively, it is better if a given piece of code can only
be interpreted one way.

 

[Kaz Kylheku]

What could be the reason for not defining the order of execution?

The reason is myopia: making it easy to write optimizing compilers,
at the cost of introducing risk into the code-base written in the programming
language.

Undefined orders of execution have no place in an imperative programming
language; i.e. one in which the majority of programs that are considered
idiomatic do their job by means of side effects in expressions.

If you were designing a C-like language from scratch today, and left
evaluation order undefined, you should be shot.

What benefit it provides ? is it the speed?

The belief that it provides speed is not a fact.

Even if evaluation order is well-defined, compilers can still rearrange the
evaluation, provided that the result of the computation is correct.

Only in cases where there are side effects does the order have to be
sufficienty constrained so that the effects are done in the proper order.

Note that C does define the order among full expressions, with the concept of
sequencing.

Any compiler that literally obeys sequence points cannot be called optimizing
by modern standards. A quality compiler must reorder computation across
sequence points! So if you write

x = a + b;
y = a + z;

even though there is a sequence point between these expressions,
they can be reordered, because they are independent. Even
these could be significantly rearranged:

a = i++;
b = i++;

The generated code could do something like

a = i;
b = i + 1;
i += 2;

Sequencing doesn't mean that the computation must literally take place as
written in every detail; it's an abstract concept tied to the ``as if'' rule.

Even if it can be shown than unspecified order of evaluation provides an
undeniable performance benefit, there is no reason why that order has to be
unspecified in every part of the program, in every expression in every function
in every source file.

If unspecified evaluation order is indeed an optimization tool, then it should
be recognized that it's a dangerous optimization tool, and a way should be
provided for the programmer to choose the regions of the program where the
order is unspecified. Suppose you had a reorder operator:

reorder /expression/

Everything under the reorder operator is subject to unspecified evaluation
order, other than sequencing operators. The return value and type of the
reorder operator are those of the expression.

 

[user923005]

Maybe it was done either way before the language was standardised, and it
was easier for the Standard to continue allowing left/right, right/left, or
arbitrary order of evaluation.

Consider things like common subexpression elimination.

Consider things like:
y = a * (2*b + c) + a * (d * e - b) + a * f;
rewritten by the compiler as:
y = a * (b + c + d * e + f);

What would be the benefits of restricting the order to say left then right?

Determinism.

 

[Stephen Sprunk]

In case of relational and logical operator the order of execution is
not defined except for && and || which is left to right.
What could be the reason for not defining the order of execution?
What benefit it provides ? is it the speed?

Not specifying the order allows implementations to do whatever is most
efficient in their circumstances; ABC might be the fastest on one
system, while CBA is the fastest on another, and doing all three in
parallel might be fastest on a third. Requiring a particular order
would provide no gain at best and a loss of performance in all other
cases -- all cost, no benefit. If the order actually matters, you can
modify the code slightly to insert sequence points as desired to force a
particular ordering. And, of course, there is the "as if" rule which
mucks everything up anyways.

Also, remember that ANSI's job was primarily to document existing
practice, not define a perfect language. Where existing implementations
didn't all agree on a particular behavior, they usually left the meaning
undefined or unspecified rather than break some of them.

S

 

[Richard Tobin]

What could be the reason for not defining the order of execution?
What benefit it provides ? is it the speed?

As others have said, it does indeed often allow compilers to produce
faster code. On reason for this is that many computers (e.g. x86)
have only a small number of registers, and different orders of
evaluation may need different numbers of registers. When there
aren't enough registers, temporary values may have to be stored
in memory, which is much slower.

For example, "a * 2 + b * c" could be compiled to something like

// multiply a by 2
LOAD R1, a
MUL R1, 2
// multiply b by c
LOAD R2, b
LOAD R3, c
MUL R2, R3
// add the terms
ADD R1, R2

This requires 3 registers. But if we evaluate b*c first, we can
do


// multiply b by c
LOAD R2, b
LOAD R3, c
MUL R2, R3
// multiply a by 2
LOAD R3, a
MUL R3, 2
// add the terms
ADD R3, R2

which only requires 2 registers.

-- Richard