Improve GCD performance

[Aatch]

Rationals rely pretty heavily on the GCD for either calculating the LCM or reducing the rational. Initial benchmarks show that the GCD is a large proportion of the time for addition and subtraction of rationals.

According perf, GCD is ~90% of the time for the rationals benchmarks.

[Aatch]

Further benchmarks suggest that, currently, simply using the GCD to find a common denominator for two rationals is a major performance hit. As in, about 95% of the time taken for addition is calculating the common denominators.

[kunerd]

#15 (comment)

[andersk]

As slow as GCD may be, not using it has seriously killed the performance of repeated addition workloads like

1/3
+ 1/2 = 5/6
+ 1/2 = 16/12
+ 1/2 = 44/24
+ 1/2 = 112/48
+ 1/2 = 272/96
+ 1/2 = 640/192
+ 1/2 = 1472/384
+ 1/2 = 3328/768
+ 1/2 = 7424/1536
+ 1/2 = 16384/3072
+ 1/2 = 35840/6144
+ 1/2 = 77824/12288
+ 1/2 = 167936/24576
…
+ 1/2 = 5775854470731728332740962458894750493680245409841152/70152078591883340073776871970381584943484762062848
…

There’s a reason why GMP canonicalizes rationals after every operation. Is GCD still slow? If so, perhaps as a compromise, rational addition could check whether the larger denominator is a multiple of the smaller, rather than merely checking the denominators for equality?

[clarfonthey]

Perhaps you could go with @andersk's recommendation while also forcing GCD once the denominator gets to a certain magnitude?

[andersk]

Honestly, my first recommendation would still be to do GCD at every operation, by the same reasoning the GMP developers used. If you wait until the denominator gets big (whatever that means), then you’ve just left yourself with the work of doing an even bigger GCD, and you’ve slowed down all the intermediate operations.

Yeah, the GCD is going to make the individual “rational + rational” microbenchmark look worse, but that’s not what anyone really cares about. Real computations tend to involve long chains of operations with lots of common factors to cancel, not individual operations where the result is thrown away.

[vks]

By allowing direct access to the numerator and denominator it is possible to do the operations without simplification if required by some use case, so I don't see a reason to make this the default behavior for the multiplication of fractions.

[andersk]

@vks But it’s not as simple as “users can normalize if they want”.

1. As noted in the GMP documentation that I linked: if we know that a/b and c/d are normalized, we can normalize their product after finding just gcd(a, d) and gcd(b, c); but if we don’t have that guarantee, we instead need to find gcd(ac, bd), which takes twice as long (because doubling the input lengths to gcd quadruples its running time).

2. If I want to use a function that operates generically on T: Add<T> + Mul<T> + … instead of only on Rational, it may not be possible for that function to normalize its intermediate computations, because that isn’t a generic operation.