From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from eggs.gnu.org ([2001:4830:134:3::10]:38159)
	by lists.gnu.org with esmtp (Exim 4.71)
	(envelope-from <P@draigbrady.com>) id 1ZpHct-0003W6-O7
	for qemu-devel@nongnu.org; Thu, 22 Oct 2015 11:18:00 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <P@draigbrady.com>) id 1ZpHcq-0002Xr-FK
	for qemu-devel@nongnu.org; Thu, 22 Oct 2015 11:17:59 -0400
Received: from mail1.vodafone.ie ([213.233.128.43]:7188)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <P@draigbrady.com>) id 1ZpHcq-0002WN-9O
	for qemu-devel@nongnu.org; Thu, 22 Oct 2015 11:17:56 -0400
References: <1445522453-14450-1-git-send-email-P@draigBrady.com>
	<5628F4BC.2040502@redhat.com> <5628F634.6040809@redhat.com>
From: =?UTF-8?Q?P=c3=a1draig_Brady?= <P@draigBrady.com>
Message-ID: <5628FE20.80802@draigBrady.com>
Date: Thu, 22 Oct 2015 16:17:52 +0100
MIME-Version: 1.0
In-Reply-To: <5628F634.6040809@redhat.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Subject: Re: [Qemu-devel] [PATCH] copy,
	dd: simplify and optimize NUL bytes detection
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: Paolo Bonzini <pbonzini@redhat.com>, Eric Blake <eblake@redhat.com>, coreutils@gnu.org
Cc: Rusty Russell <rusty@rustcorp.com.au>, "qemu-devel@nongnu.org" <qemu-devel@nongnu.org>

On 22/10/15 15:44, Paolo Bonzini wrote:
> 
> 
> On 22/10/2015 16:37, Eric Blake wrote:
>>>> +  /* Check first 16 bytes manually.  */
>>>> +  for (len = 0; len < 16; len++)
>>>> +    {
>>>> +      if (! bufsize)
>>>> +        return true;
>>>> +      if (*p)
>>>> +        return false;
>>>> +      p++;
>>>> +      bufsize--;
>>>> +    }
>>>> +
>>>> +  /* Now we know that's zero, memcmp with self.  */
>>>> +  return memcmp (buf, p, bufsize) == 0;
>>>>  }
>> Cool trick of using a suitably-aligned overlap-to-self check to then
>> trigger platform-specific speedups without having to rewrite them by
>> hand!  qemu is doing a similar check in util/cutils.c:buffer_is_zero()
>> that could probably benefit from the same idea.
> 
> Nice trick indeed.  On the other hand, the first 16 bytes are enough to
> rule out 99.99% (number out of thin hair) of the non-zero blocks, so
> that's where you want to optimize.  Checking them an unsigned long at a
> time, or fetching a few unsigned longs and ORing them together would
> probably be the best of both worlds, because you then only use the FPU
> in the rare case of a zero buffer.

Note the above does break early if non zero detected in first 16 bytes.

Also I suspect the extra conditions involved in using longs
for just the first 16 bytes would outweigh the benefits?
I.E. the first simple loop probably breaks early, and if not
has the added benefit of "priming the pumps" for the subsequent memcmp().

BTW Rusty has a benchmark framework for this as referenced from:
http://rusty.ozlabs.org/?p=560

cheers,
Pádraig.