Improving performance of `Ord::cmp` for `Ratio<T>` with `CheckedMul`

[mitchmindtree]

Motivation

I'm working on a generative music project downstream (picture a DAW-like interface) that uses Ratio<i64> to represent time. One very common operation in this project is checking if two Spans intersect, where a Span is represented with two Ratio<i64>s. This implementation involves 3 comparisons:

    pub fn intersect(self, other: Self) -> Option<Self> {
        let start = std::cmp::max(self.start, other.start);
        let end = std::cmp::min(self.end, other.end);
        if end <= start {
            None
        } else {
            Some(Span { start, end })
        }
    }

When doing some profiling, I've noticed these comparisons showing up as a pretty significant bottleneck for complex compositions. Doing some digging reveals that the Ord impl for Ratio<T> does some division:

https://github.com/rust-num/num-rational/blob/a3d5ecedfe078b9779b07af5972974a885ef8920/src/lib.rs#L333-L389

Solution?

A couple of comments mention that a more efficient implementation might first attempt a checked multiplication as "comparing a/b and c/d is the same as comparing a*d and b*c".

The inline comment implies that, at the time of implementing Ord, a CheckedMul trait was not available - however now it is! https://docs.rs/num-traits/0.2.16/num_traits/ops/checked/trait.CheckedMul.html.

The problem is, adding this CheckedMul constraint to the Ord implementation is a breaking change, specifically for folks using Ratio<T> where T is some custom newtype that doesn't happen to implement CheckedMul.

Do we have a branch for a hypothetical upcoming 0.5 release yet? Or should a PR go up against master?

[cuviper]

The inline comment implies that, at the time of implementing Ord, a CheckedMul trait was not available - however now it is! https://docs.rs/num-traits/0.2.16/num_traits/ops/checked/trait.CheckedMul.html.

The problem is, adding this CheckedMul constraint to the Ord implementation is a breaking change, specifically for folks using Ratio<T> where T is some custom newtype that doesn't happen to implement CheckedMul.

Right, the comment is not about that trait existing at all, but in this specific context, as the existing bounds don't offer any checked methods. This was way back in rust-num/num#169. As you say, it's a breaking change to strengthen that, although maybe we should have added that in one of the semver bumps since then.

Do we have a branch for a hypothetical upcoming 0.5 release yet? Or should a PR go up against master?

No plans yet, but I don't think a PR is needed until we're closer to wanting that bump. This issue can remain open as a reminder, and I'll label it as a breaking change. If you'd like to work on it and push a prototype branch on your own fork, that would be fine, and that could be used for performance comparisons too.

(Also, integer division has gotten a lot better on recent CPUs, so the benefit may not be as much as it used to be.)