Re: [PATCH] copy, dd: simplify and optimize NUL bytes detection

[Bernhard Voelker]

On 10/22/2015 05:17 PM, Pádraig Brady wrote:
> 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().

what about spending some 16 bytes of memory and do the memcmp on the whole
buffer?

  static unsigned char p[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
  return 0 == memcmp (p, buf, bufsize);

Have a nice day,
Berny