This is impossible to work with. It's like having Undefined Behavior, but always triggered by design.
You can always find some algebraic transformation that loses all the bits of precision, but fn algebraic_add(_: f32, _: f32) -> f32 { 0.0 } should not be allowed to be a valid implementation.
In the sum case you get a different result when temporaries exceed significand of the float. In practice you still don't get non-integer results, and you still should get an exact result for n < 1<<23.
Much as I like tree-reduce (I added it), it's still a guaranteed order, so is deterministic and unlikely to match exactly whatever order a parallel or SIMD reduction will want to use.
RISC-V have two instructions: vfedosum.vs and vfredusum.vs. With vfredosum.vs performing linear addition (so it wouldn't match tree reduce, by definition) and with vfredusum.vs performing some implementation-defined form of tree reduction. There are no limitation, except for “this would be some kind of reduction tree, implementation may decide which one”.
So you if you want some deterministic addition then vfredusum.vs couldn't be used. Permission to use arbitrary permutations is needed, really.
But not permission to add 1e30 and then subtract 1e30 and thus turn everything into 0.0!
Would adding the following note to the docs improve matters?
Note: in degenerate cases, the result may be arbitrarily incorrect, including such behaviors as returning a constant value unrelated to the inputs. However, the general expectation is that given “reasonable” inputs you'll get a "reasonable" approximation of the algebraically correct result, for some value of “reasonable.”
Algebraic operators of the form a.algebraic_*(b) allow the compiler to optimize floating point operations using all the usual algebraic properties of real numbers – despite the fact that those properties do not hold on floating point numbers. This can give a great performance boost since it may unlock vectorization.
The exact set of optimizations is unspecified but typically allows combining operations, rearranging series of operations based on mathematical properties, converting between division and reciprocal multiplication, and disregarding the sign of zero. This means that the results of elementary operations may have undefined precision, and “non-mathematical” values such as NaN, +/-Inf, or -0.0 may behave in unexpected ways, but these operations will never cause undefined behavior.
Because of the unpredictable nature of compiler optimizations, the same inputs may produce different results even within a single program run. Unsafe code must not rely on any property of the return value for soundness. However, implementations will generally do their best to pick a reasonable tradeoff between performance and accuracy of the result.
Should algebraic operations allow non-determinism?
I think the answer fundamentally must be yes to accomplish the stated goal, for one specific reason: wasm's relaxed vector operations. Core wasm v1 is almost[1] fully deterministic, but later extensions introduce controlled forms of nondeterminism in the name of boosted performance where host behavior may reasonably differ. I believe all such extensions require that within a single execution environment the same implementation defined choice of possible output is chosen, but wasm also allows for the host execution environment to be changed arbitrarily and transparently to the running module, meaning that host dependent behavior in a wasm operation is functionally non-deterministic.
The most notable example is of course relaxed-simd.
Core wasm has nondeterministic NaNs very similar to Rust's, although a bit more constrained. ↩︎