Loop gas optimisation

[FlyingStraus]

The MerkleProof.sol contract by OZ is used very widely in contracts for EVM chains. Some of the functions are used for-loop. And the way that this for-loop is not the gas-optimal

📝 Details

After the gas optimized code will consume 100 gas units less per each element of an array.

🔢 Code to reproduce bug

The overheads outlined below are PER LOOP, excluding the first loop

storage arrays incur a Gwarmaccess (100 gas) memory arrays use MLOAD (3 gas) calldata arrays use CALLDATALOAD (3 gas) Caching the length changes each of these to a DUP (3 gas), and gets rid of the extra DUP needed to store the stack offset

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;

contract Counter {

    uint256[] public proof;

    constructor() {
        for(uint256 i = 0; i < 100; i++) {
            proof.push(1);
        }
    }


    function loop_not_opt() public {
        uint256 j;
        for (uint256 i = 0; i < proof.length; i++) {
            j++;
        }
    }

    function loop_opt() public {
        uint256 j;
        uint256 len = proof.length;
        for (uint256 i = 0; i < len; i++) {
            j++;
        }
    }
}

As you see on a screenshot, the difference between these two calls is around 10_000 gas units, for a array length of a 100 elements.

Which is not pretty much for one call, But since a lot of contracts use this OZ library, the total amount of overspent gas is high.

Code snippet:

openzeppelin-contracts/contracts/utils/cryptography/MerkleProof.sol

Line 64 in c80b675

for (uint256 i = 0; i < proof.length; i++) {

openzeppelin-contracts/contracts/utils/cryptography/MerkleProof.sol

Line 53 in c80b675

for (uint256 i = 0; i < proof.length; i++) {

Recomendation
And Recommendation is to calculate the length of an array one's and keep it locally

 uint256 len = proof.length;
        for (uint256 i = 0; i < len; i++) {
            j++;
        }