User pagination is extremely gas inefficient #641
Labels
Version2
Proposals for the version 2 contract
Comments
fleupold
added a commit
to gnosis/solidity-data-structures
that referenced
this issue
Apr 8, 2020
More context: gnosis/dex-contracts#641 `size()` is currently iterating over all items making it potentially very gas costly. Since this behaviour is internal to the library it is easy for dependent contracts to oversee the consequences. This PR therefore changes the implementation so that every insert will increment the size variable. Due to the fact that the size variable is aligned (last takes 160 bits leaving 96 in the word), the amount of gas used on insertion barely changes (by measuring test suite with eth-gas-reporter): ||min|max|avg |---|---|---|--- No storage| 25713|66479|56044 U96|25469|66552|53192 U256|25469|86700|64361 I also removed the `atIndex` method as it is subject to the same flaw and therefore of questionable use anyway.
|
#647 mitigates this somewhat in the viewer by only fetching the list of users required for this page once. This allows to fetch the open orders with a page size of 1000 for now. To really fix this we need to upgrade the IterableAppendOnlySet (pending gnosis/solidity-data-structures#22) |
|
If we end up making the SPAM-rinkeby-test, I think it's best to do it in a newly deployed contract, so we don't ruin the current contract to get what's the limit. Does it make sense? |
|
Yes that makes perfect sense. |
fleupold
added a commit
that referenced
this issue
Apr 9, 2020
We currently fetch the next user "on demand" whenever we exhaust the order for the current one. #641 noticed that the act of getting a single user is querying the `size()` of the allUser struct und thus actually iterates the list of all users in the system. Consequently, getting all users is just twice as expensive as getting a single user (once for checking the size and once for getting them) mod the memory of storing them. For a single unfiltered page we can have at most `pageSize` users (a user is only in the system if they have at least on order). This PR therefore replaces the "fetch n times one user when needed" logic with "fetch once n users at the beginning" and then read the next user from that list. ### Test Plan No logic is changed (unit tests keep running). Notice, that now we can query the open orderbook with a page size of 1000 on a standard infura node: `npx truffle console --network mainnet` ```js let instance = await BatchExchangeViewer.at("0xd7a78A333BAe9AAdDD5ebE41C209Fb5226eA155B") let page = {nextPageUser: "0x0000000000000000000000000000000000000000", nextPageUserOffset:0} page = await instance.contract.methods.getOpenOrderBookPaginated([], page.nextPageUser, page.nextPageUserOffset, 1000).call() // ... continue last call until nextPage = false ```
fleupold
added a commit
to gnosis/util-contracts
that referenced
this issue
Jun 12, 2020
…all (#31) While #30 works great for reading specific one-off storage slots, it is not very convenient in case we want to add more sophisticated view function logic to an already deployed contract (e.g. to [improve gas efficiency for view functions on Gnosis Protocol](gnosis/dex-contracts#641)) This PR allows anyone to deploy a smart contract with the same storage layout as our original (StorageReading subclassed) contract and implement arbitrary view functions on it. They can then invoke `executeStaticDelegatecall` on the existing contract, which will execute **their code** in **its own context** via a delegatecall (using the state of the original contract). Whatever happens in this call is reverted in the end, making it side-effect-less (static). The return value is returned as abi-encoded bytes for easier consumption in web3 as well as other smart contracts (encoding as revert message would suffice for the latter). The cool thing is that we can even invoke methods that are non-view (i.e. have side effects) and thus simulate more complex invocations. All side effects will be reverted, the returned result remains. This is similar to the [state override feature in geth](https://geth.ethereum.org/docs/rpc/ns-eth#3-object---state-override-set) but make it client agnostic and available to other smart contracts. Credit goes to @rmeissner who wrote this code [before](https://github.com/gnosis/safe-contracts/blob/v2/contracts/base/StateProvider.sol) (I'm just making it generally accessible here) ### Test Plan Added unit test to demonstrate how a fixed contract can be amended with reader functionality.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I noticed that getting the next user via our pagination is extremely gas inefficient (currently >1M gas)
I believe the reason for this is that we call the method
size()on our IterableAppendOnlySet every time just to make sure it is not empty.dex-contracts/contracts/BatchExchange.sol
Lines 445 to 448 in b075120
The way
size()is implemented is by iterating over all items in the list visSLOAD, which becomes increasingly inefficient as our set grows (it's unbounded so at some point even a single call will exceed gas limit).We only rely on this method for our view functions (as far as I can tell, none of them are called via the solutionSubmission or orderPlacement).
We could omit the check or replace it with a check like
allUsers.last() != address(0). However, this cannot be done in the BatchExchangeViewer contract as allUsers is declared private:dex-contracts/contracts/BatchExchange.sol
Line 69 in b075120
The text was updated successfully, but these errors were encountered: