User pagination is extremely gas inefficient

[fleupold]

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.

https://github.com/gnosis/dex-contracts/blob/b075120c985d4ad725ab8aaf6a325500907868ca/contracts/BatchExchange.sol#L445-L448

The way size() is implemented is by iterating over all items in the list vis SLOAD, 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: https://github.com/gnosis/dex-contracts/blob/b075120c985d4ad725ab8aaf6a325500907868ca/contracts/BatchExchange.sol#L69.

[fleupold]

#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 https://github.com/gnosis/solidity-data-structures/pull/22)

[anxolin]

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?

[fleupold]

Yes that makes perfect sense.