Save gas and clean the upper bits of computed pool address properly #291

shuhuiluo · 2023-05-07T15:08:21Z

Refactor `_v2Swap` to resolve stack too deep error

Previously UniversalRouter can only be compiled via the IR pipeline due to the "stack too deep" error which takes a long time especially in Foundry. After refactoring _v2Swap and modifying SignatureTransfer.permitWitnessTransferFrom to

bytes32 hash = permit.hashWithWitness(witness, witnessTypeString);
_permitTransferFrom(permit, transferDetails, owner, hash, signature);

it not only saves gas but the project can also be compiled with via_ir = false which allows for faster compilation and testing

Compute v2 and v3 pool address using inline assembly and explicitly clean the upper bits

Previously the pool address was computed in pure Solidity and casted via address(uint160(uint256())). However the upper 12 bytes are not explicitly cleaned and the address is later used in solmate::SafeTransferLib.safeTransfer which is written in inline assembly. When compiled with via_ir enabled, all tests pass. However, after making the aforementioned changes, some Foundry tests failed in a ERC20.transfer with via_ir disabled. It was discovered that the dirty upper bits of pool address are the culprit, but somehow the IR pipeline may clean the address after keccak256. Nonetheless, pairForPreSorted and computePoolAddress are rewritten in inline assembly to save gas and clean the upper bits. Closes #290.

Add Uniswap v3 Foundry tests for more granular gas comparison

There weren't Uniswap v3 tests in Foundry. In order to validate gas optimizations to be made, test contracts UniswapV3Test and V3MockMock have been added. forge snapshot --diff is run after each modification to validate the gas savings.

Replace conditional statements with bitwise operations

The current Solidity optimizer isn't smart enough to reduce ternary expressions to fewer opcodes and likely translate them to JUMPI. Therefore TernaryLib utils written in inline assembly have been added to replace ternary expressions as much as possible. sortTokens is also refactored to TernaryLib but inlined where appropriate.

In general for x = y ? a : b, when y = true

x = a = 0 ^ a = b ^ b ^ a = b ^ (b ^ a) * y

When y = false

x = b = b ^ 0 = b ^ (b ^ a) * y

Therefore x = y ? a : b is equivalent to x = b ^ (b ^ a) * y according to the properties of xor.

saving 100~200 gas

…orPreSorted` and clean the upper bits explicitly saving 500~1000 gas

…lean the upper bits at the same gas

…tion since there weren't V3 Foundry tests Rewritten `computePoolAddress` saves ~500 gas

ewilz · 2023-05-08T18:10:21Z

contracts/modules/uniswap/v2/TernaryLib.sol

+
+    /// @notice Sorts two uint256 in ascending order
+    /// @dev Equivalent to: `a < b ? (a, b) : (b, a)`
+    function sort2(uint256 a, uint256 b) internal pure returns (uint256, uint256) {


Is this used anywhere?

ewilz · 2023-05-08T18:12:09Z

contracts/modules/uniswap/v2/TernaryLib.sol

+
+    /// @notice Swaps two uint256 if `condition` is true
+    /// @dev Equivalent to: `condition ? (b, a) : (a, b)`
+    function swapIf(bool condition, uint256 a, uint256 b) internal pure returns (uint256, uint256) {


since this is a swap router, swap can easily get confused here. maybe reverseOrderIf / reverseIf / switchIf / switchOrderIf

I opt for switchIf.

ewilz · 2023-05-08T18:12:40Z

contracts/modules/uniswap/v2/TernaryLib.sol

+pragma solidity >=0.5.0;
+
+/// @title Library for replacing ternary operator with efficient bitwise operations
+library TernaryLib {


slick ternary ops in here!

One function is a ternary, while the other is not. I wonder if SortLib would be more readable and make more sense?

Only sortTokens is used for sorting. But the rest of the library is meant for replacement of the built-in ternary operator.

ewilz · 2023-05-08T18:15:59Z

contracts/modules/uniswap/v2/TernaryLib.sol

+/// @title Library for replacing ternary operator with efficient bitwise operations
+library TernaryLib {
+    /// @notice Equivalent to the ternary operator: `condition ? a : b`
+    function ternary(bool condition, uint256 a, uint256 b) internal pure returns (uint256 res) {


not used anywhere either?

It was more of an illustration. Now that overloaded versions of ternary() on int256 and address are used in V3SwapRouter, should we leave this one here for completeness?

ewilz · 2023-05-08T19:59:29Z

contracts/modules/uniswap/v2/UniswapV2Library.sol

-                )
-            )
-        );
+        assembly ("memory-safe") {


I think I like the gas savings here. Wonder if it's worth a comment:

// accomplishes the following: // address(keccak256(abi.encodePacked(hex'ff', factory, keccak256(abi.encodePacked(token0, token1)), initCodeHash)))

to get a feel for what this is doing at a glance

thanks, I think that's pretty helpful for readability, one for the V3Lib would probably make sense too. (sorry, missed that)

ewilz · 2023-05-08T20:03:28Z

contracts/modules/uniswap/v3/V3SwapRouter.sol

+        assembly {
+            // amountOutReceived = uint256(-(zeroForOne ? amount1Delta : amount0Delta))
+            // no need to check for underflow
+            amountOutReceived := sub(0, xor(amount0Delta, mul(xor(amount1Delta, amount0Delta), zeroForOne)))


could these ternaries in this file get abstracted into the Library with all the xors??

Actually yes. I was afraid the optimizer wouldn't inline properly. But it seems the gas level remains the same as long as we uncheck the unary - on int256

unchecked { uint256 amountOutReceived = uint256(-zeroForOne.ternary(amount1Delta, amount0Delta)); if (amountOutReceived != amountOut) revert V3InvalidAmountOut(); }

For

hasMultiplePools ? address(this) : recipient

using hasMultiplePools.ternary(address(this), recipient) in place also saves gas due to less stack shuffling.

For zeroForOne := xor(isExactIn, lt(tokenOut, tokenIn)) though, using

zeroForOne = isExactIn.ternary(tokenIn < tokenOut, tokenOut < tokenIn);

wouldn't be cheaper. And writing zeroForOne = isExactIn ^ (tokenOut < tokenIn) isn't allowed since "Operator ^ not compatible with types bool and bool.".

Writing

sqrtPriceLimitX96 = zeroForOne.ternary(MIN_SQRT_RATIO + 1, MAX_SQRT_RATIO - 1);

instead of xor and literal hexes in assembly also wouldn't be cheaper. We could define the literal hexes as contract level constants though if that improves readability.

cool thanks for the explanation. We definitely strive to strike a balance between readability and gas savings (or else we could just write low-level code for everything :)

Even with our steepest gas savings tests, these ternaries that cannot be abstracted away would only save < 100 extra gas per full swap, So I'd personally vote to just omit them. Can always get a third opinion..

Also some context, our v2 UniversalRouter has already been audited so we cannot include this, these gas savings would go into V3 of the router.

We can always abstract them away. It will just costs a few more opcodes. I'm okay with replacing sqrtPriceLimitX96 done in assembly with literal hexes with zeroForOne.ternary(MIN_SQRT_RATIO + 1, MAX_SQRT_RATIO - 1). But frankly speaking, is

zeroForOne = isExactIn ? tokenIn < tokenOut : tokenOut < tokenIn;

more understandable and cleaner than

assembly { zeroForOne := xor(isExactIn, lt(tokenOut, tokenIn)) }

with derivations?

shuhuiluo added 7 commits May 6, 2023 00:12

Refactor _v2Swap to resolve stack too deep error

e3bf4ea

saving 100~200 gas

Compute pair address using inline assembly in `UniswapV2Library.pairF…

2b2ea49

…orPreSorted` and clean the upper bits explicitly saving 500~1000 gas

Rewrite V3SwapRouter.computePoolAddress using inline assembly and c…

8deab37

…lean the upper bits at the same gas

Run Hardhat gas snapshot to demonstrate computePoolAddress optimiza…

d16a6d9

…tion since there weren't V3 Foundry tests Rewritten `computePoolAddress` saves ~500 gas

Add Foundry test UniswapV3Test for more granular gas comparison

b3bfe32

Replace conditional statements with bitwise operations

bade844

Uncheck loop index

bc568ac

shuhuiluo changed the title ~~Gas savings~~ Save gas and clean the upper bits of computed pool address properly May 8, 2023

ewilz reviewed May 8, 2023

View reviewed changes

shuhuiluo added 3 commits May 8, 2023 19:48

Refactor to address comments

65cad3d

Improve readability

68baa9c

Further optimize pool address calculation

1ff67ff

shuhuiluo mentioned this pull request Jun 16, 2023

Optimize SqrtPriceMath Uniswap/v4-core#258

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Save gas and clean the upper bits of computed pool address properly #291

Save gas and clean the upper bits of computed pool address properly #291

shuhuiluo commented May 7, 2023

ewilz May 8, 2023

shuhuiluo May 9, 2023

ewilz May 8, 2023

shuhuiluo May 9, 2023

ewilz May 8, 2023

ewilz May 8, 2023

shuhuiluo May 9, 2023

ewilz May 8, 2023

shuhuiluo May 9, 2023

ewilz May 8, 2023 •

edited

Loading

shuhuiluo May 9, 2023

ewilz May 10, 2023

shuhuiluo May 10, 2023

ewilz May 8, 2023

shuhuiluo May 9, 2023

ewilz May 10, 2023 •

edited

Loading

shuhuiluo May 10, 2023

Save gas and clean the upper bits of computed pool address properly #291

Are you sure you want to change the base?

Save gas and clean the upper bits of computed pool address properly #291

Conversation

shuhuiluo commented May 7, 2023

Refactor _v2Swap to resolve stack too deep error

Compute v2 and v3 pool address using inline assembly and explicitly clean the upper bits

Add Uniswap v3 Foundry tests for more granular gas comparison

Replace conditional statements with bitwise operations

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ewilz May 8, 2023 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ewilz May 10, 2023 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Refactor `_v2Swap` to resolve stack too deep error

ewilz May 8, 2023 •

edited

Loading

ewilz May 10, 2023 •

edited

Loading