From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from eggs.gnu.org ([2001:4830:134:3::10]:34874)
	by lists.gnu.org with esmtp (Exim 4.71)
	(envelope-from <paolo.bonzini@gmail.com>) id 1WxXpg-0005IS-RZ
	for qemu-devel@nongnu.org; Thu, 19 Jun 2014 04:36:42 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <paolo.bonzini@gmail.com>) id 1WxXpX-0005bd-RJ
	for qemu-devel@nongnu.org; Thu, 19 Jun 2014 04:36:32 -0400
Received: from mail-wi0-x234.google.com ([2a00:1450:400c:c05::234]:50200)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <paolo.bonzini@gmail.com>) id 1WxXpX-0005bS-Jz
	for qemu-devel@nongnu.org; Thu, 19 Jun 2014 04:36:23 -0400
Received: by mail-wi0-f180.google.com with SMTP id hi2so2410497wib.13
	for <qemu-devel@nongnu.org>; Thu, 19 Jun 2014 01:36:22 -0700 (PDT)
Sender: Paolo Bonzini <paolo.bonzini@gmail.com>
Message-ID: <53A2A102.4060807@redhat.com>
Date: Thu, 19 Jun 2014 10:36:18 +0200
From: Paolo Bonzini <pbonzini@redhat.com>
MIME-Version: 1.0
References: <1387711957-703-1-git-send-email-aurelien@aurel32.net>
In-Reply-To: <1387711957-703-1-git-send-email-aurelien@aurel32.net>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [Qemu-devel] [PATCH] bitops: provide an inline implementation
	of find_first_bit
List-Id: <qemu-devel.nongnu.org>
List-Unsubscribe: <https://lists.nongnu.org/mailman/options/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=unsubscribe>
List-Archive: <http://lists.nongnu.org/archive/html/qemu-devel>
List-Post: <mailto:qemu-devel@nongnu.org>
List-Help: <mailto:qemu-devel-request@nongnu.org?subject=help>
List-Subscribe: <https://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=subscribe>
To: Aurelien Jarno <aurelien@aurel32.net>, qemu-devel@nongnu.org
Cc: Corentin Chary <corentin.chary@gmail.com>, Richard Henderson <rth@twiddle.net>

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