Avoiding PartialOrd problems by introducing fast finite floating-point types

[kornel]

In the ergonomics issue there’s a mention of deprecating PartialOrd/PartialEq.

Apart from #[derive] verbosity (which I hope can be fixed somehow) these traits become annoying only when using the floating-point types.

So how about making it easy for users to avoid these traits by introducing a fast, finite-only floating point type instead?

This could solve two problems at once, as the new floating point type could also work as an enabler of -ffast-math which Rust currently lacks.

The new floating-point type would forbid NaN and Inf (caught with debug assertions similarly to overflows), which makes Eq and Ord well-defined and use fast intrinsics for arithmetic operations, allowing more aggressive optimizations.

I’ve prototyped a newtype f32 wrapper that uses the fast intrinsics, but newtypes don’t work with floating-point literals and the as operator (and AFAIK there’s no intention to ever allow that), so it’d be much better as a built-in Rust type.

[withoutboats]

The new floating-point type would forbid NaN and Inf (caught with debug assertions similarly to overflows),

What operations would have debug assertions?

What would be the behavior in release builds?

[rkruppe]

Interesting idea, getting rid of NaN by reframing the types has a certain appeal. I have two concerns, however:

1. Infinities and NaN exist for good reasons, they provide reasonable closure under operations that don’t have sensible finite results. Rounding guarantees also exist for good reasons, they make it possible to reason about (and work to optimize) the numeric stability of programs. These are not just a concern for highly accurate scientific simulations, they are also useful in computer graphics (the reason shaders and so on tend to default to fast-math is a deliberate trade off where the massive performance win trumps other concerns). Getting rid of both is a big step, and one I could easily see reducing the reliability of Rust programs. Basically, I would like to see much more discussion of the effects of eschewing these features. (This also ties into @withoutboats’s questions.)
2. I am quite uneasy with coupling absence of NaN to fast-math (breaking rounding guarantees and removing infinities). There are many cases where one might want to statically get rid of NaN/use Eq and Ord without having a good reason to abandon other properties of IEEE 754. I am concerned that these types would be an attractive nuisance, used for NaN-freeness and then causing trouble with their fast-math-ness.

[kornel]

What operations would have debug assertions?

It could be is_finite() after every operation that could produce a NaN/Inf, e.g. division. And when regular float is mixed with the fast float.

What would be the behavior in release builds?

IEEE float behavior, but with associativity. Like clang’s -ffast-math.

[kornel]

f32 / f64 remain as they are for users who have good reasons to use NaN, Inf and care about every ULP. Even if you use fast floats, you can still identify the parts of your calculations that need extra guarantees and cast to and from f32 / f64 there (that’s a big improvement over -ffast-math in C which is a global all or nothing).

The role of NaN as a signal of an error condition will be mostly handled by debug assertions. I presume that (-1. as fast_f32).sqrt() will panic. This may actually be more useful than just propagating NaN through calculations, as it shows ASAP exactly where it originated from (as opposed appearing somewhere later, or even just silently breaking things if results are converted to integers or only used to compare numbers).

I mainly use Rust for computer graphics, that’s why I’m so keen on a finite fast-math type. In most cases f32 has more than enough precision for even complex computations on linear light RGB.

[glaebhoerl]

after every operation that could produce a NaN/Inf

Isn’t this almost all of them with overflow?

[rkruppe]

f32 / f64 remain as they are for users who have good reasons to use NaN, Inf and care about every ULP.

Obviously. My point is that (1) making it too easily available and (2) combining no-NaN and other kinds of fast-math into one package could lead to over-use of fast-math behavior, and that this could negatively affect the reliability of the average Rust program.

The role of NaN as a signal of an error condition will be mostly handled by debug assertions.

The important part is the behavior in release mode. fast-math mode doesn’t actually remove NaNs and infinities, it just permits optimization that ignore their existence. This is an odd “Schrödinger’s cat” state. Calculations that result in NaNs or infinities will generally still produce them (maybe constant folding does something weird), but code will be transformed assuming they don’t (potentially breaking code that may otherwise handle them gracefully).

So AFAICT, and contrary to my initial impression, this would not actually remove the need for PartialOrd by eliminating NaN. It would just mean giving up on trying to preventing errors from the order being partial, but we could do this without the whole fast-math business (the idea has been voiced before, independently). The only other solution I can see is giving this fast-math type a different comparison operation, e.g. the total ordering predicate described in IEEE 754. However:

1. This is at odds with the stated performance goal, since these comparisons generally don’t have as much hardware support.
2. This, too, is entirely independent of the whole fast math thing.

[kornel]

The important part is the behavior in release mode. fast-math mode doesn’t actually remove NaNs and infinities, it just permits optimization that ignore their existence.

This is what I’m proposing. The release mode would be like -ffast-math.

Here’s a rough implementation of it:

https://play.rust-lang.org/?gist=d516771d1d002f740cc9bf6eb5cacdf0&version=nightly&backtrace=0

[rkruppe]

Good to hear that I understood correctly. Then I’d like you to respond to the issues that I listed.

[kornel]

lead to over-use of fast-math behavior, and that this could negatively affect the reliability of the average Rust program

I don’t think it’s so clear-cut:

• From what I’ve seen -ffast-math is widely (over)used in C and doesn’t cause problems in general applications. Developers who require certain IEEE behaviors know not to use it.

• It may improve reliability of Rust programs. The debug assertions don’t remove NaNs, they make them louder. Just yesterday I’ve found NaNs in my program while trying the fast-float prototype. I weren’t seeing the NaN before, because I only used it for if result < 0., which was silently corrupting my data. I find these assertions super useful, but they can’t be added to the existing f32 without causing huge breakage, so it has to be a new type.

[kornel]

It would just mean giving up on trying to preventing errors from the order being partial, but we could do this without the whole fast-math business (the idea has been voiced before, independently).

I think giving up on Ord reliability for all floating point types would be worse, since it would lose the guarantees for all programs everywhere, without a way to opt out. Limiting potential Ord problems to only the special type limits the damage to only uses of that type, and allows others to stick to the strict float if they want to.

The new Ord-compatible float type can have extra debug assertions that help in removing NaNs from the program. That’s better than just allowing Ord for f32, where avoiding NaN is purely programmer’s responsibility without any help from Rust.

[kornel]

As for coupling fast-math and no-NaN assertions in one type: yes, they are separate concerns.

However, both of them are best expressed as a type. I think both are useful. But adding two or three new floating types (separate type for each and perhaps one more type for the combination of both) would be obviously too much. So merging them into one new type, while not ideal, I think is a pragmatic choice.

[jmst]

What we might need are float types with typestate.

Something like F64<CheckAtRuntime, NoNaNs, NoInfs, NoSignedZeroes, AllowReciprocal, AllowContraction, Reassociate, OtherFast> (these are LLVM’s flags for floating point operations, except for Reassociate split out of OtherFast).

Ord would be implemented only for NoNaNs = True. Checks in debug mode only unless CheckAtRuntime is True (unsafe code already can’t rely on Ord behavior).

Developers would use this by defining a type alias with the desired options. Would need to add an “as” trait to the compiler, a “pragma” allowing to choose the type to assign to constants, and preferably keyword-based parameters for generics.

Anyway, another possible solution for sort is to define sort on “SemiOrd”, which would be a new trait inheriting from PartialOrd that adds an “is_comparable” method and guarantees that the order is a total order on elements where “is_comparable” is true, while the other elements are not comparable with anything (obviously in the float case is_comparable would be !is_nan).

This allows to trivially implement a fast sort respecting the partial order by first placing all incomparable elements at the end, and then sorting the rest as normal using a comparator based on PartialOrd with unwrap.

(without such a guarantee it would still be possible to implement a sort, but it would take n^2 time on a slice with all nans since it needs to do all pairwise comparisons in case a pair is comparable, which is unacceptable)

[burakumin]

I still do not understand what is the answer to @withoutboats’s question:

What would be the behavior in release builds?

If I write let z = 1.0ff32 / 0.0ff32 (with postfix ff32 representing this finite floating-point type) what do I get while running the program in release build? +Infinity ? Undefined behaviour? Panic ?

If the issue is about PartialOrd why isn’t this sufficient ?

[kornel]

f I write let z = 1.0ff32 / 0.0ff32 (with postfix ff32 representing this finite floating-point type) what do I get while running the program in release build? +Infinity ? Undefined behaviour? Panic ?

1. You get “warning: attempt to divide by zero”, same as for “1/0” in Rust today.

2. It compiles, and you get the result of core::intrinsics::fdiv_fast(1.0f32, 0.0f32). In this particular case it’s Inf, but since LLVM is free to optimize these expressions with assumption that they’re finite, you might get a different value in a more optimizable expression.

3. Presence of Inf or NaN is never supposed to be an Undefined Behavior. Per existing LLVM rules division by zero, in any mode, already is UB.

[burakumin]

As far as I understand this behavior would contradict the very definition of a type. To me a type defines a set of legal values and the result of some associated transformations (functions). Here we would have a type that in the end can handle exactly the same values as f32, that would pretend some of them do not exist and that would let the compiler introduce any sort of unpredictable behavior it wants if one of such values unexpectedly enters the type and propagates.

[kornel]

(I would prefer to stay away from “what is a type”. That can easily change the topic of the discussion from floating-point usability and performance into a discussion about semantics of the term itself)

From what I understand your concern is that the fast-f32 type would be defined as having only finite values, but it would still be able technically to have NaN and Inf values.

This type can be defined as a type that can contain NaN and Inf values, but it is considered a programmer error to create them. Similarly like u32 is defined to overflow, but it is considered a programmer error to overflow.

would let the compiler introduce any sort of unpredictable behavior it wants if one of such values unexpectedly enters the type and propagates.

The alternative of implementing Ord on f32 and f64 allows exactly this on all floating-point types, in both debug and release mode.

I think I’m proposing a less-bad version of this, where such error can be introduced only for the finite-float type, and only when debug assertions are disabled.

[le-jzr]

Looking at the problem from the opposite direction, is it actually necessary to have traits for total ordering/total equality? As far as I can tell, we could just have Eq and Ord with the semantics of current Partial*, and the loss of functionality would be negligible, if any. Especially for Eq, which doesn’t do anything different and the invariant can’t even be depended on, since there’s no way to verify it.

[troplin]

since LLVM is free to optimize these expressions with assumption that they’re finite

This is exactly what makes undefined behavior so dangerous. You might not call it undefined behaviour, but the effect is the same.

[le-jzr]

It’s never an undefined behavior.

If optimizations are allowed to assume that something doesn’t happen, then that thing happening is undefined behavior by definition. More to the point, depending on which optimizations take place, it could have repercussions for safety, and might be entirely nontrivial to prove that those repercussions don’t exist. But I might be reading too much into it. If it’s just about allowing certain expression transformations, and not about blank check for assuming those properties, then it should probably be fine. Maybe. Possibly.

Wouldn’t it be better to instead augment comparison in all build modes? Make NaN == NaN true. The impact on performance can’t be that bad if only comparisons are affected, can it?