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:
|
// 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?
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 twoSpans intersect, where aSpanis represented with twoRatio<i64>s. This implementation involves 3 comparisons: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
Ordimpl forRatio<T>does some division:num-rational/src/lib.rs
Lines 333 to 389 in a3d5ece
Solution?
A couple of comments mention that a more efficient implementation might first attempt a checked multiplication as "comparing
a/bandc/dis the same as comparinga*dandb*c".The inline comment implies that, at the time of implementing
Ord, aCheckedMultrait 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
CheckedMulconstraint to theOrdimplementation is a breaking change, specifically for folks usingRatio<T>whereTis some custom newtype that doesn't happen to implementCheckedMul.Do we have a branch for a hypothetical upcoming 0.5 release yet? Or should a PR go up against
master?