Coercing Floating-Point to Be Deterministic in .Net

Coercing floating-point to be deterministic in .NET?

The 8087 Floating Point Unit chip design was Intel's billion dollar mistake. The idea looks good on paper, give it an 8 register stack that stores values in extended precision, 80 bits. So that you can write calculations whose intermediate values are less likely to lose significant digits.

The beast is however impossible to optimize for. Storing a value from the FPU stack back to memory is expensive. So keeping them inside the FPU is a strong optimization goal. Inevitable, having only 8 registers is going to require a write-back if the calculation is deep enough. It is also implemented as a stack, not freely addressable registers so that requires gymnastics as well that may produce a write-back. Inevitably a write back will truncate the value from 80-bits back to 64-bits, losing precision.

So consequences are that non-optimized code does not produce the same result as optimized code. And small changes to the calculation can have big effects on the result when an intermediate value ends up needing to be written back. The /fp:strict option is a hack around that, it forces the code generator to emit a write-back to keep the values consistent, but with the inevitable and considerable loss of perf.

This is a complete rock and a hard place. For the x86 jitter they just didn't try to address the problem.

Intel didn't make the same mistake when they designed the SSE instruction set. The XMM registers are freely addressable and don't store extra bits. If you want consistent results then compiling with the AnyCPU target, and a 64-bit operating system, is the quick solution. The x64 jitter uses SSE instead of FPU instructions for floating point math. Albeit that this added a third way that a calculation can produce a different result. If the calculation is wrong because it loses too many significant digits then it will be consistently wrong. Which is a bit of a bromide, really, but typically only as far as a programmer looks.

Deterministic floating point and .NET

I'm not sure of the exact answer for your question but you could use C++ and do all your float work in a c++ dll and then return the result to .Net through an interopt.

Floating point determinism for gamedev in .NET Core

So, if CoreCLR uses SSE FP instructions on x86-64, does that mean that it doesn't suffer from the truncation issues, and/or any other FP-related non-determinism?

If you stay on x86-64 and you use the exact same version of CoreCLR everywhere, it should be deterministic.

If the runtime still uses x87 instructions with unreliable results, would it make sense to use a software float implementation [...] I've prototyped this and it seems to be work, but is it unnecessary?

It could be a solution to workaround the JIT issue, but you will likely have to develop a Roslyn analyzer to make sure that you are not using floating point operations without going through these... or to write an IL rewriter that would perform this for you (but that would make your .NET assemblies arch dependent... which could be acceptable depending on your requirements)

If we can just use normal floating point operations, is there anything we should avoid, like trigonometric functions?

As far as I know, CoreCLR is redirecting math functions to the compiler libc, so as long as you stay on the same version, same platform, it should be fine.

Finally, if everything is OK so far how would this work when different clients use different operating systems or even different CPU architectures? Do modern ARM CPUs suffer from the 80-bit truncation issue, or would the same code run identically to x86 (if we exclude trickier stuff like trigonometry), assuming the implementation has no bugs?

You can have some issues not related to extra precision. For example, for ARMv7, subnormal floats are flushed to zero while ARMv8 on aarch64 will keep them.

So assuming that you are staying on ARMv8, I don't know well if the JIT CoreCLR for ARMv8 is behaving in that regard; you should probably ask on GitHub directly. There is still also the behavior of the libc that would likely break deterministic results.

We are working exactly at solving this at Unity on our "burst" compiler to translate .NET IL to native code. We are using LLVM codegen across all machines, disabling a few optimizations that could break determinism (so here, overall we can try to guarantee the behavior of the compiler across the platforms), and we are also using the SLEEF library to provide deterministic calculation of mathematical functions (see for example https://github.com/shibatch/sleef/issues/187)… so it is possible to do it.

In your position, I would probably try to investigate if CoreCLR is really deterministic for plain floating point operations between x64 and ARMv8… And if it looks okay, you could call these SLEEF functions instead of System.Math and it could work out of the box, or propose CoreCLR to switch from libc to SLEEF.

How to convert IEEE754 float to fixed-point in deterministic way?

While @StephenCanon's answer might be right about this particular case being fully deterministic, I've decided to stay on the safer side, and still do the conversion manually. This is the code I have ended up with (thanks to @CodesInChaos for pointers on how to do this):

public static Fixed FromFloatSafe(float f) {
    // Extract float bits
    uint fb = BitConverter.ToUInt32(BitConverter.GetBytes(f), 0);
    uint sign = (uint)((int)fb >> 31);
    uint exponent = (fb >> 23) & 0xFF;
    uint mantissa = (fb & 0x007FFFFF);

    // Check for Infinity, SNaN, QNaN
    if (exponent == 255) {
        throw new ArgumentException();
    // Add mantissa's assumed leading 1
    } else if (exponent != 0) {
        mantissa |= 0x800000;
    }

    // Mantissa with adjusted sign
    int raw = (int)((mantissa ^ sign) - sign);
    // Required float's radix point shift to convert to fixed point
    int shift = (int)exponent - 127 - FRACTION_SHIFT + 1;

    // Do the shifting and check for overflows
    if (shift > 30) {
        throw new OverflowException();
    } else if (shift > 0) {
        long ul = (long)raw << shift;
        if (ul > int.MaxValue) {
            throw new OverflowException();
        }
        if (ul < int.MinValue) {
            throw new OverflowException();
        }
        raw = (int)ul;
    } else {
        raw = raw >> -shift;
    }

    return Fixed.FromRaw(raw);
}

Does F# suffer from same C# caveats on non-deterministic floating point calculation?

In short; C# and F# shares the same run-time and therefore does floating point number computations in the same way so you will see the same behavior in F# as in C# when it comes to floating point number computations.

The issue of 0.1 + 0.2 != 0.3 spans most languages as it comes from the IEEE standard of binary floating pointing numbers, where double is an example. In a binary floating point number 0.1, 0.2 and so on can't be exactly represented. This is one the reason some languages support hex float literals like 0x1.2p3 which can be exactly represented as a binary floating point number (0x1.2p3 is equal to 9 btw in a decimal number system).

Lots of software that relies on double internally like Microsoft Excel and Google Sheet employ various cheats to make the numbers look nice but often isn't numerically sound (I am no expert I just read a bit of Kahan).

In .NET and many other languages there is often a decimal data type that is a decimal floating point numbers ensuring 0.1 + 0.2 = 0.3 is true. However, it doesn't guarantee that 1/3 + 1/3 = 2/3 as 1/3 can't be represented exactly in a decimal number system. As there is no hardware for support for decimal they tend to be slower, in addition the .NET decimal is not IEEE compliant which may or may not be a problem.

If you have fractions and you have lots of clock cycles available you can implement a "big rational" using BigInteger in F#. However, the fractions quickly grows very large and it can't represents 12th roots as mentioned in the comment as outcomes of roots arecommonly irrational (ie can't be represented as rational numbers).

I suppose you could preserve the whole computation symbolically and try to preserve exact values for as long as possible and then very carefully compute a final number. Probably quite hard to do correct and most likely very slow.

I've read a bit of Kahan (he co-designed 8087 and the IEEE standard for floating point numbers) and according to one of the papers I read a pragmatic approach to detect rounding errors due to floating point number is to compute thrice.

One time with normal rounding rules, then with always round down and finally with always round up. If the numbers are reasonably close at the end the computation is likely sound.

According to Kahan cute ideas like "coffins" (for each floating point operation produce a range instead of single value giving the min/max value) just don't work as they are overly pessimistic and you end up with ranges that are infintely large. That certainly match my experience from the C++ boost library that does this and it's also very slow.

So when I worked with ERP software in the past I have from what I read of Kahan recommended that we should use decimals to eliminate "stupid" errors from like 0.1 + 0.2 != 0.3 but realize that there are still other sources for errors but eliminating them is beyond us in compute, storage and competence level.

Hope this helps

PS. This is a complex topic, I once had a regression error when I changed the framework at some point. I dug into it and I found the error came from that in the old framework the jitter used the old-style x86 FPU instructions and in the new jitter it relied on the SSE/AVX instructions. There are many benefits by switching to SSE/AVX but one thing that was lost that the old style FPU instructions internally used 80 bits floats and only when the floating point numbers left the FPU they were rounded to 64 bits while SSE/AVX uses 64 bits internally so that meant the results differed between frameworks.

---

Related Topics