Add small precision fast-path to Quo

[aaronc]

I've been doing some benchmarks to compare APD's performance vs other approaches we're considering (cosmos/cosmos-sdk#7772).

It seems that Quo operations perform pretty poorly compare to Add, Mul, etc.:

Benchmark/1_Ops:_apd.Decimal128.Add
Benchmark/1_Ops:_apd.Decimal128.Add-16         	 5285344	       218 ns/op
Benchmark/1_Ops:_apd.Decimal128.Sub
Benchmark/1_Ops:_apd.Decimal128.Sub-16         	 5665453	       208 ns/op
Benchmark/1_Ops:_apd.Decimal128.Mul
Benchmark/1_Ops:_apd.Decimal128.Mul-16         	 9138602	       138 ns/op
Benchmark/1_Ops:_apd.Decimal128.Quo
Benchmark/1_Ops:_apd.Decimal128.Quo-16         	  162537	      7790 ns/op

This benchmark is basically just perform a single operation on two random floating point numbers (different ones each round). I'm using a Context configured with decimal128 parameters (i.e. Precision = 34, etc.)

Is Quo inherently expected to be 40x slower than other operations or could there be a performance bottleneck?

[aaronc]

So looking at the Quo code, there are a lot of for loops. It looks like it's trying to do things digit by digit. Is this algorithm designed around cases with very large precision? What if there were a fast path for precision <= 34 (decimal128, etc.)?

I benchmarked some decimal128 code based on https://software.intel.com/content/www/us/en/develop/articles/intel-decimal-floating-point-math-library.html by the way and division is comparable to multiplication there. So it must be possible for apd to have a more efficient Quo implementation for "low" precision.

[nvanbenschoten]

Hi @aaronc, thanks for the report. Quo performance has improved recently (it's about 50% faster on your benchmark), but it still lags the performance of other operations by quite a margin. As you identified, this has to do with the digit-by-digit loop in Quo. The algorithm is designed around cases with very large precision and does not include any form of fast-path for low precision values. I'd like to keep this issue open to track the introduction of such a fast path.