search

makerdao / univ2-lp-oracle

GNU Affero General Public License v3.0
23 stars 13 forks source link

CVF-32: Improve gas of sqrt function #33

Closed WilfredTA closed 3 years ago

WilfredTA commented 3 years ago

This changes the sqrt function to the one recommended by ABDK: https://github.com/abdk-consulting/abdk-libraries-solidity/blob/master/ABDKMath64x64.sol#L687-L709

kmbarry1 commented 3 years ago

So, pretty much all my code comments here are nits relating to spacing or minor typos.

As far as content--very nice use of the dapptools fuzzing :). I was a little curious how things looked at values < WAD or that just weren't even multiples of WAD, so I spent some time generating cases in other ranges--looks like equality holds across the board. The gas advantage starts to go away at low values, and even disappears in some cases--largest number I found for which the un-optimized method has lower gas was 261. So basically irrelevant in practice, and the savings is huge in % terms for the magnitudes we'll care about.

I also stared at the code for a while to the point where I convinced myself it made sense (it's also doing the Babylonian method, with a clever way to pick the starting guess and a hardcoded number of iterations chosen based on the quadratic convergence of the algorithm).

So, based on that + the work you've done here, I'm in favor to officially adopt this new implementation.

WilfredTA commented 3 years ago

Yes, I had a similar finding. While the ABDK method gets better gas even at small values > 261, the 4X difference doesn't occur until close to WAD

WilfredTA commented 3 years ago

So, pretty much all my code comments here are nits relating to spacing or minor typos.

As far as content--very nice use of the dapptools fuzzing :). I was a little curious how things looked at values < WAD or that just weren't even multiples of WAD, so I spent some time generating cases in other ranges--looks like equality holds across the board. The gas advantage starts to go away at low values, and even disappears in some cases--largest number I found for which the un-optimized method has lower gas was 261. So basically irrelevant in practice, and the savings is huge in % terms for the magnitudes we'll care about.

I also stared at the code for a while to the point where I convinced myself it made sense (it's also doing the Babylonian method, with a clever way to pick the starting guess and a hardcoded number of iterations chosen based on the quadratic convergence of the algorithm).

So, based on that + the work you've done here, I'm in favor to officially adopt this new implementation.

After further experimentation, I've found that the superiority of one over the other varies for small numbers.

E.g., the old method performs better when calculating the square root of 62 and 125, but the new method is better when calculating the square root of 94.

However, for numbers > WAD, the ABDK method consistently uses 3 to 4 times less gas.