Most gas efficient way to check if byte array contains zeroes?

Question

I have a contract that I pass data packed into an array of uint256 (as it's apparently cheaper to use uint256 over bytes32) and each byte in the uint256 contains positions referencing another array of 256 objects, so in the following example, the first 00 is 1 index, then 01 is the next, 02 is the next etc etc:

0x000102030405060708090A0B0C0D0E0F0102030405060708090A0B0C0D0E0F01
  ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

In my use case of this, 00 is representing "empty", so in the following example theres 6 empty slots e.g.:

0x0A0102030405060708090000000000000102030405060708090A0B0C0D0E0F01
                      ^ ^ ^ ^ ^ ^ 

What is the most gas efficient way to count how many bytes/slots are 00/"empty"?

At the moment I am iterating through each byte in the array, masking and shifting, which gets the job done:

function check32PositionGroupForZeroes(uint256 toCheck) public pure returns (uint256 amountOfZeroes) {
        assembly {
            let converted := and(toCheck, 0x00000000000000000000000000000000000000000000000000000000000000FF) // first is actually last 1 byte in the byte array (uint256 converted to uint8)
            if eq(converted, 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            let len := 0x1F //31 (we already have the first decoded)
            let offset := 0x1F
            
            for { let i := 0 } lt(i, len) { i := add(i, 1) } {
                mstore(offset, toCheck)
                converted := and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF)
                
                if eq(converted, 0x00) {
                    amountOfZeroes := add(amountOfZeroes, 1)
                }
                offset := sub(offset, 0x01)
            }
        }
    }

however as mentioned I have an array of uint256 objects which this check is applying to each entry, and the array is very large, so I want to reduce the work to the bare minimum to save on gas; is there a cheaper way to do this?

EDIT:

I can pretty much halve the gas by eliminating the for loop and adding explicit code to check every position, but it still seems far from ideal:

function checkEfficient32PositionGroupForZeroes(uint256 toCheck) public pure returns (uint256 amountOfZeroes) {
        assembly {
            // first is actually last 1 byte in the byte array (uint256 converted to uint8)
            if eq(and(toCheck, 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x1F, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x1E, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x1D, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x1C, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x1B, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x1A, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x19, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x18, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x17, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x16, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x15, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x14, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x13, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x12, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x11, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x10, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x0F, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x0E, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x0D, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x0C, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x0B, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x0A, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x09, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x08, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x07, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x06, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x05, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x04, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x03, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }

            mstore(0x02, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
            
            mstore(0x01, toCheck)
            if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
                amountOfZeroes := add(amountOfZeroes, 1)
            }
        }
    }

EDIT2: I just found out about iszero(...) which i replaced the eq(.., 0x00) with, which shaves the gas down by a few hundred but still involves the same individual checking of bytes

Answer 1

You might find more efficiency if you venture into assembler but the concern that jumps out is the iterative nature of this approach, which is O(n).

When you say "most gas efficient way" you don't say for who, exactly, it is meant to be efficient. You might consider shifting the burden to users during the evolution of the state.

You don't say where this state comes from or how it evolves before it's time to check. In that design choice, you are probably opting for cheap inserts and expensive checks. You might consider checking at the time when data is inserted so that the count is predetermined when it is time to check. That would be O(1) in both steps and, by extension, scalable.

Any example is just conceptual because I'm not sure how the array of pointers is formed. Consider this just a suggestion that might inspire you to look at it from a new perspective.

Step 1 - insert:

Count the zeroes now. You are iterating over 256 slots but it is finite/bounded, so you write the count and you can consider assembler to optimize that process. When you are done, write it down. Something like an array of these instead of an array of uints:

struct PointerElement {
  uint zeroCount; // counted
  uint pointers;
}

Step 2: Recall it

It should be self-evident that reading it back now is a one-stepper.

In essence, this approach amortizes the work of the big count by sprinkling the cost across all the insert operations that create the data set. Since we want to avoid unbounded iteration, it is almost always preferable to construct a data set where everything we need to read back is accessible with O(1) complexity.

Some more heuristics that might help: https://blog.b9lab.com/getting-loopy-with-solidity-1d51794622ad

Hope it helps.