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<N> (3 gas), and gets rid of the extra DUP<N> 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: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/c80b675b8db1d951b8b3734df59530d0d3be064b/contracts/utils/cryptography/MerkleProof.sol#L64 https://github.com/OpenZeppelin/openzeppelin-contracts/blob/c80b675b8db1d951b8b3734df59530d0d3be064b/contracts/utils/cryptography/MerkleProof.sol#L53

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++;
        }

[0xScratch]

You are pointing out the right thing @FlyingStraus. There are a lot of projects with the same unoptimized code as per my knowledge. Accessing the length of some storage datatype again and again in a for loop is often more costly than keeping that same specific length in some particular uint variable

[jhubbardsf]

Wanted to add to this that the code could be further optimized by removing the assignment to i, and using ++i instead of i++ which will be functionally equivalent here, although your primary gas savings will obviously come from removing proof.length from the for-loop definition.

Also, for loops where i (in this example) can be guaranteed to be less than type(i).max or when the counter is circular, you can place the increment inside an unchecked block at the end of the for-loop body instead of inside the loop definition. In this case, we know that both len and i are uint256, so i will never exceed type(i).max due to the for-loop condition i < len. This optimization provides gas savings that scale with len, as it removes the overflow checks performed on each iteration.

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

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

            unchecked {
                 ++;
            }
        }
    }

[Amxx]

This is automatically handled by the compiler since 0.8.22.