From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from eggs.gnu.org ([208.118.235.92]:35276)
	by lists.gnu.org with esmtp (Exim 4.71)
	(envelope-from <pbonzini@redhat.com>) id 1UF4fT-0007Sa-RN
	for qemu-devel@nongnu.org; Mon, 11 Mar 2013 11:29:42 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <pbonzini@redhat.com>) id 1UF4fL-0000ui-JW
	for qemu-devel@nongnu.org; Mon, 11 Mar 2013 11:29:39 -0400
Received: from mx1.redhat.com ([209.132.183.28]:38438)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <pbonzini@redhat.com>) id 1UF4fL-0000uR-Ay
	for qemu-devel@nongnu.org; Mon, 11 Mar 2013 11:29:31 -0400
Message-ID: <513DF854.80003@redhat.com>
Date: Mon, 11 Mar 2013 16:29:24 +0100
From: Paolo Bonzini <pbonzini@redhat.com>
MIME-Version: 1.0
References: <513DDFA3.1020308@dlhnet.de> <513DE6D6.9000105@redhat.com>
	<FE8F3AB7-45F9-4B76-B2D4-46179AAD08FE@dlhnet.de>
	<513DEBCF.9050407@redhat.com>
	<E594D4E5-EDA7-4277-9910-D498E9E1E66A@dlhnet.de>
In-Reply-To: <E594D4E5-EDA7-4277-9910-D498E9E1E66A@dlhnet.de>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Subject: Re: [Qemu-devel] [RFC] find_next_bit optimizations
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: Peter Lieven <pl@dlhnet.de>
Cc: Orit Wasserman <owasserm@redhat.com>, "qemu-devel@nongnu.org" <qemu-devel@nongnu.org>, Corentin Chary <corentin.chary@gmail.com>

Il 11/03/2013 16:24, Peter Lieven ha scritto:
> 
>> How would that be different in your patch?  But you can solve it by
>> making two >= loops, one checking for 4*BITS_PER_LONG and one checking
>> BITS_PER_LONG.
> 
> This is what I have now:
> 
> diff --git a/util/bitops.c b/util/bitops.c
> index e72237a..b0dc93f 100644
> --- a/util/bitops.c
> +++ b/util/bitops.c
> @@ -24,12 +24,13 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
>      const unsigned long *p = addr + BITOP_WORD(offset);
>      unsigned long result = offset & ~(BITS_PER_LONG-1);
>      unsigned long tmp;
> +    unsigned long d0,d1,d2,d3;
>  
>      if (offset >= size) {
>          return size;
>      }
>      size -= result;
> -    offset %= BITS_PER_LONG;
> +    offset &= (BITS_PER_LONG-1);
>      if (offset) {
>          tmp = *(p++);
>          tmp &= (~0UL << offset);
> @@ -42,7 +43,19 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
>          size -= BITS_PER_LONG;
>          result += BITS_PER_LONG;
>      }
> -    while (size & ~(BITS_PER_LONG-1)) {
> +    while (size >= 4*BITS_PER_LONG) {
> +        d0 = *p;
> +        d1 = *(p+1);
> +        d2 = *(p+2);
> +        d3 = *(p+3);
> +        if (d0 || d1 || d2 || d3) {
> +            break;
> +        }
> +        p+=4;
> +        result += 4*BITS_PER_LONG;
> +        size -= 4*BITS_PER_LONG;
> +    }
> +    while (size >= BITS_PER_LONG) {
>          if ((tmp = *(p++))) {
>              goto found_middle;
>          }
> 

Minus the %= vs. &=,

Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>

Perhaps:

        tmp = *p;
        d1 = *(p+1);
        d2 = *(p+2);
        d3 = *(p+3);
        if (tmp) {
            goto found_middle;
        }
        if (d1 || d2 || d3) {
            break;
        }

Paolo