Hacker News Reader

Comment by shepmaster | Hacker News Reader

> the escape hatch suggested on the internet, `partial_cmp(...).unwrap_or(Ordering::Less)`

This is often a Bad Idea, as you get unstable sorts and you are right back to the same problem.

- Explanation: How do I get the minimum or maximum value of an iterator containing floating point numbers? — https://stackoverflow.com/a/50308360/155423

- Example: https://play.integer32.com/?version=stable&mode=debug&editio...

See also:

- How to do a binary search on a Vec of floats? — https://stackoverflow.com/q/28247990/155423

Instead, use a wrapper type or raise a panic.

View on HN

OP here -- this post is pretty dated. I currently use the OrderedFloat [1] crate to solve this problem which works quite well and plays nicely with NaN

https://crates.io/crates/ordered-float

To me this feels quite pedantic. Being able to do less than on NaNs and just having it do something vaguely sensible (as in your linked solution) is a far more common requirement than need to handle NaNs specially.

You could even say the reason NaN exists is so that you don't have to check for NaN constantly. Rust is being technically correct but practically really annoying, for basically no benefit.

For what it's worth, many in the Rust community agree with you. Many people consider this a mistake, in hindsight, though not everyone.

Isn't there a default total order for floats? E.g. -Inf < -1.0 < -0.0 < 0.0 < 1.0 < Inf < NaN?

Yes, there is: https://en.wikipedia.org/wiki/IEEE_754#Total-ordering_predic...

It is not something to use by default though. It is implemented in software and thus a lot slower than the hardware comparison.

I'm curious as to why it isn't implemented in hardware. Is it really so rare to need to sort floats, or so common to need a different ordering when you do?

Of course sorting floats happens a lot. In practice one rarely encounters NaN's and ±Inf's, so fast comparison for concrete values is the default. I don't know why the 'slow' total order is not implemented in hardware though.

But fortunately in comparison sort algorithms that run in O(n lg n) you can get away with doing an O(n) partitioning of the array into [-, +, NaN] and then applying a fast integer comparison operator to the negative values (-) and positive values (+).

In fact the above idea ties in neatly with QuickSort, which is already based on partitioning & sorting recursively.

> Of course sorting floats happens a lot.

Is this true?

I am actually struggling to remember the last time I did a sort with a float/double as the key--especially in a performance bounded context

... <thinking> ...

Aha. Graphic engine. Octtree with coordinates.

I really had to think about that.

So, I'm a bit skeptical of float sorting happening a "lot".

Is this perhaps an ML primitive somewhere?

Languages that only have floats, such as JavaScript and Lua, certainly sort floats quite often.

No, because x < NaN and x > NaN are false for any value of x.

Yes, the literal < in the language induces a partial order by convention. What I'm getting at in my comment is that you can define a sensible total ordering.

The challenge becomes what code to emit when you see those operators: native target comparisons, or the software implementation of your total ordering? The latter is safe and slow and the former is fast and IMO idiomatic.

So since no one needs this often enough to emit the soft-float comparison code, we should emit the fast code. If folks need different behavior they should use different types. This is similar to the behavior with integer overflow, which you can opt into by using checked types or checked operations. Though in rust we have a convenience that the overflow-detecting code is emitted for debug targets.

It is possible to do redefine NaN as something different than what IEEE 754 contains, but it will surprising to some users, and it will come at a performance cost because you can no longer let the hardware handle all float comparisons directly.

Reply on news.ycombinator.com