ACP: NonNanFNN and FiniteFNN float wrappers

[clarfonthey]

Proposal

Problem statement

A lot of the existing code for floating-point values will special-case infinite and NaN values, and it's desirable to be able to specify at the type level that these values cannot occur. Additionally, the ability to remove NaN values from floats would allow the ability to implement Ord for these types, enabling their use in many APIs without relying on total_cmp.

Motivating examples or use cases

• Inclusion in types which require Ord invariants, such as the keys of a BTreeMap or the values in a BinaryHeap.
• Storing values which are interpolated in various contexts, such as layout engines or stored statistics, since interpolating these values can cause undesired behaviour.
• Floating-point values stored in enums which leverage niche optimisations, reducing memory usage by storing sentinel NaN values.
• High-performance floating-point code which wishes to avoid special-casing NaN and infinite values.

Notes on optimisation as motiviation

One potential benefit of these types is the ability to add additional optimisations to them. For example, operations like sin, cos, and hypot could all be modified to return values that are explicitly non-NaN to avoid additional checks for NaN in code.

However, note that these cases can be relatively niche and it's not clear how many of these would be actually useful. Additionally, operations that are more complicated like linear interpolation would have to be included in the standard library, and we've already mostly decided that these operations are not a good fit for the standard library due to their complexity.

Additionally, many operations would only be easily optimised if the floats were further constrained to be explicitly positive, non-zero, non-one, or bounded in some other arbitrary way. This definitely reduces the usefulness of this avenue of optimisation, and it feels best to only analyse these types as being useful specifically for their invariants, rather than for their ability to optimise various mathematical operations, at least within the standard library. Obviously, downstream crates can leverage these types for their own optimisations, assuming that they're okay with using unsafe code.

Solution sketch

Four types would be added: NonNanF32 and NonNanF64 for f32 and f64 types which exclude NaN values, and FiniteF32 and FiniteF64 for types which exclude both NaN values and the two infinities.

The minimum API for these types should mimic that of the NonZero* types, namely (using NonNanF32 as an example):

pub const unsafe fn new_unchecked(x: f32) -> NonNanF32;
pub const fn new(x: f32) -> Option<NonNanF32>;
pub const fn get(self) -> f32;

Additionally, these would implement all of the common traits from their underlying floating-point types (PartialEq, PartialOrd, Copy, Debug, etc.) but also implement Eq, Ord, and Hash due to the lack of NaN values. Unlike the NonZero* types, Default would be fine, since zero would still be included.

These types would additionally include niche areas for the forbidden values, which is possible due to the fact that non-finite values are represented by two continuous ranges (one for each sign) when treated as integer bits. The infinities also exist at the edges of these ranges adjacent to the finite values and can easily be represented.

Alternatives

The primary alternative would be to simply avoid adding these types, as there are many crates that already exist to provide these types. The largest benefits of a standard library implementation would be to standardise these types, provide niche optimisations (at least until a stable avenue exists), and to potentially optimise various mathematical operations on these types with compiler help, although that last bit is disputed in the motivation section.

Links and related work

• RFCs issue discussion: Idea: NonZero-like float wrappers rfcs#2458
• Internals thread discussion: https://internals.rust-lang.org/t/pre-pre-rfc-range-restricting-wrappers-for-floating-point-types/6701
• Popular external crate solution: https://docs.rs/decorum/latest/decorum/

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[scottmcm]

It might be interesting to explore what using, say, the nnan flag in LLVM actually allows optimizing in practise.

Unfortunately, neither non-NAN nor Finite are closed for floats, so these types if they had even Add and friends, would plausibly still be Output = f32.

As such, I suspect that the most useful versions are the NonNan ones, as they can be Ord. But it plausibly would still be best for those to be operated on in normal f32, and only converted back to NonNan as a storage format at the end.

[clarfonthey]

I had no idea about the nnan and ninf flags in LLVM; those do give some indication of the optimisations being useful, but I have no idea what LLVM does to them in practice.

That said, while I get that finites aren't closed under most operations (you can easily add/multiply finite numbers and get an infinity), I thought that at least non-NaN operations were? Like, obviously finites aren't closed under operations like sqrt, but I thought that something like x + y is guaranteed to be non-NaN as long as x and y aren't NaN.

[scottmcm]

Finite+Finite might be ±∞, though, same with Finite/Finite, so Finite isn't closed.

And NonNan±NonNan might be NAN because of ∞-∞ or ∞ + -∞, so NonNan isn't closed either.

[pitaj]

0/0 is even an operation on non-NaN finites that doesn't close.

[clarfonthey]

Right, in those cases Finite + Finite = NonNan, so, not closed, but still not NaN. Honestly, given the number of variations, you're right to say that it seems like way more work than just using it for storage, as I mentioned originally.

[m-ou-se]

I've wanted something like this quite a few times, but in a way that every single NaN representation will be interpreted as Option<NonNanF32>::None, instead of using only one specific bit pattern for that.

The compiler currently doesn't support that. But the advantage would be that NonNanF32::new would be a no-op. (In that situation, None-propagating math operations on Option<NonNanF32> would be 'free', since f32 operations already propagate NaN.)

[m-ou-se]

• Inclusion in types which require Ord invariants, such as the keys of a BTreeMap or the values in a BinaryHeap.

How would Ord behave for positive and negative zero? Would those compare equal? If so, f32::total_cmp could still be preferrable when using floats as keys in a BTreeMap.

[m-ou-se]

• High-performance floating-point code which wishes to avoid special-casing NaN and infinite values.

Wouldn't the NonNan types actually cause more special casing? If a processor natively supports operations like addition/multiplication/division/etc. that can result in NaN, using NonNan types would mean extra branches to handle those results separately, right?

[m-ou-se]

• Floating-point values stored in enums which leverage niche optimisations, reducing memory usage by storing sentinel NaN values.

That would work for something like

enum Thing {
    Float(NonNanF64),
    False,
    True,
    FileNotFound,
}

but for most such 'nan boxing' optimizations I've seen in the wild, you want to be able to make use of all 52 bits, which won't happen through a simple enum like that, unless we add some magic compiler support and a special 'only NaN' type like:

enum Thing {
    Float(NonNanF64),
    NotFloat(Nan52),
}

Also, most cases I've seen still want to support actual NaN, so they still reserve one bit pattern for f64::NAN and using the remaining NaN representations for other values. For those cases, NonNanF64 isn't what they need.

So for 'NaN boxing' I'm not convinced NonNanF64 is more useful than a #[repr(transparent)] struct Thing(f64); with methods that use f64::bits() and f64::from_bits().

[clarfonthey]

• Inclusion in types which require Ord invariants, such as the keys of a BTreeMap or the values in a BinaryHeap.

How would Ord behave for positive and negative zero? Would those compare equal? If so, f32::total_cmp could still be preferrable when using floats as keys in a BTreeMap.

This is a good point; I was considering them as being treated equal.

• High-performance floating-point code which wishes to avoid special-casing NaN and infinite values.

Wouldn't the NonNan types actually cause more special casing? If a processor natively supports operations like addition/multiplication/division/etc. that can result in NaN, using NonNan types would mean extra branches to handle those results separately, right?

So, my thought process is that this only reduces special-casing for inputs, and not for outputs. So, these operations could output NaN floats, but at least any special-casing of what happens for input NaNs wouldn't be necessary. But if you want to make it a closed loop, you're right that it would require extra branches.

[m-ou-se]

So, my thought process is that this only reduces special-casing for inputs, and not for outputs. So, these operations could output NaN floats, but at least any special-casing of what happens for input NaNs wouldn't be necessary.

But that just moves the checks elsewhere, right? Is that by itself very useful?

Do you have any example use cases where these types would help with performance or correctness while also making good use of the NaN niche optimization*?

(* Because that's the reason this currently can't be done outside core/std.)

[clarfonthey]

So, while it is the one example of something that got tossed out of libstd, I keep thinking back to lerp because it's a good example of something well-behaved that could really benefit from these sorts of optimisations. While the fundamental operations can overflow to infinites or lead to NaNs in some cases, if you're careful about how you deal with them and have bounded inputs, you're effectively guaranteed to end up with bounded outputs.

Interpolation in general is probably the most common case here, since it's something that requires having a lot of bounds checks on inputs, but by its nature bounds outputs to inputs, and thus also satisfies the closure property. Effectively, the unboundedness of the outputs of fundamental operations is resolved by additional unsafe assertions, rather than branches.

Effectively, you can "get past" the extra branches on the outputs with assertions, but you can't easily do this on inputs without the compiler support. Maybe some sort of finagling with assertions can coerce the existing compiler to optimise properly today, but at least I'm not aware of any.

Another potential example on my mind that actually exists in the standard library is hypot. With how hypot works, finite inputs will always result in finite outputs, since the triangle inequality holds. Since it actually ensures the precision of the computation instead of doing the naïve square-sum-square-root method, this works out, although the naïve method could still fail since sqrt(MAX_FINITE * MAX_FINITE) would be infinity.

[dtolnay]

Another potential example on my mind that actually exists in the standard library is hypot. With how hypot works, finite inputs will always result in finite outputs, since the triangle inequality holds. Since it actually ensures the precision of the computation instead of doing the naïve square-sum-square-root method, this works out, although the naïve method could still fail since sqrt(MAX_FINITE * MAX_FINITE) would be infinity.

hypot is $\sqrt{a^2+b^2}$, not $\sqrt{a \times b}$. Finite inputs do not necessarily result in a finite output. The output may be up to √2 times larger than the largest input.

println!("{}", f64::MAX.is_finite()); // true
println!("{}", f64::hypot(f64::MAX, f64::MAX).is_finite()); // false

[dtolnay]

We discussed this proposal in the most recent T-libs-api meeting. We discussed each of the motivations, and came away not convinced that these additions to the standard library would be worthwhile.

1. The desire for "float without edge case I must check when doing math" is real, but fragmented across "float without NaN", "finite float", "float without zero", "positive float" and probably others, depending on what math operations one wants to apply to it. NotNanFNN and FiniteFNN would surely cover the largest chunk of this, but since a standard library version of these are unlikely to optimize any better than a naïve newtype from a crate, we didn't feel compelled by this to standardize.

   We would be prepared to consider compelling evidence about the advantage of LLVM nnan or ninf on a mainstream backend, though, but take into account that NotNanFNN can end up wasting more time checking for NaN, as pointed out in ACP: NonNanFNN and FiniteFNN float wrappers #238 (comment) and ACP: NonNanFNN and FiniteFNN float wrappers #238 (comment).

2. "Float that I can use a map key" may be the closest to a compelling justification, but ultimately we leaned toward ordered_float serving this use case better. Neither NotNanFNN nor FiniteFNN are what you want for a map key, due to the negative zero issue: ACP: NonNanFNN and FiniteFNN float wrappers #238 (comment). OrderedFloat is some third thing.

3. "Float storage format with niche" sounds nice but neither NotNanFNN nor FiniteFNN is the thing people want in this context. See ACP: NonNanFNN and FiniteFNN float wrappers #238 (comment).

While we're not interested in NotNanFNN or FiniteFNN for the standard library, our impression is that lang/compiler folks are interested in functionality that an external implementation of these types could use to implement real niches for the NaN range. See rust-lang/rfcs#3334, rust-lang/rust#107606, https://cohost.org/oli-obk/post/165584-ranged-integers-via for work in this space, and feel free to contribute. The most recent discussion on this is happening in the t-types Zulip.