Splitting off a small tangential discussion that started in the TWiR quotes of the week thread.
writing deterministic floating point math is possible, but i agree that its very, very difficult without some kind of static analysis
(which most (all?) languages lack, but forking std and removing all non-deterministic floating point functions would technically be a (horrible) way to partially achieve it, and once you have a way to partially detect non-determinism you'll realize that you need to patch half your dependencies)
the worst part is the fact that a + (b + c) != (a + b) + c, and I can't think of any reasonable way to prove the absence of that.
forking std and removing all non-deterministic floating point functions would technically be a (horrible) way to partially achieve it,
You don’t need to fork std; instead, don’t use it. Under #![no_std], the floating-point methods that call out to system libraries are not present. (That said, we could imagine a future where that’s no longer true and there's sin(), etc. in core.)
the worst part is the fact that a + (b + c) != (a + b) + c, and I can't think of any reasonable way to prove the absence of that.
That’s doesn’t interfere with determinism: if you run the same operations, you still get the same results. I think the thing that does what you want would not actually be static analysis for nondeterminism but static analysis for using floats wrong. Which is a harder problem.
You don’t need to fork
std; instead, don’t use it. Under#![no_std]
that's also a option, but getting rid of std gets rid of a lot of things you and/or your dependencies depend (e.g. Vec, fs) on that are unrelated to floating point math
That’s doesn’t interfere with determinism
it does if your dependencies split work between different threads and then sum up the result, sum a hash map, or do anything else involving randomness that assumes that you can do addition in any order and get the same result.
The other part of this is that the traditional numerical analysis approach to floating point is not to guarantee determinism, but to provide a guaranteed relationship between the error on the input values, and the error on the output values.
This in part is because historically, you weren't trying to synchronize across a network, but instead had readings from the real world (with associated error bounds) and wanted to either compute something that you can't measure, or predict the future; in both cases, you're a lot more bothered that the output of an algorithm stays within a reasonable error bound given the accuracy of measurement than that it's entirely deterministic - especially since the "same" real world measurement might be 150.1 one time, and 150.2 another thanks to the errors in your sensors.
This is an example where summation algorithms come into play - you get to make engineering compromises when you choose one. Naïve summation has awful error bounds, but is fast on hardware; precise summation is slow, but is guaranteed to have error no more than the machine representation, and there's a variety of options in between those two.
At core, though, the problem with floating point is that people treat it as "computer representation of the real numbers", but it's not - it's a finite approximation of the real numbers with useful engineering properties, and you have to do the design work to benefit from those properties.
This has been possible for decades (some existence proofs), and is the only reasonable path for certain genres. Plus having replays is a great game feature in addition to a wonderful debugging tool.
Yes, you need to segregate your gameplay logic from your animation-and-rendering-and-effects logic (since the latter doesn't need determinism), run at a consistent timestep instead of at machine framerate, etc but those are good things that you should be doing anyway.
And sure, sin/acos tend to be non-portable, but as the classic avoiding trigonometry article elaborates, they're massively overused anyway. (Plus in games you generally don't need an accurate one anyway, so making your own one that's kinda bad but obviously consistent is fine.)
And sure,
sin/acostend to be non-portable, but as the classic avoiding trigonometry article elaborates, they're massively overused anyway.
you can also use deterministic software implementations, which can be surprisingly fast.
Looking at that article and the comments under it one would conclude floating point determinism is not possible. At least not without ensuring one has the same compiler, debugs settings, hardware architecture etc. Or accepts a performance drop.
Back in the 1980's an project manager of mine told a new team member:
If you think you need floating point to solve the problem then you don't understand the problem.
Years later I arrived at a corollary to that:
If you do need floating point to solve the problem then you will have a problem you won't understand.
IEEE754 has a whole section on "Reproducible floating-point results", FWIW. The core of the rules is that your basic operations (add, subtract, multiply, divide, square root, fused multiply-add, comparisons, conversions to/from integers) are fully deterministic in an IEEE754 compliant world, and a language that purports to be IEEE754-compliant shall support reproducible results from those basic operations, albeit it is permitted to require you to tell it to disable non-reproducible optimizations.
It's the recommended operations (powers and logs, trig, reciprocal square root etc) that are not guaranteed to be reproducible, and there are optimizations possible (such as turning a * b + c into FMA) that are supposed to need a programmer's permission, because they can change the results - IEEE754 says that languages are required to at the very least allow you to opt-out of those optimizations, while still permitting optimizations like 1.0 * a going to a (which can't change the results).
However, I'm now firmly at a point where I'd change your saying and corollary to "if you're using FP, and you haven't read and understood IEEE754, you're going to have problems you can't explain".
Just to be clear for other people reading this thread: in Rust, “reproducible” is the default, and only, behavior Rust supports for the basic operations.[1] You can opt in to non-reproducible optimizations using the “algebraic” operator methods, but you will never get those without asking for them at each call site.
The notorious x86-32 80-bit floats are considered the platform being non-compliant. ↩︎
I also appreciate that Rust documents the precision guarantees on other functions - for example, div_euclid (which is not a basic operation) is documented as "the rounded infinite-precision result" (which is therefore reproducible, following IEEE754's lead), but non-reproducible functions are documented as "Unspecified precision".
Whoever documented Rust's floating point support exceeded expectations - if you haven't read IEEE754, it's still fairly obvious what the guarantees are (although you're in a bad place because you're almost certain to make assumptions that aren't quite true), and if you have read the standard, the documentation makes it completely clear how Rust complies with IEE754, and therefore where the sharp edges are.
I'm that vein, WGSL (the shader language for WebGPU / wgpu) is surprisingly nice in that it documents precise required (and not required!) behavior of it's floating points, especially where it differs from IEEE-754, up to minimum ULPs for all the functions
As long as we continue to rely on LLVM as a backend, this will live in the realm of theoretically possible, but practically out-of-reach.
I'm thinking of things like floats behaving different when eagerly evaluated at compile time for example, where there are still open miscompilation bugs to this day. Avoiding const contexts is not enough here, and neither is using black_box.
There is another aspect I don't see brought up very often, which is that LLVM is designed with C++ in mind where floating point behavior is notably not deterministic (e.g. see floating point contractions, or the messy history of x86 and softfloat). I don't know any open bugs at the top of my head, but it would not surprise me given that a good portion of Rust miscompilations are from LLVM assuming C++ semantics (e.g. see infinite side-effect-free loops)
That dooms an awful lot of FP work to non-determinism. Does it not?
To be fair I don't think there was an IEEE 754 at the time my project manager said what I quoted. It was not released until 1985. Even today I suspect pretty few working programmers have read it. My corollary was only a response to seeing so many people asking question like "Why is 0.1 + 0.1 + 0.1 == 0.3 false? all over the place for years, clearly not understanding what they were dealing with.
All floating-point ops are reducible to binary operations after all, so even a library could expose sf32,sf64 with all of the functions.
Then it's a matter of optimizing sf32::add to CPU fp addition instruction on targets where it's guaranteed to have the same behavior, etc.
(Notably, the lib could do it itself, rather than leaving it for LLVM!)
In my personal experience, no. Most of the FP code I deal with just uses the basic operations (thankfully), which means that applying numerical analysis to it to get error bounds on the output given known bounds on the input error is tractable, and if you can prove that given inputs with error not more than machine precision, you have an output of not more than machine precision, that code is fully deterministic on IEE754 platforms.
I see more problems in fixed-point arithmetic, where it's not at all uncommon for code authors to simply neglect to consider what happens when an intermediate calculation underflows (or more rarely, overflows) - instead, they assume that underflow is harmless (so they assume that (a + b / c) * d == (a * d) + (b * d / c)) == (a * d) + (b * (d / c)), which is not always true, since the multiplication and division hide a scaling factor adjustment).
It's also tractable to reimplement the recommended operations purely in terms of the basic operations yourself (indeed, this is common in IEEE754 libraries, since very few modern processors offer trigonometric functions at all). If you absolutely need determinism, and are willing to sacrifice performance to get it, you can implement everything you care about in terms of basic operations.
And yes, pre IEEE754 was a minefield; quite a few of the things people dislike about IEEE754 (denormalized numbers, for example) exist because they make the numerical analysis easier to get right - but they were rare in pre-IEEE754 FP, where a lot of vendors prioritised "fast" over "useful" - often not even bothering to fully specify the precision of what IEEE754 calls basic operations in the case where the exponents don't match.
It's also tractable to reimplement the recommended operations purely in terms of the basic operations
you can also use non-basic operations that are explicitly documented as being deterministic and cast the float to an integer to get (very confusing) bitwise operations, which are also deterministic (as long as NaN bit patterns don't affect the bits of non-NaN floats).
An interesting project for multiplayer games would be to dynamically negotiate which implementation of sin,atan2,etc to use (if the players are on different platforms that is).
that would certainly be interesting,
it would be a good idea to benchmark the hardware and software implementations first to determine whether a non-deterministic hardware implementation has any advantages over a software implementation for your game.
for example Bhāskara I's formula can approximate cosine in about 3 multiplications, 1 addition, 1 subtraction, and 1 division (not counting π² as a multiplication because you can compute that ahead of time),
but isn't very precise precise (~2% max error).
(you can also use Bhāskara I for sine, but that has more operations, so it'd likely be faster to just shift (which would only be 1 addition/subtraction) the cosine function to implement sine)
Note that most hardware (x87 on 32-bit x86 is the most modern FPU where this isn't true) doesn't bother providing most of the non-reproducible operations; you get the IEEE754 basic operations (which are fully reproducible across systems), and maybe reciprocal square root, and that's about it (until you do things like turning off denormal support for speed).
The "non-deterministic" implementations of things like cos, exp and other recommended IEEE754 functions in the stdlib are themselves software implementations, either supplied by LLVM or by your platform's libm equivalent.
As a result, if you start from a good implementation of (say) cosine in terms of IEEE754 basic operations, you're likely to end up with something that's as fast as the Rust-supplied version, but with the reproducibility that you want.