Perf: can do better than Kernighan's algorithm in BitmapUtils' countNumOnes function

[0xkarmacoma]

Here is the current function:

    /// @return count number of ones in binary representation of `n`
    function countNumOnes(uint256 n) internal pure returns (uint16) {
        uint16 count = 0;
        while (n > 0) {
            n &= (n - 1); // Clear the least significant bit (turn off the rightmost set bit).
            count++; // Increment the count for each cleared bit (each one encountered).
        }
        return count; // Return the total count of ones in the binary representation of n.
    }

It is linear in the number of bits set, so it's very efficient when the bitmap is empty or very sparse, but gets very inefficient for dense bitmaps.

Solady implements an O(1) algorithm, inspired by https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

I ran a simple test to figure out where the breakeven is:

  solady_countNumOnes(0): 158
  solady_countNumOnes(UINT256_MAX): 201

  eigen_countNumOnes(0): 73
  eigen_countNumOnes(1): 279
  eigen_countNumOnes(UINT256_MAX): 52852

Based on this, it seems that the current version of countNumOnes is only more efficient for the empty bitmap, and can cost up to 50k+ gas more than the O(1) version

[0xkarmacoma]

I used the following test:

    function solady_countNumOnes(uint256 x) internal pure returns (uint16 c) {
        /// @solidity memory-safe-assembly
        assembly {
            let max := not(0)
            let isMax := eq(x, max)
            x := sub(x, and(shr(1, x), div(max, 3)))
            x := add(and(x, div(max, 5)), and(shr(2, x), div(max, 5)))
            x := and(add(x, shr(4, x)), div(max, 17))
            c := or(shl(8, isMax), shr(248, mul(x, div(max, 255))))
        }
    }

    /// @return count number of ones in binary representation of `n`
    function eigen_countNumOnes(uint256 n) internal pure returns (uint16) {
        uint16 count = 0;
        while (n > 0) {
            n &= (n - 1); // Clear the least significant bit (turn off the rightmost set bit).
            count++; // Increment the count for each cleared bit (each one encountered).
        }
        return count; // Return the total count of ones in the binary representation of n.
    }

    function test_countNumOnes_gas() public {
        uint256 gasLeftBefore;
        uint256 gasLeftAfter;

        uint256 UINT256_MAX = type(uint256).max;

        gasLeftBefore = gasleft();
        solady_countNumOnes(0);
        gasLeftAfter = gasleft();
        emit log_named_uint("solady_countNumOnes(0)", gasLeftBefore - gasLeftAfter);

        gasLeftBefore = gasleft();
        solady_countNumOnes(UINT256_MAX);
        gasLeftAfter = gasleft();
        emit log_named_uint("solady_countNumOnes(UINT256_MAX)", gasLeftBefore - gasleft());

        gasLeftBefore = gasleft();
        eigen_countNumOnes(0);
        gasLeftAfter = gasleft();
        emit log_named_uint("eigen_countNumOnes(0)", gasLeftBefore - gasLeftAfter);

        gasLeftBefore = gasleft();
        eigen_countNumOnes(1);
        gasLeftAfter = gasleft();
        emit log_named_uint("eigen_countNumOnes(1)", gasLeftBefore - gasLeftAfter);

        gasLeftBefore = gasleft();
        eigen_countNumOnes(UINT256_MAX);
        gasLeftAfter = gasleft();
        emit log_named_uint("eigen_countNumOnes(UINT256_MAX)", gasLeftBefore - gasleft());
    }

[wadealexc]

i gotta be honest, i don't understand your algorithm at all, but -- we're only going to be using this with bitmaps of size 2 at max, so the gas cost difference should be negligible

thanks for the idea -- we may want to revisit this later :)