ACP: Add `fN::ordinal`

Proposal

Problem statement

Sorting a slice of floats or of structs containing floats is rather painful because floats are not Ord and so the slice::sort functions can not be used naively. The standard way to work around this requires more code and also turns out to be slower than necessary.

Motivating examples or use cases

The current solution is to use fN::total_cmp with slice::sort_by (or sort_unstable_by), e.g.

let v = &mut [f32::NAN, 4., f32::INFINITY, -2., f32::MIN, -0.];
v.sort_by(f32::total_cmp);

which is fine, albeit slower than necessary, as I will discuss later. But already in the case where you want to sort in reverse order, the code becomes quite a bit longer, because you have to write a closure:

v.sort_by(|a, b| a.total_cmp(&b).reverse());

If your slice contains structs where the float is possibly deeply nested, the code starts becoming rather ugly:

v.sort_by(|a, b| a.foo.bar.total_cmp(&b.foo.bar));

You end up having to repeat the same fields twice, which is more error-prone.
The case where you want to compare multiple fields in order (one of them being a float) is even more complicated because you can't #[derive(Ord)], so you either have to manually implement it (and PartialCmp and PartialEq and Eq because they all have to agree with each other) or write a complicated closure:

v.sort_by(|a, b| a.int.cmp(&b.int).then(a.float.total_cmp(&b.float)));

Though solving this is not necessarily best achieved by this proposal (you probably want a separate OrderedFloat type, which I will talk about in the Alternatives section), it is possible to work around this using fN::ordinal.

I also quickly want to mention the slice::sort_floats functions, which, it seems, will not be stabilized, because something like OrderedFloat is preferred. Even if these functions were added, they are currently only for the ascending sort, and only when the slice elements are floats and not a float inside a struct which you'd want to sort by. They are just implemented as sort_unstable_by(f32::total_cmp).

Solution sketch

I propose adding the following functions:

impl fN {
    /// Returns a signed integer such that the signed integer comparison agrees with `fN::total_cmp`,
    /// i.e. `a.ordinal().cmp(&b.ordinal()) == a.total_cmp(&b)`.
    pub fn ordinal(self) -> iN {
        let bits = self.to_bits() as iN;
        bits ^ (((bits >> (N - 1)) as uN) >> 1) as iN
    }

    /// Reconstructs the floating point number from its ordinal. See [`fN::ordinal`].
    fn from_ordinal(ordinal: iN) -> fN {
        fN::from_bits(ordinal as uN ^ (((ordinal >> (N - 1)) as uN) >> 1))
    }
}

(The comments should probably be expanded, and I am not dead set on the name ordinal, although I think it describes it well.)
Looking at the implementation of fN::total_cmp, it is clear where this comes from. total_cmp is, in terms of ordinal, literally implemented as a.ordinal().cmp(&b.ordinal()), so, should this be added, that implementation should probably be changed too.

What this buys us in terms of the previous examples, is that we no longer have to explicitly address both arguments of the comparison, and can instead use the by_key sorting functions.
For the simplest of cases, this is actually just worse (more characters), because fN::ordinal takes self instead of &self (in order to be consistent with the other functions on the float types), so we can't just pass it to sort_by_key and have to create a closure instead:

v.sort_by_key(|f| f.ordinal());

For the reversed sort it is shorter (assuming std::ord::Reversed is in scope):

v.sort_by_key(|f| Reversed(f.ordinal()));

Note that it's not possible to use

v.sort_by_key(|f| -f.ordinal());

because the negation overflows when the ordinal is iN::MIN, which corresponds to some NaN.
If I am reading the rules around NaN correctly (in particular that - is guaranteed to just change the sign bit), I think this should work though:

v.sort_by_key(|f| (-f).ordinal());

which is even shorter than the Reversed.

When you want to compare some field, it starts being shorter by a lot and we don't have to repeat the same fields twice:

v.sort_by_key(|s| s.foo.bar.ordinal());

From a performance perspective, these two approaches are of course equivalent. They should ideally compile to the same machine code. And I will show a benchmark at the end where they run equally fast.

However, you can pre-compute or cache the ordinal to avoid recomputing it for each comparison.
This can take several shapes:

You can use the ordinal with sort_by_cached_key, which will automatically cache it:

v.sort_by_cached_key(|f| f.ordinal());

However, this is a bad idea and almost always the slowest way to sort, because it:

• allocates a Vec with (cached_key, index) entries
• sorts that (which involves comparing pairs)
• reorders the elements in the original slice

ordinal or total_cmp are fast enough (ordinal is 3-5 instructions on x86 depending on what you count) for that extra work to never be worth it in my benchmarks.

But if the key you want to sort by is the result of some computation, (e.g. you want to sort n-dimensional vectors by length or by distance or dot product with another fixed vector), you would want to cache the key regardless. And currently you would have to essentially re-implement sort_by_cached_key because that function requires keys to be Ord, whereas with ordinal you can write:

v.sort_by_cached_key(|v| (v.x * v.x + v.y * v.y).ordinal());

Another way in which this can be useful, is if you want to sort by a more complicated composite key (e.g. a tuple where one of the elements is a float), or you have a struct where a float member is mostly used for comparisons. In those cases you can consider storing the ordinal in the key/struct. In the example from above, we were forced to write

v.sort_by(|a, b| a.int.cmp(&b.int).then(a.float.total_cmp(&b.float)));

With ordinal we can do this:

v.sort_by_key(|a| (a.int, a.float.ordinal());

Or, when you almost exclusively use a float in a struct for comparisons, you can consider storing the ordinal instead, which allows you to derive Ord:

#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct S {
    int: i32,
    float_ordinal: i32,
}

Note that the ordinal function is bijective, i.e. we can go back from an ordinal to the float. (It is, ignoring the types and only looking at the bits, its own inverse.)
So you can actually store the ordinal in your struct, sort, and then get back the original float at the end.
This turns out to be the fastest way to sort a slice of floats with more than 4 elements according to my benchmark:

fn sort_floats(v: &mut [fN]) {
    // Interpret the floats as integers. At this point they are not yet ordinals.
    let ordinals = unsafe {
        std::slice::from_raw_parts_mut(v.as_mut_ptr() as *mut iN, v.len())
    };

    // Turn the bits of a float into an ordinal.
    fn float_ordinal(bits: &mut iN) {
        *bits ^= ((*bits >> (N - 1)) as uN >> 1) as iN
    }

    // Convert all floats to ordinals.
    ordinals.iter_mut().for_each(float_ordinal);

    // Do the sort.
    ordinals.sort_unstable();

    // Turn the ordinals back into floats.
    ordinals.iter_mut().for_each(float_ordinal);
}

I'm not proposing we add this to the standard library with this proposal (although I do think it would be nice to have an efficient way to sort a slice of floats in the standard library), because there are some unanswered questions here. Of course, there is already the unstable slice::sort_floats which this could replace, but there were a bunch of questions there too, which meant it ended up in unstable limbo. I also don't like that this function as written can not easily be used to sort in descending order, or sort a slice of (say) structs by some float key. These use cases could be supported with a more complicated version of the function, but I'm not exactly sure what it should look like, so I'd rather write a separate proposal, should the ordinal function be added.

Benchmarks

use rand::{RngExt, SeedableRng, rngs::StdRng};

fn ordinal(f: f32) -> i32 {
    let bits = f.to_bits() as i32;
    bits ^ ((bits >> 31) as u32 >> 1) as i32
}

fn sort_total_cmp(v: &mut [f32]) {
    v.sort_unstable_by(f32::total_cmp);
}

fn sort_total_cmp_stable(v: &mut [f32]) {
    v.sort_by(f32::total_cmp);
}

fn sort_by_key(v: &mut [f32]) {
    v.sort_unstable_by_key(|f| ordinal(*f));
}

fn sort_by_key_stable(v: &mut [f32]) {
    v.sort_by_key(|f| ordinal(*f));
}

fn sort_by_cached_key(v: &mut [f32]) {
    v.sort_by_cached_key(|f| ordinal(*f));
}

fn sort_mutate(v: &mut [f32]) {
    let ordinals = unsafe {
        std::slice::from_raw_parts_mut(v.as_mut_ptr() as *mut i32, v.len())
    };

    fn float_ordinal(bits: &mut i32) {
        *bits ^= ((*bits >> 31) as u32 >> 1) as i32
    }

    ordinals.iter_mut().for_each(float_ordinal);
    ordinals.sort_unstable();
    ordinals.iter_mut().for_each(float_ordinal);
}

fn sort_mutate_stable(v: &mut [f32]) {
    let ordinals = unsafe {
        std::slice::from_raw_parts_mut(v.as_mut_ptr() as *mut i32, v.len())
    };

    fn float_ordinal(bits: &mut i32) {
        *bits ^= ((*bits >> 31) as u32 >> 1) as i32
    }

    ordinals.iter_mut().for_each(float_ordinal);
    ordinals.sort();
    ordinals.iter_mut().for_each(float_ordinal);
}

struct Sort {
    name: &'static str,
    f: fn(&mut [f32]),
    duration: std::time::Duration,
}

macro_rules! sort {
    ($f:ident) => {
        Sort {
            name: stringify!($f),
            f: $f,
            duration: Default::default(),
        }
    }
}

fn bench(len: usize, print: bool) {
    let iters = if len <= 100 {
        100_000
    } else if len <= 10_000 {
        10_000
    } else if len <= 100_000 {
        1_000
    } else {
        100
    };

    let mut sorts = [
        sort!(sort_total_cmp),
        sort!(sort_total_cmp_stable),
        sort!(sort_by_key),
        sort!(sort_by_key_stable),
        sort!(sort_by_cached_key),
        sort!(sort_mutate),
        sort!(sort_mutate_stable),
    ];

    let mut rng = StdRng::seed_from_u64(0);
    for i in 0..iters + 10 {
        // Re-using the same array for all comparisons seems to heavily favor the later ones.
        // Especially the first one is always quite a bit slower than it otherwise would be,
        // so we generate a new random vector for each sort.
        // let mut v = Vec::new();
        // for _ in 0..len {
        //     v.push(f32::from_bits(rng.random()));
        // }

        // let mut last: Option<Vec<f32>> = None;

        for sort in std::hint::black_box(&mut sorts) {
            // let mut l = v.clone();
            let mut l = Vec::new();
            for _ in 0..len {
                l.push(f32::from_bits(rng.random()));
            }
            let start = std::time::Instant::now();
            std::hint::black_box(sort.f)(std::hint::black_box(&mut l));

            // 10 warmup iterations. Can't hurt.
            if i >= 10 {
                sort.duration += start.elapsed();
            }

            // if let Some(last) = last.as_ref() {
            //     assert!(last.iter().zip(&l).all(|(a, b)| a.to_bits() == b.to_bits()));
            // }

            // last = Some(l);
        }
    }

    if print {
        println!("Sorting {len} floats {iters} times took:");
        for sort in &sorts {
            println!("{:32}: {:.4}ms", sort.name, sort.duration.as_secs_f64() * 1000.);
        }
        println!();
    }
}

fn main() {
    // Get the CPU running.
    bench(1_000_000, false);

    for len in [0, 1, 2, 3, 4, 5, 6, 7, 8, 16, 32, 64, 256, 1_000, 10_000, 100_000, 1_000_000] {
        bench(len, true);
    }
}

Sorting 0 floats 100000 times took:
sort_total_cmp                  : 1.6655ms
sort_total_cmp_stable           : 1.6615ms
sort_by_key                     : 1.6632ms
sort_by_key_stable              : 1.6648ms
sort_by_cached_key              : 1.6880ms
sort_mutate                     : 1.6531ms
sort_mutate_stable              : 1.6474ms

Sorting 1 floats 100000 times took:
sort_total_cmp                  : 1.6657ms
sort_total_cmp_stable           : 1.6664ms
sort_by_key                     : 1.6654ms
sort_by_key_stable              : 1.6675ms
sort_by_cached_key              : 1.6825ms
sort_mutate                     : 1.7378ms
sort_mutate_stable              : 1.7390ms

Sorting 2 floats 100000 times took:
sort_total_cmp                  : 1.9272ms
sort_total_cmp_stable           : 1.9542ms
sort_by_key                     : 1.9094ms
sort_by_key_stable              : 1.9135ms
sort_by_cached_key              : 2.6262ms
sort_mutate                     : 2.0303ms
sort_mutate_stable              : 2.0657ms

Sorting 3 floats 100000 times took:
sort_total_cmp                  : 2.3330ms
sort_total_cmp_stable           : 2.3581ms
sort_by_key                     : 2.3363ms
sort_by_key_stable              : 2.3319ms
sort_by_cached_key              : 3.1930ms
sort_mutate                     : 2.4578ms
sort_mutate_stable              : 2.4715ms

Sorting 4 floats 100000 times took:
sort_total_cmp                  : 2.8769ms
sort_total_cmp_stable           : 3.0534ms
sort_by_key                     : 3.0421ms
sort_by_key_stable              : 2.9819ms
sort_by_cached_key              : 3.8364ms
sort_mutate                     : 3.0700ms
sort_mutate_stable              : 3.0325ms

Sorting 5 floats 100000 times took:
sort_total_cmp                  : 3.8410ms
sort_total_cmp_stable           : 3.9940ms
sort_by_key                     : 3.9499ms
sort_by_key_stable              : 3.9351ms
sort_by_cached_key              : 4.8907ms
sort_mutate                     : 3.6931ms
sort_mutate_stable              : 3.5500ms

Sorting 6 floats 100000 times took:
sort_total_cmp                  : 4.4083ms
sort_total_cmp_stable           : 4.6720ms
sort_by_key                     : 4.6029ms
sort_by_key_stable              : 4.6249ms
sort_by_cached_key              : 5.9629ms
sort_mutate                     : 4.3830ms
sort_mutate_stable              : 4.1931ms

Sorting 7 floats 100000 times took:
sort_total_cmp                  : 5.3000ms
sort_total_cmp_stable           : 5.4503ms
sort_by_key                     : 5.3761ms
sort_by_key_stable              : 5.3926ms
sort_by_cached_key              : 8.4633ms
sort_mutate                     : 5.0188ms
sort_mutate_stable              : 4.8659ms

Sorting 8 floats 100000 times took:
sort_total_cmp                  : 6.2851ms
sort_total_cmp_stable           : 6.3080ms
sort_by_key                     : 6.2645ms
sort_by_key_stable              : 6.2344ms
sort_by_cached_key              : 10.1925ms
sort_mutate                     : 5.4894ms
sort_mutate_stable              : 5.5380ms

Sorting 16 floats 100000 times took:
sort_total_cmp                  : 13.5831ms
sort_total_cmp_stable           : 13.4685ms
sort_by_key                     : 13.5042ms
sort_by_key_stable              : 13.4946ms
sort_by_cached_key              : 21.0543ms
sort_mutate                     : 11.2012ms
sort_mutate_stable              : 10.9114ms

Sorting 32 floats 100000 times took:
sort_total_cmp                  : 35.3752ms
sort_total_cmp_stable           : 24.9602ms
sort_by_key                     : 34.7284ms
sort_by_key_stable              : 24.8534ms
sort_by_cached_key              : 37.0610ms
sort_mutate                     : 13.9159ms
sort_mutate_stable              : 21.5260ms

Sorting 64 floats 100000 times took:
sort_total_cmp                  : 70.7529ms
sort_total_cmp_stable           : 59.0248ms
sort_by_key                     : 69.5626ms
sort_by_key_stable              : 59.1163ms
sort_by_cached_key              : 75.9287ms
sort_mutate                     : 29.9551ms
sort_mutate_stable              : 48.2254ms

Sorting 256 floats 10000 times took:
sort_total_cmp                  : 29.2315ms
sort_total_cmp_stable           : 23.7030ms
sort_by_key                     : 29.2044ms
sort_by_key_stable              : 23.6405ms
sort_by_cached_key              : 31.4903ms
sort_mutate                     : 12.8505ms
sort_mutate_stable              : 20.8894ms

Sorting 1000 floats 10000 times took:
sort_total_cmp                  : 120.5222ms
sort_total_cmp_stable           : 100.6452ms
sort_by_key                     : 120.5268ms
sort_by_key_stable              : 99.5727ms
sort_by_cached_key              : 125.7928ms
sort_mutate                     : 54.6148ms
sort_mutate_stable              : 87.9289ms

Sorting 10000 floats 10000 times took:
sort_total_cmp                  : 1327.4152ms
sort_total_cmp_stable           : 1131.5475ms
sort_by_key                     : 1328.1386ms
sort_by_key_stable              : 1125.5843ms
sort_by_cached_key              : 1419.3393ms
sort_mutate                     : 635.6373ms
sort_mutate_stable              : 997.2769ms

Sorting 100000 floats 1000 times took:
sort_total_cmp                  : 1452.6490ms
sort_total_cmp_stable           : 1237.1462ms
sort_by_key                     : 1451.2857ms
sort_by_key_stable              : 1233.1472ms
sort_by_cached_key              : 1601.8738ms
sort_mutate                     : 719.2545ms
sort_mutate_stable              : 1085.2351ms

Sorting 1000000 floats 100 times took:
sort_total_cmp                  : 1562.0894ms
sort_total_cmp_stable           : 1336.9514ms
sort_by_key                     : 1562.4168ms
sort_by_key_stable              : 1336.4100ms
sort_by_cached_key              : 1846.8120ms
sort_mutate                     : 800.1597ms
sort_mutate_stable              : 1178.5108ms

Let me start with the expected results:
Sorting with total_cmp or ordinal are equally fast. sort_by_cached_key is basically always the slowest, except for len == 1, where it is faster than the mutating sorts, which could be improved by simply adding an early return when len <= 1. Starting at 5 elements, the mutating sorts are always the fastest.

What I didn't expect is that starting somewhere between 16 and 32 elements, the stable sorts are clearly outperforming the unstable sorts when the ordinal is computed during the comparison, whereas for the mutating sort, the unstable variant starts to clearly outperform the stable variant. Without having looked at it too deeply, my guess is that the unstable variant performs more comparisons while saving memory, whereas the stable variant does the opposite, and even for this relatively cheap comparison function, the difference is clearly visible. When the comparison function is only an integer comparison as in the mutating sort, we see the opposite.

It would be interesting to see if these results hold for other architectures/hardware configurations.

Alternatives

Implementing it in a crate

The reason that I think it belongs in the standard library is because it complements nicely with the already existing total_cmp function (the implementation of which can then be simplified). It is also a rather small change that feels tied to the existing data type. Implementing this in a crate would either mean adding a trait which would then have to be imported whenever you want to use this, or you would have to call it like this float_to_ordinal(f).

Adding an OrderedFloat type

You would get the same benefit of being able to use the by_key functions for sorting.
I believe an OrderedFloat type should probably be added, but that doesn't mean that this can't exist too:
When computing the ordinal in the closure passed to sort_by_key, they do end up being essentially the same, i.e. we compute the ordinal for each float for each comparison, but they do behave differently when stored. OrderedFloat has the same data layout as the underlying float, which means it could support all the typical floating point type functions, but for Ord, it would have to compute the ordinal each time, whereas the ordinal does not require any additional computation for comparisons. A more practical benefit is that the ordinal change is just a couple of lines of code, so it could probably be added a lot sooner, whereas the OrderedFloat requires implementing a bunch of traits and potentially all the floating point functions. And of course, ordinal can be used in the implementation of OrderedFloat and of the faster sort, should that also be added.

Making the ordinal its own type

We could add a FloatOrdinal type (or a type for each floating point type) and return that instead of the integer type. It would signify what the integer represents, we could add a to_float function that does the inverse, and we probably wouldn't implement the normal integer operations on it, because most of them are meaningless. E.g. multiplying an ordinal with an integer is probably a mistake that the type could prevent. Ultimately, the question is whether the added complexity of a different type is worth it. I think it isn't. The bugs this could prevent are probably rather unrealistic, and fN::from_ordinal is a fine way to compute the inverse.

Links and related work

fN::total_cmp implementation
slice::sort_floats issue

Start with the linked implementation of f32::total_cmp in library/core/src/num/f32.rs and review the proposed ordinal/from_ordinal API against the sorting examples and issue 93396. Check the benchmark code in the proposal and existing float behavior, then document a settled API design and validation plan before implementation.