6

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.

Mike 'Pomax' Kamermans
  • 49,297
  • 16
  • 112
  • 153
  • Because `0 * NaN != 0` – Mysticial Mar 07 '13 at 17:44
  • Also, in C and C++, the order of evaluation of the operands is unspecified. – Daniel Fischer Mar 07 '13 at 17:47
  • 1
    Also, because that would require determining statically that no side effects occur in the RHS, which in general is equivalent to the Halting Problem. – Pieter Geerkens Mar 07 '13 at 17:48
  • @PieterGeerkens No. In `x * y`, there is no associativity (or precedence) involved. Just one operator, two operands, and an unspecified evaluation order. – Daniel Fischer Mar 07 '13 at 17:51
  • 1
    @PieterGeerkens: `x = a * b` - is `a` read before or after `b`? – Nik Bougalis Mar 07 '13 at 17:51
  • @PieterGeerkens Who said we have to prove the RHS is pure, rather than just skipping evaluation any time the LHS is 0, in the same manner the LHS of `a && b` is skipped if `a` is false? –  Mar 07 '13 at 17:53
  • Operand order doesn't particularly matter in a sequence of multiplications, if you encounter a * b * 0 * c * d, the result is still 0, except in the case that Mystical mentions: if the language has a NaN (distinct from inf) then 0 * NaN is indeed not 0, but then it becomes a specification question; is a function that returns a number allowed to return "not a number" (out of scope for this question of course, but an argument not to optimize if your language does allow that). – Mike 'Pomax' Kamermans Mar 07 '13 at 17:57
  • @Daniel: OK. New since I last wrote vanilla C. – Pieter Geerkens Mar 07 '13 at 18:00
  • 1
    @Mike'Pomax'Kamermans: right, but in this instance: `x = a * b * f() * 0 * c` and assuming that we allow the compiler to optimize this away, should the function `f()` be called? If `c` is a `volatile` should it be read anyways? – Nik Bougalis Mar 07 '13 at 18:00
  • @PieterGeerkens I think that was already unspecified in C89. I know it was in C99. – Daniel Fischer Mar 07 '13 at 18:01
  • @PieterGeerkens I don't think it ever was specified. This isn't the kind of guarantee that gets thrown out on a whim. Now, your *implementation* may not have taken advantage of this leeway, but that's not the same thing as it being defined. –  Mar 07 '13 at 18:03
  • @Daniel: The MSDN C spec that I checked a moment ago still says that associativity determines evaluation order. A specific implemenation, of course. – Pieter Geerkens Mar 07 '13 at 18:03
  • I may also be confusing specific compiler guarantees with the language spec. It was a long time ago. – Pieter Geerkens Mar 07 '13 at 18:04
  • 1
    @PieterGeerkens If it's the same MSDN article mentioned in [Operator Precedence vs Order of Evaluation](http://stackoverflow.com/q/5473107/395760), it's wrong. Read that question in its entirety, it's about this issue and the answers are very clear. –  Mar 07 '13 at 18:05
  • 1
    @PieterGeerkens Link? The associativity (and precedence) determine the grouping in the absence of explicit parentheses, so `x * y * z` is equivalent to `(x * y) * z`, but whether `z` is evaluated first, or `x * y` [and in the latter, whether `x` or `y` is evaluated first] is unspecified. – Daniel Fischer Mar 07 '13 at 18:05
  • @NikBougalis: true! So if a language has gone with "unordered resolution" for arithmetic expressions, you basically can't optimize for a multiplication by zero. Although someone might then follow up with "wait, how can they be unordered if the syntax is evaluated left to right" etc. (out of scope for this question of course, and specific to C) – Mike 'Pomax' Kamermans Mar 07 '13 at 18:07
  • "The following table summarizes the precedence and associativity (the order in which the operands are evaluated) of C operators, listing them in order of precedence from highest to lowest.": http://msdn.microsoft.com/en-us/library/2bxt6kc4.aspx – Pieter Geerkens Mar 07 '13 at 18:07
  • @PieterGeerkens [What delnan said](http://stackoverflow.com/questions/15278064/why-do-most-languages-not-optimise-0-and-are-there-any-languages-that-d#comment21555769_15278064). – Daniel Fischer Mar 07 '13 at 18:14
  • @Daniel: Thank you gentlemen; my eyes have been opened. I do not currenlty use vanilla C, but will remember this if I do so in future. – Pieter Geerkens Mar 07 '13 at 18:22

2 Answers2

9

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.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • relating to your last point, languages that have short-circuiting operations generally also have non-short-circuiting versions of essentially the same operator (in C, `&` and `|` to match with `&&` and `||`). – Chris Dodd Mar 07 '13 at 17:54
  • @ChrisDodd: Indeed... although of course those operators have other meanings when applied to non-boolean expressions. – Jon Skeet Mar 07 '13 at 17:56
  • You ignore the possibility of the compiler, be it AOT or JIT, proving the RHS to be free of side effects - which would, of course, allow skipping its evaluation. (Yes, I know how hard and impractical and probably pointless it is.) –  Mar 07 '13 at 17:56
  • True, but this is more an argument about rigid syntax. The choice first has to be made to not say "X * Y evaluates X, and if not zero, then Y". Languages having support for a "NaN" result is a pretty strong argument for not optimizing a multiplication by zero, since that would be plain wrong, rather than simply more complex. – Mike 'Pomax' Kamermans Mar 07 '13 at 18:03
  • @Mike'Pomax'Kamermans: It's pretty rare to have an *integer* `NaN` value. So then you'd potentially have different behaviour for floating point arithmetic and integer arithmetic - it gets hideously messy. – Jon Skeet Mar 07 '13 at 19:49
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?

Nik Bougalis
  • 10,495
  • 1
  • 21
  • 37
  • I didn't, in the first place? This wasn't a "why don't language do this for me", but a "why don't language do this, in general?" question. Supporting a NaN that is treated as a numerical type (rather than an error when encountered) is a pretty solid argument for not optimizing multiplication by zero! – Mike 'Pomax' Kamermans Mar 07 '13 at 18:04
  • My point is that there are *other* issues with optimization multiplication by zero, beyond the support for `NaN`. Again, consider this bit of code, where `c` is `volatile`: `x = 0 * c`. Should `c` be read? Remember, with a `volatile` variable, a read may produce a side-effect and cannot be elided. – Nik Bougalis Mar 07 '13 at 18:06
  • That depends on what the language settles on when it comes to supporting a "volatile" type. Not all languages do. For C, the fact that reading a volatile may produce a side effect is another justification for not optimizing multiplication by zero, so it's certainly another argument why C wisely doesn't optimize in this case. – Mike 'Pomax' Kamermans Mar 07 '13 at 18:14