Solidity 102 #2: O(1) Iterable Map

This is part 2/N of Band Protocol’s “Solidity 102” series. We explore and discuss data structures and implementation techniques for writing efficient Solidity code under Ethereum’s unique EVM cost model. Readers should be familiar with coding in Solidity and how EVM works in general.

In the previous article, we talked about the techniques to write smart contracts with Solidity while keeping gas costs under control. In this article, we will talk about one concrete data structure that is often needed: Iterable Map. As you may know, iterating in naive solidity mapping is currently not possible. But we will make it possible by augmenting the mapping data structure so it supports iteration functionality with very minimal gas cost overhead. Throughout the article, you will be implementing the smart contracts and experimenting them with us together. If you're ready, let's get into it!

Example Problem #1: School and Students

We want to create a “School” smart contract collecting student addresses. The contract must have 3 main functionalities:

1. Add or remove a student from the contract.
2. Ask if a given student address belongs to the school.
3. Get list of all students.

Our School smart contract will look like this:

Simple Solutions (Hint: Not That Great)

There are 2 simple methods that can partially solve the problem. However, each solution has its own drawback in certain cases. Let’s explore both solutions in details.

Simple Solution #1: Use mapping (address => bool)

We use mapping to store the existence of each student. If value mapped to a given address is true, that means the address is one of our students. While the solution is simple, it has its limitation that it can't support getting all students. In Solidity, iteration on mapping is not supported, unlike most other languages. Solidity code will look like the following.

Simple solution #1. We use plain mapping to store student addresses. This solution does not support iteration.

Simple Solution #2: Use address[] students

In this solution, we use an array of addresses instead of mapping. Now It’s clear that we solve the third requirement (ability to return the list of all students). However, finding and deleting existing students becomes way more difficult. We must loop on every element in array to find an address, to check for address existence, or to remove a student. Code will look like this:

Simple solution #2. We use plain array. Performance will likely suffer.

Simple Solutions: Performance Analysis

We ran an experiment to understand how much gas is used in order to add or remove an address to/from the list when the size of the list is 10 and 100. Here’s the result.

Note that removing an element from an array can be more efficient by swapping the removing element with the last element, then popping the last element from the array. That said, doing that still requires O(n) looping to find the location of element to be removed.

We derive at a simple conclusion, mapping is more efficient but does not fulfill all requirements, while array can do it all with the cost that scales proportionally with the total number of students. So both of them are not good. We need a better alternative!

Better Solution: Use mapping(address ⇒ address)

Here comes the exciting part! The basis of this data structure is linked-list. We store the address of next student (i.e. a pointer to next student) as a value of mapping instead of a plain boolean value. Sounds confusing confused right? This picture will help you understand.

Top: Linked-List data structure. The each node points to its next node and the last node point back to GUARD. Bottom: Concrete representation of the top image with Key-Value mapping.

Initialization of the data structure is done by setting GUARD to point to GUARD, which means the list is empty

Now let’s go over the implementation of each of the functions.

Check If a Student is in the School: isStudent

We use the fact that the value in the mapping structure of a particular student in the school always points to the next student's address. Thus, we can easily verify if a given address is in the school by checking the value that this address maps to. If it points to some non-zero address, that means this student address is in the school.

Add a new Student to the School: addStudent

We can add a new address after the GUARD (which represents the HEAD pointer of the list) by changing the guard's pointer to this new address and setting the pointer from this new address(New Student) to the previous front address(Front Student).

Remove a Student from the School: removeStudent

This function is more tricky than 2 functions above. We know if address is in list or not, but we can’t easily derive the previous address of any given student (unless we use doubly link-listed, but that’s significantly more expensive in terms of storage costs). To remove an address, we need to make its previous student point to the next address of the removing address, and set the removing address’s pointer to zero.

Note that to implement removeStudent, we must also introduce getPrevStudent function that helps find the previous student address before any given student.

Get the List of All Students: getStudents

This is simple. We loop through the mapping starting from the GUARD address and set current pointer to next pointer until it points GUARD again, which is when the iteration is completed.

Optimizing removeStudent Further

Notice that removeStudent function that we implemented consumes gas proportionally to the number of students in the school, because we need to loop through the whole list once to find the previous address of the address to be removed. We can optimize this function by sending previous address to function, using off-chain computation. Thus, the smart contract only needs to verify that the previous address indeed points to address we want to remove.

Better Solution: Performance Analysis

We ran an experiment to confirm the performance of our linked-list implementation. As seen below, add and remove (optimized) function cost constant ( O(1) ) amount of gas regardless of the number of elements in the list! Better yet, we can iterate through the whole collection with this solution too. Yikes!

Final performance analysis. As you can see, both add and remove cost O(1) gas regardless of the student count!

Conclusion

In this article, we explore an implementation of Iterable Maps, a data structure that not only supports O(1) add, remove, and find, similar to traditional mapping, but also supports collection iteration. We performed a performance analysis to confirm the assumption and arrived at the final implementation that works! In the next article, we will explore how to utilize this data structure further to solve more real-world problems. Stay tuned for updates!

Band Protocol is a platform for decentralized data governance. We are a team of engineers who look forward to the future where smart contracts can connect to real-world data efficiently without trusted parties. If you are a passionate developer and want to contribute to Band Protocol, please reach out to us at talent@bandprotocol.com.