13 ms·
High Performance Correctly Rounded Math Libraries for 32-Bit Floating Point
- camgunz 5y agoThere are ~30 year old legends in the client/server gamedev community about floating point differing across platforms, but I assumed they were ironed out by now. Wild to find out they haven't been.
- dleslie 5y agoDecades ago we were deeply concerned with syncronized simulations; the dominant replication method was lock-step input replication, or similar, and that made it very important that everyone's simulation was identical or bad things would happen. Nowadays that's not an issue, as there's a slew of different ways of overcoming that and allowing clients to operate asynchronously; sometimes widely asynchronous.
- _dwt 5y agoAny good resources (or even search term hints) you could recommend on the more modern/async approaches? I’d love to read about them.
- lodi 5y agohttps://gafferongames.com/post/state_synchronization/ https://gafferongames.com/post/state_synchronization/ Also search for "game networking" + the following: - state replication - dead reckoning - client side prediction - networked physics
- camgunz 5y agoIt's still super important for clientside prediction. If the client and server are getting different math results that's a desync. Now that can matter not at all or a lot depending on the game, but regardless it's still fundamental.
- thxg 5y agoNowadays, all major platforms follow IEEE754, which specifies exactly the results of elementary operations (+, -, x, /). You must get bit-for-bit reproducible results across different runs, compiles, libraries, OSes and hardware. Any difference is a bug. However: 1. As the paper emphasizes, math library functions (sin, cos, log, etc.) are not covered by that standardization, at least not mandatorily and not in practice. This is the problem that the paper tackles. 2. In the bad old days of the x87, the FPU carried out computations on eight 80-bit registers. The problem is that whenever those registers spilled out to the stack, precision was truncated down to whatever type the language actually meant (64-bit double or 32-bit float). Because the register-spilling decision is mostly taken by the compiler, it was largely unpredictable. This resulted in code that was not reproducible, even across compiles! Since x87 was deprecated in favor of SSE/AVX, the precision of operations is always that of the type used in the code. Lower than 80-bits but much better in practice because of consistency and reproducibility. 3. The bad old days are making a comeback with FMA instructions (fused multiply-add). This is a single operation (a x b + c) and so it is correctly rounded to the closest representable number. This number can be different from ((a x b) + c) in which two roundings occur. If we give the compiler freedom to decide whether or not to fuse such expressions, we will again see non-reproducibility across compiles. Unfortunately, gcc and icc both do that by default at -O3 (see -ffast-math, and more specifically -fexcess-precision). Specifying a proper language standard (for example -std=c99, -std=c++14, etc.) restores sane behavior.
- adgjlsfhk1 5y agoOn the one hand, the ambiguity of FMA is kind of annoying, but on the other, FMA is a godsend for writing accurate arithmatic. One reason for this, is that the error of `ab` is `fma(a, b, -ab)` which makes compensated algorithms much faster to write. Secondly, polynomial evaluations using horner's method converge to .5 ULP (units in last place) with FMA, but to 1.5 ULP without. This is incredibly useful since polynomial approximations are at the heart of pretty much everything else. I think Julia takes an interesting approach here of never reordering floating point computations unless you explecitly give permission using @fastmath (which acts locally instead of globally like a --fast-math in C/C++). This makes it much easier to use ieee specific tricks and be confident that the compiler won't mess with you, while still making it easy to tell the compiler to do what it wants.
- GeorgeTirebiter 5y agoI've read that, if one is going to use floats, then one should eschew 32-bit floats, and go with 64-bit floats. 80-bit floats seem only useful for very special applications. I converted a satellite orbital prediction program that used doubles (64-bit floats) to use long doubles (80-bit floats) but only saw a difference in the 11th decimal place, with lots of sin/cos/atan/sqrt involved in the calculations. With 32-bit floats it was a joke: the accumulated error made the 'predictions' useless. The basic problem with 32-bit is you have to be quite careful with your arithmetic so you don't lose significance. It's almost as bad as using Q-notation. https://en.wikipedia.org/wiki/Q_(number_format) https://en.wikipedia.org/wiki/Q_(number_format)
- dynm 5y agoThe main use for 80-bit floats is probably to confirm that when you switch from 64-bit to 80-bit, nothing changes. This is a very important use, though!
- dragontamer 5y agoErrors grow exponentially in most floating-point operations. The exception is cancellation error, which can suddenly cause the error rate to spike dramatically. But if you sort your numbers before adding/subtracting, you can often negate this overwhelming cancellation error. The exponential growth of other floating point errors is almost unstoppable however. The only real way to stop it is to design an algorithm that operates with fewer steps. --------- 64-bit has a much smaller initial error (1/2^53), while 32-bit has (1/2^23) initial errors... starting with 30-magnitudes more error than double-precision.
- vlovich123 5y agoKahan summation[1] may be better than just doing a sorted sum & doesn't require you have all the numbers up-front to sort (i.e. running sum). Although I think even it benefits from doing it in sorted order if you do have the full history available & the wikipedia article lists a parallelization technique you can leverage in that case. Klein sum might be better but I haven't investigated. EDIT: Apparently there's a nice Rust crate for doing this stuff: https://crates.io/crates/accurate https://crates.io/crates/accurate [1] https://en.wikipedia.org/wiki/Kahan_summation_algorithm#Alternatives https://en.wikipedia.org/wiki/Kahan_summation_algorithm#Alte...
- thxg 5y agoThis work essentially allows one to go beyond the IEEE754 standard which mandates correctly-rounded elementary operations +, -, x and / : they provide implementations of libm functions (cos, sin, log, exp, etc.) that are also correctly rounded. This is really nice, not necessarily because anyone cares about the correctness of the last bit in a float. But more importantly, because since there is only one "correct" answer, requiring correct rounding means that those functions are then fully specified and deterministic. No more getting slightly different result when changing platform, OS, or even just updating libm (some transcendental functions are still actively being improved, thus changed, in glibc!). This is amazing for reproducibility. Since the performance is good (even better than existing libm implementations, they claim), this is a true win-win. This is obviously made possible by the fact that one can easily enumerate all 32-bit floats. It would be amazing to have something similar, even at a big performance cost, for 64-bit doubles (MPFR can do it of course but the perf cost there is truly massive). Things are much harder with 64 bits, unfortunately.
- wumpus 5y ago> No more getting slightly different result when changing platform, OS, or even just updating libm Optimizing compilers are usually used with flags that cause them to break IEEE754. Still, it would be nice if results from low-optimization runs might be bit-exact.
- thxg 5y agoYes, indeed it is the case with fused multiply-add operations, as I wrote below in another thread. By default at -O3, unfortunately, gcc and icc both take responsibility for deciding whether or not to use FMA instructions when they see (a x b + c) expressions. As a result we can even see slightly different result across compiles!! However, as far as I understand, specifying a proper language standard (for example -std=c99, -std=c++14, etc.) restores sane behavior (see -ffast-math, and more specifically -fexcess-precision). Are there other cases where -O3 breaks IEEE754 on modern setups?
- jcranmer 5y ago
- brandmeyer 5y agoIts unfortunate that they don't mention the prior work of the crlibm project in this domain. https://gforge.inria.fr/scm/browser.php?group_id=5929&extra=crlibm https://gforge.inria.fr/scm/browser.php?group_id=5929&extra=... Github mirror: https://github.com/taschini/crlibm https://github.com/taschini/crlibm Python bindings: https://pypi.org/project/crlibm/ https://pypi.org/project/crlibm/ Julia bindings: https://juliapackages.com/p/crlibm https://juliapackages.com/p/crlibm
- samth 5y agocrlibm is discussed in their paper: https://people.cs.rutgers.edu/~sn349/papers/rlibm32-pldi-2021-preprint.pdf https://people.cs.rutgers.edu/~sn349/papers/rlibm32-pldi-202...
- brandmeyer 5y agoBased on their press material, you'd think that nobody else has done this before at any precision. You can see the resulting confusion in this very forum. That kind of behavior is disingenuous at best.
- jart 5y agoI'm a libc author and I want to use this. Then I clicked on the repository and there wasn't any code implementing these libm routines. Instead it just had tools and they told me I need to install a 6gb docker container to use them.
- stephencanon 5y agoI love everything about this project, but I am fairly skeptical of their benchmarking. In particular, they use a _lot_ of polynomial intervals for some of these functions, it's easy to accidentally construct microbenchmarks that miss the cache effects that fall out of that (the full set of coefficients for one of these math functions can easily take up a substantial fraction of your L1; for some use cases that won't matter, for some other scenarios it will be catastrophic). Historically, high-performance libm implementations have gone to great pains in their internal benchmarking projects to avoid accidentally ignoring these effects and shipping functions that are significantly slower in real use. None of this is to say that they have necessarily fallen into this trap, but historically most "fast" math function implementations that use piecewise polynomials with high segment counts do (and none of it should take away from the accomplishment--even if they're really 2x slower than claimed, they're fast enough for most code to simply use it unconditionally and get the portability benefits).
- FullyFunctional 5y agoI love that they have an implementation for posits too.
- herodotus 5y agoI know this is off topic, but the inconsistent use of "i.e." and "e.g." is particularly bad in this article. If you are not sure of the difference in your own writing, use "that is" in stead of "i.e." and use "for example" instead of "e.g." Notice in this article, in the section entitled "What is the correct result of f(x)?" they say "e.g. ln(x)" in one case and "i.e. ln(x)" three sentences later. Well which is it? It is not just that I am a curmudgeon. Precision matters. When they say, for example, "Everyone uses math libraries (i.e. libm)" do they mean "Everyone uses the libm math library" or, more likely, "Everyone uses math libraries such as libm". Yes, the resolution in this case is fairly obvious, but I would get much more out of the article if I was not distracted by these slight inadvertent ambiguities and misuses.
- jasonwatkinspdx 5y agoThe nemonic I was taught was "In Explanation" and "Example Given."
- josephg 5y agoI always just think of them as “in effect” and “(for) example”, which is their direct expansion. But that distinction makes sense to me because I use the phrase “in effect” in speech as well sometimes. It hadn’t occurred to me that this is unusual - I suppose it is? I wonder if it’s a aus / US cultural difference? (I’m Australian) or maybe something I picked up years ago as a grad student?
- macintux 5y agoI just think “egsample” and then i.e. must be the other one.
- moonchild 5y agoHow does this compare with sleef[0], which also provides high performance (as well as vectorization), and implements all the same routines as rlibm (among others) with ≤1 ulp error? 0. https://sleef.org/ https://sleef.org/
- adgjlsfhk1 5y agoIt will be a good bit slower. The difference between 1 ULP and .5 ULP is pretty big. Also the method of using a bunch of different polynomials won't vectorize especially well.