Optimize powApprox

[Thunnini]

Currently powApprox under gamm/keeper/math.go is using a lot of resources. BenchmarkPow() test will measure the performance of the function. I’m ran 10 small pows on my MBP(2018/2.3GHz 8 Core i9/16GB RAM) and this was the result I got:

go test -bench . -benchmem -cpu 1,2,4,8,16

goos: darwin
goarch: amd64
pkg: github.com/c-osmosis/osmosis/x/gamm/keeper
BenchmarkPow                  25          51252602 ns/op        30098473 B/op     898416 allocs/op
BenchmarkPow-2                26          46804606 ns/op        30099396 B/op     898423 allocs/op
BenchmarkPow-4                24          46385548 ns/op        30100596 B/op     898430 allocs/op
BenchmarkPow-8                24          45494231 ns/op        30102812 B/op     898441 allocs/op
BenchmarkPow-16               25          45395677 ns/op        30106263 B/op     898449 allocs/op
PASS

Because multithreading is not used, the number of CPU cores shouldn’t matter, but it does require a lot of memory space and allocation.

Currently, the function is used to find a rational number exponent of a rational number. However, this seems to require too many loops so speed and memory becomes an issue.

The current implementation uses an expanded recursion function to find the binomial series so using multithreading will be difficult.

As for the memory, Cosmos-SDK’s sdk.Dec is immutable so it’s safer to use, but requires memory allocation every single time so it uses a lot of memory. To run some tests on the benefits, I’ve created a temporary mutable dec type under the gamm-math-perf branch.

The following are the results:

goos: darwin
goarch: amd64
pkg: github.com/c-osmosis/osmosis/x/gamm/keeper
BenchmarkPow                  40          29956045 ns/op         3770156 B/op     171524 allocs/op
BenchmarkPow-2                39          28767250 ns/op         3770280 B/op     171525 allocs/op
BenchmarkPow-4                40          28282755 ns/op         3770435 B/op     171526 allocs/op
BenchmarkPow-8                40          28204827 ns/op         3770722 B/op     171527 allocs/op
BenchmarkPow-16               40          28658882 ns/op         3771151 B/op     171528 allocs/op
PASS

It seems like memory allocation and memory use has definitely decreased. So the speed is a bit faster. But using a mutable dec will require extra caution, and because it’s different from Cosmos-SDK’s sdk.Dec each must be managed separately and must be well checked for bugs.

Pros:

• Memory usage, memory allocation decreased. Improved performance in calculation.

Cons:

• Must use a separate mutable dec, and not sdk.Dec -> may have bugs.

[sunnya97]

@ValarDragon thoughts?

[ValarDragon]

I'm strongly in favor of a mutable decimal. However I think in the end-state, we shouldn't be making a new type, but instead be adding in_place operations to the existing Dec implementation.

I am in favor of adding a MutativeDec type for now though.

[ValarDragon]

I also think theres a lot we can do to just have faster code for expected "normal" exponents we'll run into.

[ValarDragon]

I'm also generally very unconvinced about the quality of the current binomial approximation we use (which is identical to what is in balancer). I think post-launch we should be looking into precomputed table based methods

[sunnya97]

Should this be #post-launch?

[ValarDragon]

Yeah, but we should probably do it soon after launch, since this does control the gas of the chain. (We can build this as a non-state breaking update anyway).

The #62 approach is complementary, and gets us more for the common use cases.