Why do most languages not optimise "0 * ...", and are there any languages that do?

Question

I was writing a 2D curve algorithm and had a bit of code that effectively did a summation a la:

for (i=0, end=...; i<end; i++) {
  value += coefficients[i] * expensiveToCalculateValue(i);
}

where the value coefficients[i] was zero for some of of the iteration steps. Since zero times something is still zero (at least under plain arithmetic rules), I figured I could optimise this code significantly by first checking if coefficients[i] is zero, and if so, just continue to the next iteration. Added, sorted, works brilliantly.

But this leaves a question: why is this not done for me? This is not some creative niche version of multiplication, it's plain arithmetic. Virtually all languages short-circuit binary OR and AND operations if an operand is found that will make the result invariant from that point on, so why is the arithmetic multiplication by zero not equally short-circuited?

I tried running this code (modified for synax) in Java, PHP, JavaScript, Perl, Python, C++, and even had a look at what Prolog did, but none of them realise that once they see "zero times ..." they don't have to evaluate the potentially expensive second (or third, fourth, etc) term:

printed = 0;
function veryExpensive() {
  print "oh god this costs so much, x" + (printed++);
  return 0;
}
value = 0 * veryExpensive() * veryExpensive() * veryExpensive()

All of them just end up running veryExpensive() three times.

Now, I understand that you can -if you're that kind of person- write your veryExpensive function to do administrative overhead work based on the fact that you can rely on it being executed despite its result not contributing to the arithmetic expression (if you do that, you're probably abusing a language, but everyone loves sneaky ninja code at some point during their programming life), but you only do that because you know the language happens to funnily not optimize for this case. You wouldn't exactly be hampered in your code expressiveness if the language optimized the arithmetic evaluation for you.

So: is there some historical precedent that has caused a boatload of currently used languages to optimise for "true OR ..." and "false AND ..." but not "zero TIMES ..."? Why do we optimise for binary operations, but not for MUL 0? (And if we're lucky, someone has a fascinating tale to tell on why we now don't short-circuit)

update

Both John Skeet and Nik Bougalis give good arguments on why optimizing this in an extant language will lead to problems, but Nik's answer lines up with the question a bit more, so I marked his answer as the "correct" one. That said, they cover different aspects of the same problem so the real answer is a combination of the two.

Answer 1

All of them just end up running veryExpensive() three times.

And so they should.

but you only do that because you know the language happens to funnily not optimize for this case.

No, it's not a matter of "funnily" not optimizing. It's a matter of optimization not violating the language specifications.

If the language specifies that the operation X * Y first evaluates X then evaluates Y, then multiplies the two values, then it's simply an incorrect optimization to remove the evaluation of Y if the value of X happens to be 0.

There are often operators which do behave like this, of course - in particular (in C-like languages):

• The conditional operator a ? b : c which will only evaluate either b or c
• x || y which will only evaluate y if x is false
• x && y which will only evaluate y if x is true

And C# has the null-coalescing operator x ?? y which only evaluates y if x is null.

Multiplication could be defined like this, but I suspect that:

• In most multiplication operations the branching hit of conditional execution isn't worth it. But you would want the behaviour to be well-defined: either it is short-circuiting or it isn't; it shouldn't (IMO) be undefined.
• It makes the language more complicated to both specify and use. You'd probably want an "unconditional multiply" operation which always evaluated both operands (just like x | y and x & y are non-short-circuiting).

Basically, I don't think it would be worth the additional complexity for all involved.

Answer 2

Having the compiler automatically add a runtime check may or may not make sense. In your particular case perhaps it's true that the check improved performance, but your particular case isn't the end-all, be-all case by which optimizations are judged.

If multiplication is super-expensive and the microprocessor doesn't have internal optimization of multiplications by zero, and the result of a zero multiplication is guaranteed (e.g. 0 * NaN != 0) to be zero then a check might make sense. But that's a lot of and operands, and as you know, you can short-circuit and.

Assume that you have a quasi-random distribution of numbers, and some unknown ratio of zero to non-zero numbers. Depending on the ratio, the run length of zero and non-zero sequences, and the processor's branch prediction algorithms, a check may actually cause trouble (i.e. pipeline stalls).

Do you still think that the compiler should insert such a check on your behalf?