[MLton-user] timing anomoly

Matthew Fluet fluet at tti-c.org
Thu Dec 6 08:11:16 PST 2007

```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
>

```