0

Inspired by What's the best way to return top X values in a mapping? and Are there well-solved and simple storage patterns for Solidity?, I've created a data structure that automatically orders itself based on an "opt-in" amount. Unfortunately, there a few loops in here consuming a fair bit of gas, and so I'm wondering if anyone has any suggestions of where I can improve my code.

It has three main methods: delete, remove and update. remove currently uses quite a bit of gas.

pragma solidity 0.4.24;
pragma experimental ABIEncoderV2;
pragma experimental "v0.5.0";

import "./LibOptIn.sol";


library LibOptInList {
    using LibOptIn for LibOptIn.OptIn;

    struct OptInList {
        mapping (address => uint256) balances;
        LibOptIn.OptIn[50] optIns;
    }

    // TODO (julian): can probably do some optimization for when there are zero addresses initially.
    function insert(
        OptInList storage self, 
        address addr, 
        uint256 value
    ) 
    internal 
    returns (LibOptIn.OptIn)
    {
        LibOptIn.OptIn memory displacedOptIn;
        uint256 i = 0;
        // get the index of the current element one higher than `value`
        for (i; i < self.optIns.length; i++) {
            if (self.optIns[i].balance < value) {
                break;
            }
        }

        // Check if the value is high enough to be inserted.
        if (i == 0 && value < self.optIns[0].balance) { 
            revert("Value is not high enough"); 
        }

        if (self.optIns[self.optIns.length-1].addr != address(0)) {
            displacedOptIn = self.optIns[self.optIns.length-1];
        }

        // shift the array of position (getting rid of the last element) 
        for (uint256 j = self.optIns.length - 1; j > i; j--) {
            self.optIns[j].balance = self.optIns[j - 1].balance;
            self.optIns[j].addr = self.optIns[j - 1].addr;
        }

        // update the new ith highest element
        self.optIns[i].balance = value;
        self.optIns[i].addr = addr;

        // update mapping
        self.balances[addr] = value;

        // return displaced value and delete from balances mapping, might be empty
        delete self.balances[displacedOptIn.addr];
        return displacedOptIn;
    }

    function remove(OptInList storage self, address addr) internal {
        uint256 i = 0;

        // get the index of the addr element
        for (i; i < self.optIns.length; i++) {
            if (self.optIns[i].addr == addr) {
                break;
            }
        }

        // check if this address is in the opt-in list
        if (i == 0 && self.optIns[0].addr != addr) { 
            revert("Address not in opt-in list."); 
        }

        // move elements up one
        for (uint256 j = i; j < self.optIns.length - 1; j++) {
            self.optIns[j].balance = self.optIns[j+1].balance;
            self.optIns[j].addr = self.optIns[j+1].addr;
        }

        // kill last element 
        delete self.optIns[self.optIns.length - 1];

        // remove from mapping
        delete self.balances[addr];
    }

    function update(
        OptInList storage self, 
        address addr, 
        uint256 newVal
    ) 
    internal
    returns (LibOptIn.OptIn)
    {
        remove(self, addr);
        return insert(self, addr, newVal);
    }        
}

The OptIn struct is very simple, it's just:

struct OptIn {
    uint256 balance;
    address addr;
}

Thank you for your help!

  • How are you going to need to query the data? Do you need to be able to get the sorted opt-in list at any time, or are you going to pull it at some finalization time? Is it enough to just get the top-most opt-in balance? You want to find some constraints you can lean into here. To answer your question more narrowly, the most expensive part of your remove is shifting all the following values backwards. An alternate strategy would be to empty removed values but not update the indices, or to store everything in a mapping and only compute the order when you need it. – ohsully Sep 12 '18 at 16:52
  • In case ordering the list can be externalized altogether. blog.b9lab.com/… – Rob Hitchens - B9lab Sep 12 '18 at 17:39
  • @ohsully For querying, the two things that I need to know are 1) membership and 2) their "pledged" balance. Ordering from a querying perspective is not important. – coolboyjules Sep 12 '18 at 19:00
  • @coolboyjules What's the purpose of having an ordered array, then? If you're not going to query the data in a way which depends on it being ordered (e.g. retrieving the top-most member & balance), then you might as well just use a map! We might be using the word "query" a little differently. And going with the gist of Rob's blog post, if you're just want to display the data elsewhere in order, consider just ordering it in the GUI. – ohsully Sep 12 '18 at 19:28
  • 1
    Yup, that makes sense. Your constraints do give you something to lean on if you design a data structure for this specific problem. If you don't care about the order, then inserts are dead simple up to the 50th one. If you then cache the lowest balance, you can use it to find which element should be replaced in the array, then finish the iteration to be sure you cache the new lowest balance. You're still looking at iterating over 50 elements, but not doing all those re-assignments will make things a good bit cheaper. – ohsully Sep 12 '18 at 19:53
1

You can control and reduce the gas cost from looping and recursion by using hints.

In the case of sorted lists, the recursive/iterative processes usually involve a search for the correct insertion point. A hint can kick off the process in the vicinity of the insertion point.

So, instead of "insert Bob", say "insert Bob after Alice, where Alice is an exact location.

You can and should write the contract with the perspective that the hint might miss by a little even with an honest client because the blockchain state might evolve before the insertion transaction is mined. That's okay. The point isn't to eliminate loopy processes, but rather to keep them under control and to ensure that insertion is possible at any scale.

So, if someone sends "insert Bob after Alice", the contract should start at Alice, notice Audrey and insert Bob after Audrey. Of course, if Alice is missing, insert Bob at the head. The important thing is the "hint" is not expected to be 100% precise. It merely reduces unnecessary looping and recursion, and gas.

Clients are incentivized to provide accurate hints that reduce gas cost or even avoid out-of-gas situations. Make sure the contract is not vulnerable to misleading hints. The contract is responsible for assuring that inserts only happen in the appropriate spot.

Hope it helps.

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.