Defined argument evaluation order leads to sub-optimal code?

Question

It is a known fact that argument evaluation order in c and c++ are not defined: for example: foo(a(),b()) In the above call it is up to the implementation of the compiler to decide which order of evaluation to pick and hence forth which function to execute first. Lately one of my friends asked why is the order of evaluation unspecified in C or C++. When I googled it, I came to know that specifying an evaluation order would lead to sub-optimal code generation. But how is it so? Why would a defined order of evaluation of arguments lead to sub-optimal code? And when I referred to Java's argument evaluation order. I found the following in the spec.

15.7.4. Argument Lists are Evaluated Left-to-Right

In a method or constructor invocation or class instance creation expression, argument expressions may appear within the parentheses, separated by commas. Each argument expression appears to be fully evaluated before any part of any argument expression to its right. If evaluation of an argument expression completes abruptly, no part of any argument expression to its right appears to have been evaluated?

That being the case, Java has a defined argument evaluation order, but saying C or C++ compilers would yield sub-optimal code if such a behavior is specified seems a little odd. Can you throw some light on this?

Answer 1

Not for the function evaluations as of for your example, but for simple expressions the two expression can even be executed in parallel. Modern architectures are pipelined and it can be more efficient to feed two pipelines (almost) simultaneously such that the operations that have to be performed overlap.

Also you seem to be under the impression that there are only two expressions to evaluate for the arguments, but there are four: a, b, a() and b(). The partial order for the function call in total is from left to right

    a -- a()
             \
         f --- f(a(), b())
             /
    b -- b()

As you can see from the picture there is a lot of potential parallelism and modern compilers can gain something by not having a prescribed evaluation order.

Edit: In view of the discussion some additional details. If a() and b() are function calls there is a guarantee by the standard that these function calls will not interleave, even if the functions are inlined. So then the picture above should have an addition constraint that a() and b() must be somehow ordered. (I don't know how to put that in the picture.)

If on the other hand they are other expression, e.g macro evaluations, these expressions may (and probably will) be interleaved if there is a gain.

Answer 2

I think we overanalyse it. The true answer is probably that in olden days before the C standard when K&R was the de facto standard, nobody bothered to specify which order to evaluate the arguments in and different compiler implementations went in different ways.

The logical way from a human point of view is to evaluate the arguments from left to right (as Java does it). The easy way, from the compiler's point of view is to do the argument evaluation from right to left. This is so that, once an argument has been evaluated, it doesn't need to be saved anywhere, it can be pushed on the stack ready for the call. Most C implementations that use the stack for arguments need to push them in reverse order. This is because K&R C has no way for a compiler to figure out how many arguments a function takes if it has not been defined in the same source file and programmers used to take advantage of that to provide a primitive form of variadic functions.

So the standard writers were faced with a choice of doing it the "right" way (left to right) and possibly breaking a lot of code or doing it the way most of the extant compilers did it and possibly breaking some other code or sticking with the status quo and letting the compiler designers choose what to do.

That's my opinion anyway, not based on any facts.

Answer 3

It's partially historical: on processors with few registers, for example, one traditional (and simple) optimization technique is to evaluate the subexpression which needs the most registers first. If one subexpression requires 5 registers, and the other 4, for example, you can save the results of the one requiring 5 in the register not needed by the one requiring 4.

This is probably less relevant that usually thought. The compiler can reorder (even in Java) if the expressions have no side effects, or the reordering doesn't change the observable behavior of the program. Modern compilers are able to determing this far better than compilers twenty or more years ago (when the C++ rule was formulated). And presumably, when they aren't able to determine this, you're doing enough in each expression that the extra spill to memory doesn't matter.

At least, that's my gut feeling. I've been told by at least one person who actually works on optimizers that it would make a significant difference, so I won't say that I'm sure about it.

EDIT:

Just to add some comments with regards to the Java model. When Java was being designed, it was designed as an interpreted langauge. Extreme performance wasn't an issue; the goal was extreme safety, and reproduceability. Thus, it specifies many things very precisely, so that any program which compiles will have exactly the same behavior regardless of the platform. There was supposed to be no undefined behavior, no implementation defined behavior, and no unspecified behavior. Regardless of cost (but with the belief that this could be done at reasonable cost on any of the most widespread machines). One initial design goals of C (and indirectly C++) was that unnecessary extra runtime cost should be minimum, that consistency between platforms wasn't a goal (since at the times, even common platforms varied greatly), and that safety, while a concern, wasn't primordial. While the attitudes have evolved some, there is still a goal to be able to support, efficiently, any machine which might be out there. Without requiring the newest, most complex compiler technologies. And different goals naturally lead to different solutions.

Answer 4

Java posits a stack-based virtual machine, in which there is no advantage to reordering operands. As per James Kanze's answer, C and most fully compiled languages posit a register architecture, in which register 'spills' to memory are expensive and are greatly to be avoided, so it can be better to reorder the operands, indeed to do all kinds of things, to maximize register usage and minimize spillage.