[MLton-user] timing anomoly

[Matthew Fluet]

Good point.  And, technically, the SML and C programs are doing ever so 
slightly different things.  The SML program has
   (...((((store + (-x1)*x4) + x2*x5) + (-x3)*x5) + (-x2)*x6) + ...)
while the C program has
   store += (...((((-x1)*x4 + x2*x5) + (-x3)*x5) + (-x2)*x6) + ...)
equivalent to
   store = store + (...((((-x1)*x4 + x2*x5) + (-x3)*x5) + (-x2)*x6) + ...)
The order of evaluation is different in the two program.  So, GCC does 
have a little more freedom; I was incorrect to claim that GCC needed to 
reassociate the computation to do the constant folding.  And, given that 
x1 = x2 = ... = x = 4.0, all the FP arithmetic works out the same, 
regardless of the rounding mode.  So, indeed, GCC is justified to constant 
fold in this case.

Now, if x1 = x2 = ... = x = 1.0 / 3.0, then the rounding mode does affect 
the FP arithmetic, but GCC still happily constant folds the expression.

If you rewrite the C program to have
   store = (...((((store + (-x1)*x4) + x2*x5) + (-x3)*x5) + (-x2)*x6) + ...)
then GCC correctly does not reassociate the arithmetic, but does constant 
fold the x? terms.  (GCC also seems to transform (-x)*y to -(x*y) and
x+(-y) to x-y (which I believe are universally valid IEEE identities), so 
that the assembly has a sequence of subs and adds of the same constant.)
However, again, GCC happily constant folds the x? term, even when the 
result depends on the rounding mode.

So, both C/GCC and SML/MLton honor the parenthesis (i.e., associativity) 
of floating-point calculations.  GCC performs constant folding of FP 
computations, even when the result would depend on the rounding mode. 
GCC also performs common-subexpression-elimination (and presumably 
loop-invariant code motion and/or partial-redundancy-elimination) of FP 
computations across calls to unknown functions (which might change the 
rounding mode).  MLton preforms no constant folding of FP computations and 
no common-subexpression-elimination (or loop-invariant or PRE) of FP 
computations.  MLton could be improved to support CSE of FP computations 
when the rounding mode can't change between the expressions.  MLton could 
also be improved to constant fold expressions whose answers don't depend 
on the rounding mode.

On Thu, 6 Dec 2007, Sean McLaughlin wrote:
>> From Goldberg: What every computer scientist should know about
> floating point arithmetic:
>
> "The importance of preserving parentheses cannot be
> overemphasized. The algorithms presented in theorems 3, 4 and 6 all depend
> on it. For example, in Theorem 6, the formula xh = mx - (mx - x) would reduce
> to xh = x if it weren't for parentheses, thereby destroying the entire
> algorithm.
> A language definition that does not require parentheses to be honored is
> useless for floating-point calculations."
>
>
> On Dec 5, 2007 4:55 PM, Florian Weimer <fw at deneb.enyo.de> wrote:
>> * Matthew Fluet:
>>
>>> FP arithemetic is not associative, so it is not really justified (or
>>> at least numerically accurate) to reassociate the computation for
>>> constant folding.  I could see constant folding the idividual
>>> negations and multiplications, but the additions really ought not be.
>>
>> In this case, the folding GCC performs increases accuracy, which is
>> permitted according to the floating point model implement by GCC (and,
>> presumably, what's described in the relevant appendix of C99).  Without
>> -ffast-math, GCC is supposed to not apply any transformation which
>> reduces accuracy.
>>
>
> _______________________________________________
> MLton-user mailing list
> MLton-user at mlton.org
> http://mlton.org/mailman/listinfo/mlton-user
>