Solidity optimisation to avoid loop

Question

I have a structs, mappings and a function as follow:

 // a list of selectors that might be allowed functions
 bytes4[] internal knownSelectors;
 mapping(bytes4 => bool) internal knownSelector;

 struct State {
    // a mapping of functions that can be executed when in this state
    mapping(bytes4 => bool) allowedFunctions;
    // a list of all the roles that have been configured for this state
    bytes32[] allowedRoles;
  }

  mapping(bytes32 => State) internal states;

  function getState(bytes32 state)
    public
    view
    returns (
      uint256 counter
    )
  {
    State storage s = states[state]; // copy to memory

    uint8 counter = 0;
    for (uint256 i = 0; i < knownSelectors.length; i++) {
      if (states[state].allowedFunctions[knownSelectors[i]]) {
        counter += 1;
     }
    }  
  }

But I would like to avoid that for loop in the end of the function, do you guys have any idea on how to do that? because if there are a lot of knownSelectors then this loop might be extremely expensive... thanks in advance for the advices!

Answer 1

It appears that your loop is merely counting elements. You can accomplish that by counting as you go.

 struct State {
    mapping(bytes4 => bool) allowedFunctions;
    uint allowedFunctionsCount;
    bytes32[] allowedRoles;
  }

I think this:

    State storage s = states[state]; // copy to memory

    uint8 counter = 0;
    for (uint256 i = 0; i < knownSelectors.length; i++) {
      if (states[state].allowedFunctions[knownSelectors[i]]) {
        counter += 1;
     }
    } 

was meant to be:

    State storage s = states[state]; // copy to memory

    uint8 counter = 0;
    for (uint256 i = 0; i < knownSelectors.length; i++) {
      if (s.allowedFunctions[knownSelectors[i]]) {
        counter += 1;
     }
    } 

In any case, you can avoid the loop by performing the counter update on insertion instead of iterating over the list here. You'll end up with:

State storage s = states[state]; // copy to memory
return s.allowedFunctionsCount;

The exact structure of the storage layout and the update process depends on the CRUD operations you actually need. In the simplest case, it's append-only and knownSelectors[i] you are using for conditional counting never changes, once set. You can just update the counter when you append to the lists.

Update and Delete operations will present a challenge. For example, if the knownSelectors[i] changes and this is supposed to affect multiple states, then you will have to find a way to update multiple counters without iteration.

Iterable sets combine lists with mappings to offer both random access and iteration. You can use those types to create structures that enforce referential integrity. You can create a structure that supports count properties even while full update and delete functions that threaten widespread reorganization are supported.

Have a look over here for inspiration: https://medium.com/robhitchens/solidity-crud-epilogue-e563e794fde

I can't be more specific as the exact use-case is unknown, particularly the maintenance requirements and needed statistics. I suspect the above is a simplified example that was put together to make a succinct question.

Hope it helps.