1

I realise looping is an anti-pattern, but I can't see a way round it.

I'm maintaining an ordered list of addresses in a mapping. Separately there is a mapping of addresses to struct where I keep the information. I'm keeping price and quantity, these values can be changed by the users.

The address list is ordered by price. That's fine, I pass in a start_address with the contract call, so it doesn't have to work the whole list to find the position of the new addition.

However, I also need to know the price at a certain cumulative quantity. The only way as far as I can tell is to iterate down the list summing the quantity on each record until I hit the cumulative quantity.

If anyone can see a way round that I would sure like to hear it.

More generally however, how many loop iterations is reasonable in solidity?

I could set a limit on the number of entries, but I have no clue what is ok - 1000, ten thousand, a million?

1

First of all, if you use loops inside read-only functions (most likely "view" functions), which get invoked by a message call, no gas is consumed and therefore you don't really have to care about the iteration count (note though that nodes can suspend your request if it takes too long). Keep in mind that this only applies if no transaction is sent and consequently the ethereum node only locally executes your request. If a transaction is sent and this function is invoked (even indirectly through other contracts), you have to think about how to limit your loop.

You cannot simply choose an iteration count as a limit, that is not enough.

Take this example: You have 10,000 loop iterations and the execution of the code inside the loop costs in every occasion

a) 10 gas

b) 1000 gas

For a you pay 10,000 gas, for b you pay 1,000,000 gas. As you can see the difference between a and b in total gas cost for the execution of the loop is a factor of 100. So the cost depends on the iteration_count and the gas cost per iteration. Therefore the cost of your loop is iteration iteration_count * gas. Since the gas cost can vary, you should write it as a sum of the gas cost for each specific iteration.

Now we face some problems. First of all, how do we know how much gas your loop consumes? Second, the gas consumption will most likely not be a constant for each iteration. Last, how much gas are we able to consume?

You can find out how much gas your loops consume in worst case by finding out which Operations the EVM executes within the loops in worst case, looking up the opcode cost (in gas) in the yellowpaper and creating the sum of those costs. A problem with this strategy is that you have to know which opcodes are being used and that is nothing that you decide in the usual case, since you use a high level language like solidity which ultimately gets compiled to low level EVM opcodes. You could take the opcodes after compilation, find out which opcodes correspond to your for loop, and finally calculate the cost. This is very cumbersome to do. Luckily you can use remix to calculate the gas cost for you or you could write your own benchmark. Nevertheless you have to think about how to produce the worst case. Using the worst case gas cost per iteration should keep you on the safe side when calculating the maximum iteration count, but this estimation will result in too high values in almost every case.

Another more powerful and accurate strategy would be to create multiple benchmarks where you collect data about how much every iteration costs (in different situations) and finally use statistics on it. The easiest variant would be to calculate the mean, although it may not be sufficient in some corner cases.

If you finally know the estimated gas cost per iteration, you can dynamically calculate an estimation of the gas cost in your smart contract before you enter the loop. You can use the result to decide whether you execute the loop fully, partially or whether you cancel execution with a revert and a custom message (e.g. in a case where the user can set a parameter which influences the iteration count)

Sadly I don't know any benchmark / analysis environments which you can use to solve this problem. I'd appreciate if someone who knows one can publish a reference here.

How much gas you can spent in your loop also depends on:

1) How much gas is supplied + how much gas is required by all the other parts of the smart contract which get execution before and after the loop

2) The maximum amount of gas that can be consumed during the execution of the transactions within a block (or in other words how much gas a transaction can use at a whole)

1

Option #1 - iterate the list "one by one":

  • Provide an on-chain function which returns the length of the list
  • Provide an on-chain function which performs the task on a given index
  • From the off-chain, call the first function in order to obtain the length
  • From the off-chain, call the second function for (i = 0; i < length; i++)

Pros: simple interface.

Cons: if the task itself is cheaper than the minimum gas for a function-call (21000), then the overall execution will be non-proportionally expensive.


Option #2 - iterate the list "in chunks":

  • Provide an on-chain function which returns the length of the list
  • Provide an on-chain function which performs the task on a given range of indexes
  • From the off-chain, call the first function in order to obtain the length
  • From the off-chain, call the second function several times until the range [0, length) is covered

Pros: the off-chain script has the liberty of optimizing execution thus reducing the overall cost.

Cons: establishing an optimal algorithm might prove to be a rather difficult task.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.