Creating an automatically ordered pledge list. Can I do better in terms of gas?

Question

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!

Answer 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.