Getting Loopy with Solidity
How to Avoid Unbounded “For” Loops in Solidity Smart Contracts
Let’s begin with a few questions:
- What is an unbounded for loop?
- Why is it an anti-pattern?
- How to avoid it?
An unbounded for loop is any loop that has no constraint on the number of iterations. In other words, cases where there is no obvious limit.
For example:
- “for every user, do something …” when there is no apparent limit on the number of users.
- “for every item, do something …” when there is no apparent limit on the number of items.
- for(i=0; i<?; i++) { // danger ahead }
It’s familiar-looking and deadly. In Solidity, we need to avoid that because it won’t scale. Suppose it read “For i equals 0 to unmitigated disaster.”
None of us sets out to build software that will lock up and fail after too many people use it. At least not on purpose, because we are nice people.
Why won’t it scale?
Because gas and gasLimit.
“gas” is the unit of account for computational work used to pass on the cost of every transaction to the user. More work equals more gas which costs more to execute. Imagine your CPU sent you a bill for every single operation. Imagine no more!
This is the reality of the Ethereum Virtual Machine. Someone always pays. You don’t need to memorize the whole price list, but newcomers should internalize the idea that there is always a full accounting of everything that happens and nothing is ever free. See OPCODE Gas Costs (not perfectly up-to-date, but there’s a handy link to the Yellow Paper in there).
“block.gasLimit” is a network property voted on by the miners. As developers, we don’t control the gas limit, but we know it exists. You can think of it as the size of the fuel tank. If a transaction runs out of gas then the transaction will revert. We can’t (currently) run a transaction that exceeds the block.gasLimit.
Imagine you and your users are in an airplane. The further you want to go, the more gas you will burn. There is a maximum limit to the fuel you can carry and therefore a maximum distance you can fly. If you aim too far away, you will run out of gas before you get there and then bad things will happen ...
The gasLimit adjusts over time (the miners vote on it) so you can never be too sure how much is too much, but you can be certain that there is a hard stop when you reach that point. You need to plan your journeys so you complete each step before that happens.
You can safely do as many short hops as you want, refueling at each stop. Doesn’t it make sense to think in terms of multiple, small, safe hops instead of depending on big risky moves?
So, if you are thinking about any process in terms of for every customer, or for every item, you are probably overlooking the limits of your machine. You are probably thinking about the wrong solution to the problem. This sort of thing isn’t an error in a particular line of code. It’s a misguided approach.
TL;DR
Every step costs money. Some processes are more expensive than money can buy. This necessitates a new focus on efficiency.
In Ethereum, unlimited work is not an option. This means some your favorite “go-to” patterns and the obvious solutions to many everyday tasks are precisely what we must not do.
Examples to avoid:
- Search for a record of interest in a list of unlimited size.
- Search for an insertion point in an ordered list of unlimited size
- Read or write too many items in a list of unlimited size.
- Reorganize list items in a big way such as a sort, roll up or splice.
- Recursively call contract functions with unlimited depth.
How can we avoid getting loopy?
There are plenty of reasons to want to iterate over n instances of something. Finding ways around such tendencies calls for new ways of thinking.
Let’s look at a few examples.
Avoid Sorts
for(i=0; I < records.length-1; i++) { for(j=i+1; j < records.length; j++) { // compare record[i] and record[j] // swap records if needed }}
The classic bubble sort algo gets the job done if you have unlimited compute resources or a very small list. But we don’t have unlimited resources and we must not approach problems this way. How on earth can we accomplish such a thing without using loops?
This may seem hard to accept, but the first thing to do is to look for ways to avoid sorting anything. That’s why you so seldom see professionally-crafted contracts doing sorts. Here’s why and how: The Joy of Minimalism
Rely on 1-step lookups
One of the reasons we like to sort data is to find things efficiently, right? What if we could find any record in exactly one operation and also enumerate the complete list of everything stored? Would it still be vital to sort the data?
Have a look over here for a popular pattern that does it all with unordered lists: Solidity CRUD.
Ordered lists make it worse
It’s hard to beat 1-step look-ups. Ordered lists are much more work and often unnecessary, which is why we look for ways to avoid them.
In that rare case that contract logic depends on an ordered list, then you must be extra cautious to ensure that there is always a way to contain the cost so you can guarantee that cost will be scale-invariant. To the author’s knowledge, there is no known algorithm that can index or sort a list of unordered data without increasing the cost by some factor of scale. For example, O(log n).
A solution to this problem is to break the mission down into smaller steps that the contract can complete at a fixed cost. This will likely involve externalizing some concerns, meaning, more reliance on outside help than seems obvious.
Use Hints
For example, clients can send hints to contract functions.
In the linked experimental pattern, the contract maintains an ordered list of everything thrown at it. Clients tell the contract what they want to insert and also give the contract a hint about where to put it. The contract checks the acceptability of the request because the contract assures system integrity: LinkedList (with hints)
Not so fast.
Consider the following:
Even if a client diligently searches and presents perfect hints, the situation may change before a transaction is mined, which means the hint may not be perfect anymore. If the contract disagrees with the hint about where to put something rather than rejecting the request outright, the contract conducts a regional search to find the right location, starting from the hint. If the correct spot can be located before it runs out of gas, then the insertion succeeds.
It will always be possible to use the contract and always at a scale-invariant cost. A bulls-eye (perfectly accurate hint) is the same cost at any scale. There are similarly predictable costs for missing by 1, missing by 2, etc., which is what we want. It’s not even vital that the hint is any good at all but the more the lazy software client misses, the higher the cost to the client.
If the author’s reasoning on this is correct, the worst-case scenario is so much data pouring into the contract that careful clients still miss by a lot because the contract state changes significantly before transactions are mined. Client costs are roughly overhead + O(missed by), so miserly clients slow down until there is less contention. The contract doesn’t fail in any case and life goes on at any scale. That’s the top priority.
The above is certainly not the only approach. Apart from dispensing with the ordered list concern entirely, which we should do if we can, the point of the example is the vital importance of finding a solution that doesn’t imply increasing cost or limits to scale.
Queries and Filtered Lists
Queries are often cited as a justification for iterative processes. A developer might say something like “I need to return a list of all the …”.
At the risk of seeming pedantic, “I need” seems to get the discussion off on the wrong foot. The developer is not normally a participant in the system architecture, so how can the non-participant have a need? This is not a good description of actual requirements. Perhaps someone has a need, but it’s not the developer. Who? Why? Let’s think carefully about that.
There’s a user interface, perhaps one or more servers, and a system of contracts. Let’s say some component in the system will produce a list because a client needs it a certain way. Fair enough, but it’s not necessarily the contract’s job to do that and we shouldn’t assume that it is. Using the contract for this purpose should be avoided where possible, and it’s almost always possible: see The Joy of Minimalism in Smart Contract Design.
What about returning arrays?
The author has very mixed feelings about the trend toward increasing support of strings, dynamic arrays and structs in the ABI. Admittedly, pioneers learned to get by with fixed-size interfaces, so now we know patterns to follow. That makes the dynamic stuff seem far less vital than it might seem to newcomers who are accustomed to object-oriented languages.
The discomfort is not merely about clinging to idiomatic patterns that have worked well for a considerable amount of time. The real source of the author’s hesitation is that it seems to encourage rather than discourage unscaleable patterns and it seems to encourage complexity in a setting where we should be striving for simplicity itself.
If we’re sure that the largest possible array and the process that assembles it and sends it will always complete at a cost below the block.gasLimit, then it’s technically feasible. The challenge is being sure. Given that (probably) no amendment of the contract will be possible, what is plan B in the case that the list-wise function becomes too expensive to be feasible or stops working entirely?
Amortisation of Work
A solution to that problem that provides maximum certainty is a more granular function that returns one item or one part of the solution at a time.
Consider this:
Software clients are not constrained by how many separate calls they make to a contract but each contract transaction and call is severely constrained by the maximum allowable computational complexity. So, we should work with patterns that move consumption from the resource that’s scarce to the resource we have in abundance. Too abstract? It’s better to have a software client make 1000 tiny contract function invocations to complete 1000 steps, instead of a contract function that repeats a step 1000 times.
Nick Johnson calls this “Amortisation of Work”.
Wait. What about race conditions?
Good! Now we’re thinking about implementation details. We can’t leave half-baked contract states out there. Each atomic operation has to leave the contract in an acceptable state. This isn’t necessarily easy, but it’s the right difficult problem to work on.
In summary, take any process that adds up to a variable amount of work and possibly a lot of work inside the contract, and turn it into a lot of small fixed-cost operations directed by the client side. When you do that, you will often find there is no longer a need for the big list-wise operation originally contemplated. Some readers may recognize that seems a lot like the concept of inverting control.
Amortisation of work is a very useful pattern
- Want to get all the rows from an array? Feed them to clients one row at a time. Instead of the client requesting the list, the client will request one item at a time.
- Want to send all the users a dividend? Wait for clients to claim them individually. Compute their entitlement in O(1) from simple values (shares and gross dividend), on-the-fly, whenever balance information is needed. Perform housekeeping when gas is available. This has the added benefit of externalizing the cost of the distribution.
- Want to sort or filter an array? Leave that to the “software client” which could be a caching server as is the case with exchanges and explorers like etherscan.io. You didn’t think they inspect the blockchain for every web request, did you? Of course not. They know better. Blocks arrive, things have happened, the off-chain high-performance database is updated because such things are designed to deal with ordering, filtering, joining and so on. This is also why you can see things on block explorers that are simply not there when you explore raw block data.
As Nick Johnson puts it:
Any loop like the one in the snippet above should set your spidey-sense tingling, and the first thing you should look for is a way to amortise the work being done.
And that’s what this post is all about.
It’s hard to accept (and even harder to adjust to) the need to amortise work. Doing so will affect the way you imagine architecture and control flows, the functions and the way you structure storage.
At B9lab, we are dedicated to guiding students to the top of this field. Our hands-on training programs mentored by instructors like myself and workshops prepare students for stringent certification exams.
Start with your Ethereum Developer Certification and consider branching out to Quorum Specialist (think “enterprise”) or Quality Assurance Specialist (think “smart contract auditor”). Maybe even check out Hyperledger, Corda and EOS. They too are interesting and different.
