Re: [Qemu-devel] [PATCH] bitops: provide an inline implementation of find_first_bit

[Paolo Bonzini <pbonzini@redhat.com>]

Il 22/12/2013 12:32, Aurelien Jarno ha scritto:
> find_first_bit has started to be used heavily in TCG code. The current
> implementation based on find_next_bit is not optimal and can't be
> optimized be the compiler if the bit array has a fixed size, which is
> the case most of the time.

If you mean by fully unrolling the loop, that's right.

However...

> -    return find_next_bit(addr, size, 0);
> +    unsigned long result, tmp;
> +
> +    for (result = 0; result < size; result += BITS_PER_LONG) {
> +        tmp = *addr++;
> +        if (tmp) {
> +            result += ctzl(tmp);
> +            return result < size ? result : size;
> +        }
> +    }
> +    /* Not found */
> +    return size;
>  }
>
>  /**
>

... you probably want to limit this to bitmaps that are of constant 
size, and small enough that the compiler will unroll them.

So it probably would be a good idea to add an

     if (!__builtin_constant_p(size) || size > 8 * BITS_PER_LONG)
         return find_next_bit(addr, size, 0);

Not urgent since TCG is the only user of find_first_bit right now, but 
worth considering.

Paolo