Avoiding PartialOrd problems by introducing fast finite floating-point types

[troplin]

In LLVM terminology that’s implementation-defined behavior.

For me that’s the desired behavior I have a ton of finite-math code that LLVM doesn’t optimize well, because it works extra hard to preserve values and conditions that are not there.

Conditions that you believe are not there. Not statically proved.

Optimizing based on wrong assumptions is dangerous and undefined behavior. It cannot be implementation defined, because the implementation then would have to specify exactly what will happen. And it cannot do this since this can affect completely unrelated code.

[burakumin]

Here I mean “undefined behavior” as defined by LLVM.

It’s not a colloquial “lacking definition”, but “precisely defined condition that allows LLVM to delete or miscompile any code proven to cause UB”.

Admittedly I do not know what LLVM calls an undefined behavior but the reference gives a list of behaviors considered undefined in Rust and among them you have:

Invalid values in primitive types, even in private fields/locals:

• Dangling/null references or boxes
• A value other than false (0) or true (1) in a bool
• A discriminant in an enum not included in the type definition
• A value in a char which is a surrogate or above char::MAX
• Non-UTF-8 byte sequences in a str

To me this looks a lot like what you are proposing.

[kornel]

For me that’s the desired behavior I have a ton of finite-math code that LLVM doesn’t optimize well, because it works extra hard to preserve values and conditions that are not there.

Conditions that you believe are not there. Not statically proved.

This is no different from vec[i] or a / b. Correctness of either is an assumption and cannot be statically proved.

In my particular case all floats come from rgb / 255.0, so I have sound reasons to believe they are finite. And I’m proposing debug assertions to confim that at run time.

@troplin @burakumin The terms “Undefined Behavior” and “Implementation Defined” come from the C spec and have been adopted by LLVM to describe how it optimizes certain code.

These terms may not fit your common-sense understanding of what is defined properly, but UB and ID are not an opinion, they are names for LLVM features. They could as well be called Blerg and Ulg. Fast math is not Blerg, but is Ulg. Division by zero is Blerg. High order bit of right shift is Ulg.

[kornel]

Optimizing based on wrong assumptions is dangerous

Fast math assumes values are finite and addition is commutative. If that doesn’t suit your assumptions, then don’t use the type that makes it a contract.

If you deliberately use NaN, then use regular f32. If you don’t expect to have NaN, but get one anyway, then it’s a bug in your code.

That’s no different than making assumptions that values in your program are positive and using u32. If values may be negative, use i32. Just like if you accidentally do 1u32 - 5u32. That doesn’t make u32 type dangerous.

These operations have garbage-in garbage-out behavior. If you feed them garbage, then it’s not really a big deal that you might get a different garbage than the garbage that the other mode would produce. In such case you never had a chance to get valid value in the first place, because your code violated assumptions in your head.

[troplin]

@troplin @burakumin The terms “Undefined Behavior” and “Implementation Defined” come from the C spec and have been adopted by LLVM to describe how it optimizes certain code.

These terms may not fit your common-sense understanding of what is defined properly, but UB and ID are not an opinion, they are names for LLVM features. They could as well be called Blerg and Ulg. Fast math is not Blerg, but is Ulg. Division by zero is Blerg. High order bit of right shift is Ulg.

The problem is not the expression itself, but further optimizations that depend on those assumptions.

Take for example a float -> integer cast. This is currently undefined behavior in Rust, which ist considered a bug.

Now let’s assume that this bug was fixed by testing for INF and NaN before casting. If you use your new shiny finite types, the compiler is allowed to optimize those tests away and we’re back to good old UB.

You cannot just argue on the LLVM level, without considering the semantics of Rust. Rust is not C.

[burakumin]

@troplin @burakumin The terms “Undefined Behavior” and “Implementation Defined” come from the C spec and have been adopted by LLVM to describe how it optimizes certain code.

These terms may not fit your common-sense understanding of what is defined properly, but UB and ID are not an opinion, they are names for LLVM features. They could as well be called Blerg and Ulg. Fast math is not Blerg, but is Ulg. Division by zero is Blerg. High order bit of right shift is Ulg.

Terms are defined relatively to a context. You can argue that this is not up to the Rust Reference to give an alternative meaning to “Undefined Behaviour” and that the source of truth on this topic is either the LLVM manual or the C spec but in that case we have a much bigger problem than optimizing floating-point types and you should instantaneously start a thread “The Rust manual is wrong!”

This is no different from vec[i] or a / b. Correctness of either is an assumption and cannot be statically proved.

I don’t understand how this comparison could be valid. AFAIK these operations panics when the requirements are not met (both in debug and release mode). Are there some flags to remove the checks ?

[kornel]

I understand your argument as “if we implement it wrong in Rust, it will be wrong in Rust”. If rustc inserts non-optional checks in the way that they’re understood as optional for LLVM, that’s just a rustc bug.

The as operator generting an undef is an interesting bug, but it’s just an implementation bug. It’s not an inherent unsafety of floats or LLVM, it’s a bug in rustc/LLVM integration that will be fixed.

[kornel]

I don’t understand how this comparison could be valid. AFAIK these operations panics when the requirements are not met (both in debug and release mode). Are there some flags to remove the checks ?

That was just a counter-example for argument that Rust can’t have conditions that can’t be statically proven. These panic exactly because they could not have been statically proven.

For non-panicking example consider a+b. Rust can’t statically prove it won’t overflow. It will panic in debug mode (same as I propose with float overflows causing Infs) and will quietly overflow in release mode (same as I propose with float overflows).

[kornel]

I really don’t understand why this discussion seems to have focused on “proper” handling of NaNs in a type that where any NaN by definition is complete garbage with no useful purpose whatsoever, and is not allowed to be used to produce any useful value in any case, by definition.

I think it’s not fair to want to deliberately break the contract of the type, feed invalid-by-definition values to an expression and then still expect it to produce valid values from invalid inputs.

I feel like if I proposed to have an integer-only type I’d have to defend its handling of 1.5 and how horrible it would be for programs using u32 not to be able to add 1.5 + 1.5 correctly.

[troplin]

I understand your argument as “if we implement it wrong in Rust, it will be wrong in Rust”. If rustc inserts non-optional checks in the way that they’re understood as optional for LLVM, that’s just a rustc bug.

The as operator generting an undef is an interesting bug, but it’s just an implementation bug. It’s not an inherent unsafety of floats or LLVM, it’s a bug in rustc/LLVM integration that will be fixed.

If you ready my post carefully, you will see that my argument was based on a future rustc where the bug is fixed.

You always argue with LLVM, but LLVM is just the implementation. I’m arguing on the language level: If your type defines that NaN and INF cannot happen, the any optimizer (not just LLVM) can optimize based on that fact. If you are producing an illegal bit pattern and use that value later on, that’s undefined behavior, you cannot just deny that.

I think it’s not fair to want to deliberately break the contract of the type, feed invalid-by-definition values to an expression and then still expect it to produce valid values from invalid inputs.

I think this is fair, since the contract is only based on convention. And it requires no unsafe code to break it. It’s possible to produce such garbage values with perfectly legal inputs, using completely innocent operations.

C is such a language and I really don’t want Rust (Rust, the language, not rustc, the compiler) to make even a small step in the direction of allowing UB in safe code.

I feel like if I proposed to have an integer-only type I’d have to defend its handling of 1.5 and how horrible it would be for programs using u32 not to be able to add 1.5 + 1.5 correctly.

The big difference is, that an integer cannot represent 1.5, while your type can represent NaN. And operations on integer cannot produce 1.5, while operations on your type can produce NaN.

[steveklabnik]

is it actually necessary to have traits for total ordering/total equality?

This was considered in the run-up to 1.0, but in the end, we kept what we had/have.

[KasMA1990]

Having followed the discussion so far, one avenue that doesn’t seem to have been followed is: what if this type was only allowed to exist in unsafe code? Then you would have to cast it to a regular float to use it in safe code, but if you have a hot path that deals with floating point values, you can opt in to the optimization at least.

Of course, that changes nothing for PartialOrd, and it still introduces some UB. Is UB allowed to exist in unsafe code as it is today?

[burakumin]

I really don’t understand why this discussion seems to have focused on “proper” handling of NaNs in a type that where any NaN by definition is complete garbage with no useful purpose whatsoever, and is not allowed to be used to produce any useful value in any case, by definition.

Maybe our disagreement comes from the fact that I precisely don’t agree with that statement. NaN is a valid value of floats with defined behaviour for mathematical operations so it is not complete garbage. It’s part of of the floating-point arithmetic. We can of course discuss if the chosen behaviour was the most appropriate (with the infamous NaN != NaN) or if it should have been replaced by another mechanism (crashing the app/exception/mere undefined behaviours when for example computing 0.0/0.0). We can also complain about the fact it may be undesirable in many numeric applications. Now it is still a valid part of the arithmetic implemented by processors (to be clear I don’t like it either) and as such it is not a second-class value.

Basically as I see NaN, it is nothing but an internal None value for floating point types. Imagine that now the compiler considers some Option<> are necessarily Some variants without any static check and if a None is unfortunately introduced, instead of panicking the program produces whatever behaviour LLVM fancied. I would personally not like it.

[kornel]

If your type defines that NaN and INF cannot happen

So let me redefine that: it’s a type where INF and NaN can happen. Optimizer should assume that code producing them can exist (by accident), and it’s not an undefined behavior.

However, existence of NaN and INF is considered an indication of a bug and treated as malformed input, rather than as legitimate valid input.

The optimizer is still allowed to make optimizations that produce accurate results only for finite values. The optimizer is required to allow code that touches non-finite values to exist (i.e. it’s not UB/undef), and is required to make operations on NaN/Inf produce some value, but the value is allowed to be implementation-defined (i.e. garbage like NaN/Inf, 0. 17.12 or any other bit pattern in f32), but the value is not undef and the optimizer is never allowed to spawn nasal demons when NaN or Inf is found.

[kornel]

NaN is a valid value of floats with defined behaviour for mathematical operations so it is not complete garbage. It’s part of of the floating-point arithmetic.

Right, that’s very well. It is a part if IEEE 754 floating-point arithmetic and conditions where NaN appears are indeed very precisely defined.

Very strictly speaking, you could think of what I’m proposing here is to create new floating point type, with its own rules and own definition of NaN, which is not the IEEE 754 float, but a new thing that just happens to look 99% like it so that it can use the existing IEEE 754 hardware for speed.

I fully acknowledge that there are domains where NaN / Inf is valid, useful and necessary. And f32 / f64 are the types to be used there.

However, there are also other domains (in my case image and video codecs) where all the well-defined proper IEEE 754 operations on NaN and Inf are never needed in practice. The nature of the problem is such that these values have no use, and are never intentionally created. In such context a NaN appearing in the program against author’s intention is an indication of a bug. For example when I have an array of RGB pixels as floats, then the concept of NaN or Inf does not apply to them. I can’t display NaN Red or Inf Blue on screen. If my program happens to produce a non-finite color value, that’s a bug in my program, even though the steps that lead to producing that value are well-defined in IEEE 754 spec, it is an indication of my mistake.

The problem is that programs which don’t intend to make useful use of NaN still have to pay the cost of it. The code is slower because the compiler is required to preserve very specific NaN handling rules, even when the program by design is incapable of doing anything useful with them.

[burakumin]

However, there are also other domains (in my case image and video codecs) where all the well-defined proper IEEE 754 operations on NaN and Inf are never needed in practice. The nature of the problem is such that these values have no use, and are never intentionally created.

I understand your usecase but I suppose me and other people here consider that your proposition for fixing this issue is not satisfying.

Now I’m a bit curious: is that really impossible for the cases you’re mentioning to create a numeric type (let’s call it for example ff32) that really excludes NaN and Inf ? Some operations might naturally make it impossible to produce invalid values (example: sin(x : ff32) naturally produces ff32) and maybe it would not require that many operations where the compiler cannot exclude invalid values (in that case a panic would may still be acceptable). I’m asking because I’ve always wondered why programming languages do not offer types for positive floats or [0.0, 1.0] floats which preserve a certain number of natural operations

[kornel]

I understand your usecase but I suppose me and other people here consider that your proposition for fixing this issue is not satisfying.

Are you referring to the proposition that NaN/Inf is caught via debug assertions and in release mode it’s left up to programmer not to produce these values?

is that really impossible for the cases you’re mentioning to create a numeric type (let’s call it for example ff32) that really excludes NaN and Inf ?

It is possible, and often it is done: via fixed-point arithmetic.

However, floats are usually more convenient to use: f32 has plenty of precision, and the “floating” part is perfect for linear light. OTOH u16.16 while sufficient, requires care and converting to u32, u48.16, etc. Most CPUs also happen to have separate integer and float ALUs, so an algorithm that’s part integer part float may use the CPU fully and end up faster than purely-integer algorithm.

[johannesvollmer]

Basically as I see NaN, it is nothing but an internal None value for floating point types

A C/C++ programmer would defend nullptr using the same argument, but I think we all agree on Option<T> being more ergonomic than nullptr.

Nan bugs could be prevented the same way that nullptr bugs are prevented, possibly by creating a method called try_div(f64) -> Option<f64>, and making the /-operator panic when the argument is zero, while statically garuanteeing that safe code cannot produce nan values for f64. Just as an example, of course. One could also introduce a new enumeration that also includes infinity instead of using the Option enum.

[gbutler]

Is UB allowed to exist in unsafe code as it is today?

No. UB in Unsafe code is not holding up the contract. “unsafe” is a promise by the developer to the compiler that even though the compiler can’t verify it, the developer has promised to uphold the necessary invariants and contracts to ensure no UB is created.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.