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:

num-rational/src/lib.rs

Lines 333 to 389 in a3d5ece

	// Comparisons
	// Mathematically, comparing a/b and c/d is the same as comparing a*d and b*c, but it's very easy
	// for those multiplications to overflow fixed-size integers, so we need to take care.
	impl<T: Clone + Integer> Ord for Ratio<T> {
	#[inline]
	fn cmp(&self, other: &Self) -> cmp::Ordering {
	// With equal denominators, the numerators can be directly compared
	if self.denom == other.denom {
	let ord = self.numer.cmp(&other.numer);
	return if self.denom < T::zero() {
	ord.reverse()
	} else {
	ord
	};
	}
	// With equal numerators, the denominators can be inversely compared
	if self.numer == other.numer {
	if self.numer.is_zero() {
	return cmp::Ordering::Equal;
	}
	let ord = self.denom.cmp(&other.denom);
	return if self.numer < T::zero() {
	ord
	} else {
	ord.reverse()
	};
	}
	// Unfortunately, we don't have CheckedMul to try. That could sometimes avoid all the
	// division below, or even always avoid it for BigInt and BigUint.
	// FIXME- future breaking change to add Checked* to Integer?
	// Compare as floored integers and remainders
	let (self_int, self_rem) = self.numer.div_mod_floor(&self.denom);
	let (other_int, other_rem) = other.numer.div_mod_floor(&other.denom);
	match self_int.cmp(&other_int) {
	cmp::Ordering::Greater => cmp::Ordering::Greater,
	cmp::Ordering::Less => cmp::Ordering::Less,
	cmp::Ordering::Equal => {
	match (self_rem.is_zero(), other_rem.is_zero()) {
	(true, true) => cmp::Ordering::Equal,
	(true, false) => cmp::Ordering::Less,
	(false, true) => cmp::Ordering::Greater,
	(false, false) => {
	// Compare the reciprocals of the remaining fractions in reverse
	let self_recip = Ratio::new_raw(self.denom.clone(), self_rem);
	let other_recip = Ratio::new_raw(other.denom.clone(), other_rem);
	self_recip.cmp(&other_recip).reverse()
	}
	}
	}
	}
	}
	}

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.)