Re: [PATCH v2] Optimize buffer_is_zero

[Alexander Monakov]

Ping^3.

On Thu, 14 Dec 2023, Alexander Monakov wrote:

> Ping^2.
> 
> On Thu, 9 Nov 2023, Alexander Monakov wrote:
> 
> > I'd like to ping this patch on behalf of Mikhail.
> > 
> >   https://patchew.org/QEMU/20231027143704.7060-1-mmromanov@ispras.ru/
> > 
> > If this needs to be split up a bit to ease review, please let us know.
> > 
> > On Fri, 27 Oct 2023, Mikhail Romanov wrote:
> > 
> > > Improve buffer_is_zero function which is often used in qemu-img utility.
> > > For instance, when converting a 4.4 GiB Windows 10 image to qcow2 it
> > > takes around 40% of qemu-img run time (measured with 'perf record').
> > > 
> > > * The main improvements:
> > > 
> > > 1) Define an inline wrapper for this function in include/qemu/cutils.h.
> > > It checks three bytes from the buffer, avoiding call overhead when
> > > any of those is non-zero.
> > > 
> > > 2) Move the decision between accelerators to the inline wrapper so it
> > > can be optimized out when buffer size is known at compile time.
> > > 
> > > * Cleanups:
> > > 
> > > 3) Delete AVX-512 accelerator, which is now invoked rarely thanks to
> > > inline wrapper, so its speed benefit is neutralized by processor
> > > frequency and voltage transition periods, as described in
> > > https://travisdowns.github.io/blog/2020/01/17/avxfreq1.html
> > > 
> > > 4) Delete SSE4 accelerator because its only difference with the SSE2 one
> > > is using ptest instead of pcmpeq+pmovmsk to compare a vector with 0, but
> > > it gives no perfomance benefit (according to uops.info data).
> > > 
> > > 5) Remove all prefetches because they are done just a few processor
> > > cycles before their target would be loaded.
> > > 
> > > * Improvements for SIMD variants:
> > > 
> > > 6) Double amount of bytes checked in an iteration of the main loop in
> > > both SSE2 and AVX2 accelerators, moving the bottleneck from ALU port
> > > contention to load ports (two loads per cycle on popular x86
> > > implementations). The improvement can be seen on real CPUs as well as
> > > uiCA simulation.
> > > 
> > > 7) Replace unaligned tail checking in AVX2 accelerator with aligned tail
> > > checking similar to SSE2's one because reading unaligned tail gives no
> > > benefit.
> > > 
> > > 8) Move tail checking in both SSE2 and AVX2 accelerators before the main
> > > loop so pcmpeq+pmovmsk checks are spread out more evenly.
> > > 
> > > * Correctness fixes:
> > > 
> > > 9) Add uint64_a type for pointers in integer version so they can alias
> > > with any other type used in the buffer.
> > > 
> > > 10) Adjust loop iterators to avoid incrementing a pointer past the end of
> > > the buffer.
> > > 
> > > * Other improvements:
> > > 
> > > 11) Improve checking buffers with len < 8 in internal integer function
> > > because inline wrapper ensures len >= 4.
> > > 
> > > After these improvements buffer_is_zero works ~40% faster and takes 28%
> > > of qemu-img run time (measured the same way as initial version, inline
> > > wrapper execution included).
> > > 
> > > The test-bufferiszero.c unit test still passes.
> > > 
> > > Signed-off-by: Mikhail Romanov <mmromanov@ispras.ru>
> > > ---
> > > 
> > > v2: reworded the commit message and comments; use casts via 'void *'
> > > 
> > > As buffer_is_zero is now a static inline function, should it be moved 
> > > into its
> > > own header file?
> > > 
> > >  include/qemu/cutils.h |  25 ++++-
> > >  util/bufferiszero.c   | 249 +++++++++++++++++-------------------------
> > >  2 files changed, 122 insertions(+), 152 deletions(-)
> > > 
> > > diff --git a/include/qemu/cutils.h b/include/qemu/cutils.h
> > > index 92c927a6a3..6e35802b5e 100644
> > > --- a/include/qemu/cutils.h
> > > +++ b/include/qemu/cutils.h
> > > @@ -187,7 +187,30 @@ char *freq_to_str(uint64_t freq_hz);
> > >  /* used to print char* safely */
> > >  #define STR_OR_NULL(str) ((str) ? (str) : "null")
> > >  
> > > -bool buffer_is_zero(const void *buf, size_t len);
> > > +bool buffer_is_zero_len_4_plus(const void *buf, size_t len);
> > > +extern bool (*buffer_is_zero_len_256_plus)(const void *, size_t);
> > > +static inline bool buffer_is_zero(const void *vbuf, size_t len)
> > > +{
> > > +    const char *buf = vbuf;
> > > +
> > > +    if (len == 0) {
> > > +        return true;
> > > +    }
> > > +    if (buf[0] || buf[len - 1] || buf[len / 2]) {
> > > +        return false;
> > > +    }
> > > +    /* For len <= 3, all bytes are already tested.  */
> > > +    if (len <= 3) {
> > > +        return true;
> > > +    }
> > > +
> > > +    if (len >= 256) {
> > > +        return buffer_is_zero_len_256_plus(vbuf, len);
> > > +    } else {
> > > +        return buffer_is_zero_len_4_plus(vbuf, len);
> > > +    }
> > > +}
> > > +
> > >  bool test_buffer_is_zero_next_accel(void);
> > >  
> > >  /*
> > > diff --git a/util/bufferiszero.c b/util/bufferiszero.c
> > > index 3e6a5dfd63..3e5a014368 100644
> > > --- a/util/bufferiszero.c
> > > +++ b/util/bufferiszero.c
> > > @@ -26,30 +26,23 @@
> > >  #include "qemu/bswap.h"
> > >  #include "host/cpuinfo.h"
> > >  
> > > -static bool
> > > -buffer_zero_int(const void *buf, size_t len)
> > > +typedef uint64_t uint64_a __attribute__((may_alias));
> > > +
> > > +bool
> > > +buffer_is_zero_len_4_plus(const void *buf, size_t len)
> > >  {
> > >      if (unlikely(len < 8)) {
> > > -        /* For a very small buffer, simply accumulate all the bytes.  */
> > > -        const unsigned char *p = buf;
> > > -        const unsigned char *e = buf + len;
> > > -        unsigned char t = 0;
> > > -
> > > -        do {
> > > -            t |= *p++;
> > > -        } while (p < e);
> > > -
> > > -        return t == 0;
> > > +        /* Inline wrapper ensures len >= 4.  */
> > > +        return (ldl_he_p(buf) | ldl_he_p(buf + len - 4)) == 0;
> > >      } else {
> > > -        /* Otherwise, use the unaligned memory access functions to
> > > -           handle the beginning and end of the buffer, with a couple
> > > +        /* Use unaligned memory access functions to handle
> > > +           the beginning and end of the buffer, with a couple
> > >             of loops handling the middle aligned section.  */
> > > -        uint64_t t = ldq_he_p(buf);
> > > -        const uint64_t *p = (uint64_t *)(((uintptr_t)buf + 8) & -8);
> > > -        const uint64_t *e = (uint64_t *)(((uintptr_t)buf + len) & -8);
> > > +        uint64_t t = ldq_he_p(buf) | ldq_he_p(buf + len - 8);
> > > +        const uint64_a *p = (void *)(((uintptr_t)buf + 8) & -8);
> > > +        const uint64_a *e = (void *)(((uintptr_t)buf + len) & -8);
> > >  
> > > -        for (; p + 8 <= e; p += 8) {
> > > -            __builtin_prefetch(p + 8);
> > > +        for (; p < e - 7; p += 8) {
> > >              if (t) {
> > >                  return false;
> > >              }
> > > @@ -58,7 +51,6 @@ buffer_zero_int(const void *buf, size_t len)
> > >          while (p < e) {
> > >              t |= *p++;
> > >          }
> > > -        t |= ldq_he_p(buf + len - 8);
> > >  
> > >          return t == 0;
> > >      }
> > > @@ -67,124 +59,112 @@ buffer_zero_int(const void *buf, size_t len)
> > >  #if defined(CONFIG_AVX512F_OPT) || defined(CONFIG_AVX2_OPT) || 
> > > defined(__SSE2__)
> > >  #include <immintrin.h>
> > >  
> > > -/* Note that each of these vectorized functions require len >= 64.  */
> > > +/* Prevent the compiler from reassociating
> > > +   a chain of similar operations.  */
> > > +#define SSE_REASSOC_BARRIER(a, b) asm("" : "+x"(a), "+x"(b))
> > > +
> > > +/* Note that each of these vectorized functions assume len >= 256.  */
> > >  
> > >  static bool __attribute__((target("sse2")))
> > >  buffer_zero_sse2(const void *buf, size_t len)
> > >  {
> > > -    __m128i t = _mm_loadu_si128(buf);
> > > -    __m128i *p = (__m128i *)(((uintptr_t)buf + 5 * 16) & -16);
> > > -    __m128i *e = (__m128i *)(((uintptr_t)buf + len) & -16);
> > > -    __m128i zero = _mm_setzero_si128();
> > > +    /* Begin with an unaligned head and tail of 16 bytes.  */
> > > +    __m128i t = *(__m128i_u *)buf;
> > > +    __m128i t2 = *(__m128i_u *)(buf + len - 16);
> > > +    const __m128i *p = (void *)(((uintptr_t)buf + 16) & -16);
> > > +    const __m128i *e = (void *)(((uintptr_t)buf + len) & -16);
> > > +    __m128i zero = { 0 };
> > >  
> > > -    /* Loop over 16-byte aligned blocks of 64.  */
> > > -    while (likely(p <= e)) {
> > > -        __builtin_prefetch(p);
> > > +    /* Proceed with an aligned tail.  */
> > > +    t2 |= e[-7];
> > > +    t |= e[-6];
> > > +    /* Use the barrier to ensure two independent chains.  */
> > > +    SSE_REASSOC_BARRIER(t, t2);
> > > +    t2 |= e[-5];
> > > +    t |= e[-4];
> > > +    SSE_REASSOC_BARRIER(t, t2);
> > > +    t2 |= e[-3];
> > > +    t |= e[-2];
> > > +    SSE_REASSOC_BARRIER(t, t2);
> > > +    t2 |= e[-1];
> > > +    t |= t2;
> > > +
> > > +    /* Loop over 16-byte aligned blocks of 128.  */
> > > +    while (likely(p < e - 7)) {
> > >          t = _mm_cmpeq_epi8(t, zero);
> > >          if (unlikely(_mm_movemask_epi8(t) != 0xFFFF)) {
> > >              return false;
> > >          }
> > > -        t = p[-4] | p[-3] | p[-2] | p[-1];
> > > -        p += 4;
> > > +        t = p[0];
> > > +        t2 = p[1];
> > > +        SSE_REASSOC_BARRIER(t, t2);
> > > +        t |= p[2];
> > > +        t2 |= p[3];
> > > +        SSE_REASSOC_BARRIER(t, t2);
> > > +        t |= p[4];
> > > +        t2 |= p[5];
> > > +        SSE_REASSOC_BARRIER(t, t2);
> > > +        t |= p[6];
> > > +        t2 |= p[7];
> > > +        SSE_REASSOC_BARRIER(t, t2);
> > > +        t |= t2;
> > > +        p += 8;
> > >      }
> > >  
> > > -    /* Finish the aligned tail.  */
> > > -    t |= e[-3];
> > > -    t |= e[-2];
> > > -    t |= e[-1];
> > > -
> > > -    /* Finish the unaligned tail.  */
> > > -    t |= _mm_loadu_si128(buf + len - 16);
> > > -
> > >      return _mm_movemask_epi8(_mm_cmpeq_epi8(t, zero)) == 0xFFFF;
> > >  }
> > >  
> > >  #ifdef CONFIG_AVX2_OPT
> > > -static bool __attribute__((target("sse4")))
> > > -buffer_zero_sse4(const void *buf, size_t len)
> > > -{
> > > -    __m128i t = _mm_loadu_si128(buf);
> > > -    __m128i *p = (__m128i *)(((uintptr_t)buf + 5 * 16) & -16);
> > > -    __m128i *e = (__m128i *)(((uintptr_t)buf + len) & -16);
> > > -
> > > -    /* Loop over 16-byte aligned blocks of 64.  */
> > > -    while (likely(p <= e)) {
> > > -        __builtin_prefetch(p);
> > > -        if (unlikely(!_mm_testz_si128(t, t))) {
> > > -            return false;
> > > -        }
> > > -        t = p[-4] | p[-3] | p[-2] | p[-1];
> > > -        p += 4;
> > > -    }
> > > -
> > > -    /* Finish the aligned tail.  */
> > > -    t |= e[-3];
> > > -    t |= e[-2];
> > > -    t |= e[-1];
> > > -
> > > -    /* Finish the unaligned tail.  */
> > > -    t |= _mm_loadu_si128(buf + len - 16);
> > > -
> > > -    return _mm_testz_si128(t, t);
> > > -}
> > >  
> > >  static bool __attribute__((target("avx2")))
> > >  buffer_zero_avx2(const void *buf, size_t len)
> > >  {
> > >      /* Begin with an unaligned head of 32 bytes.  */
> > > -    __m256i t = _mm256_loadu_si256(buf);
> > > -    __m256i *p = (__m256i *)(((uintptr_t)buf + 5 * 32) & -32);
> > > -    __m256i *e = (__m256i *)(((uintptr_t)buf + len) & -32);
> > > +    __m256i t = *(__m256i_u *)buf;
> > > +    __m256i t2 = *(__m256i_u *)(buf + len - 32);
> > > +    const __m256i *p = (void *)(((uintptr_t)buf + 32) & -32);
> > > +    const __m256i *e = (void *)(((uintptr_t)buf + len) & -32);
> > > +    __m256i zero = { 0 };
> > >  
> > > -    /* Loop over 32-byte aligned blocks of 128.  */
> > > -    while (p <= e) {
> > > -        __builtin_prefetch(p);
> > > -        if (unlikely(!_mm256_testz_si256(t, t))) {
> > > +    /* Proceed with an aligned tail.  */
> > > +    t2 |= e[-7];
> > > +    t |= e[-6];
> > > +    SSE_REASSOC_BARRIER(t, t2);
> > > +    t2 |= e[-5];
> > > +    t |= e[-4];
> > > +    SSE_REASSOC_BARRIER(t, t2);
> > > +    t2 |= e[-3];
> > > +    t |= e[-2];
> > > +    SSE_REASSOC_BARRIER(t, t2);
> > > +    t2 |= e[-1];
> > > +    t |= t2;
> > > +
> > > +    /* Loop over 32-byte aligned blocks of 256.  */
> > > +    while (likely(p < e - 7)) {
> > > +        t = _mm256_cmpeq_epi8(t, zero);
> > > +        if (unlikely(_mm256_movemask_epi8(t) != 0xFFFFFFFF)) {
> > >              return false;
> > >          }
> > > -        t = p[-4] | p[-3] | p[-2] | p[-1];
> > > -        p += 4;
> > > -    } ;
> > > +        t = p[0];
> > > +        t2 = p[1];
> > > +        SSE_REASSOC_BARRIER(t, t2);
> > > +        t |= p[2];
> > > +        t2 |= p[3];
> > > +        SSE_REASSOC_BARRIER(t, t2);
> > > +        t |= p[4];
> > > +        t2 |= p[5];
> > > +        SSE_REASSOC_BARRIER(t, t2);
> > > +        t |= p[6];
> > > +        t2 |= p[7];
> > > +        SSE_REASSOC_BARRIER(t, t2);
> > > +        t |= t2;
> > > +        p += 8;
> > > +    }
> > >  
> > > -    /* Finish the last block of 128 unaligned.  */
> > > -    t |= _mm256_loadu_si256(buf + len - 4 * 32);
> > > -    t |= _mm256_loadu_si256(buf + len - 3 * 32);
> > > -    t |= _mm256_loadu_si256(buf + len - 2 * 32);
> > > -    t |= _mm256_loadu_si256(buf + len - 1 * 32);
> > > -
> > > -    return _mm256_testz_si256(t, t);
> > > +    return _mm256_movemask_epi8(_mm256_cmpeq_epi8(t, zero)) == 
> > > 0xFFFFFFFF;
> > >  }
> > >  #endif /* CONFIG_AVX2_OPT */
> > >  
> > > -#ifdef CONFIG_AVX512F_OPT
> > > -static bool __attribute__((target("avx512f")))
> > > -buffer_zero_avx512(const void *buf, size_t len)
> > > -{
> > > -    /* Begin with an unaligned head of 64 bytes.  */
> > > -    __m512i t = _mm512_loadu_si512(buf);
> > > -    __m512i *p = (__m512i *)(((uintptr_t)buf + 5 * 64) & -64);
> > > -    __m512i *e = (__m512i *)(((uintptr_t)buf + len) & -64);
> > > -
> > > -    /* Loop over 64-byte aligned blocks of 256.  */
> > > -    while (p <= e) {
> > > -        __builtin_prefetch(p);
> > > -        if (unlikely(_mm512_test_epi64_mask(t, t))) {
> > > -            return false;
> > > -        }
> > > -        t = p[-4] | p[-3] | p[-2] | p[-1];
> > > -        p += 4;
> > > -    }
> > > -
> > > -    t |= _mm512_loadu_si512(buf + len - 4 * 64);
> > > -    t |= _mm512_loadu_si512(buf + len - 3 * 64);
> > > -    t |= _mm512_loadu_si512(buf + len - 2 * 64);
> > > -    t |= _mm512_loadu_si512(buf + len - 1 * 64);
> > > -
> > > -    return !_mm512_test_epi64_mask(t, t);
> > > -
> > > -}
> > > -#endif /* CONFIG_AVX512F_OPT */
> > > -
> > >  /*
> > >   * Make sure that these variables are appropriately initialized when
> > >   * SSE2 is enabled on the compiler command-line, but the compiler is
> > > @@ -192,20 +172,17 @@ buffer_zero_avx512(const void *buf, size_t len)
> > >   */
> > >  #if defined(CONFIG_AVX512F_OPT) || defined(CONFIG_AVX2_OPT)
> > >  # define INIT_USED     0
> > > -# define INIT_LENGTH   0
> > > -# define INIT_ACCEL    buffer_zero_int
> > > +# define INIT_ACCEL    buffer_is_zero_len_4_plus
> > >  #else
> > >  # ifndef __SSE2__
> > >  #  error "ISA selection confusion"
> > >  # endif
> > >  # define INIT_USED     CPUINFO_SSE2
> > > -# define INIT_LENGTH   64
> > >  # define INIT_ACCEL    buffer_zero_sse2
> > >  #endif
> > >  
> > >  static unsigned used_accel = INIT_USED;
> > > -static unsigned length_to_accel = INIT_LENGTH;
> > > -static bool (*buffer_accel)(const void *, size_t) = INIT_ACCEL;
> > > +bool (*buffer_is_zero_len_256_plus)(const void *, size_t) = INIT_ACCEL;
> > >  
> > >  static unsigned __attribute__((noinline))
> > >  select_accel_cpuinfo(unsigned info)
> > > @@ -213,24 +190,18 @@ select_accel_cpuinfo(unsigned info)
> > >      /* Array is sorted in order of algorithm preference. */
> > >      static const struct {
> > >          unsigned bit;
> > > -        unsigned len;
> > >          bool (*fn)(const void *, size_t);
> > >      } all[] = {
> > > -#ifdef CONFIG_AVX512F_OPT
> > > -        { CPUINFO_AVX512F, 256, buffer_zero_avx512 },
> > > -#endif
> > >  #ifdef CONFIG_AVX2_OPT
> > > -        { CPUINFO_AVX2,    128, buffer_zero_avx2 },
> > > -        { CPUINFO_SSE4,     64, buffer_zero_sse4 },
> > > +        { CPUINFO_AVX2,   buffer_zero_avx2 },
> > >  #endif
> > > -        { CPUINFO_SSE2,     64, buffer_zero_sse2 },
> > > -        { CPUINFO_ALWAYS,    0, buffer_zero_int },
> > > +        { CPUINFO_SSE2,   buffer_zero_sse2 },
> > > +        { CPUINFO_ALWAYS, buffer_is_zero_len_4_plus },
> > >      };
> > >  
> > >      for (unsigned i = 0; i < ARRAY_SIZE(all); ++i) {
> > >          if (info & all[i].bit) {
> > > -            length_to_accel = all[i].len;
> > > -            buffer_accel = all[i].fn;
> > > +            buffer_is_zero_len_256_plus = all[i].fn;
> > >              return all[i].bit;
> > >          }
> > >      }
> > > @@ -256,35 +227,11 @@ bool test_buffer_is_zero_next_accel(void)
> > >      return used;
> > >  }
> > >  
> > > -static bool select_accel_fn(const void *buf, size_t len)
> > > -{
> > > -    if (likely(len >= length_to_accel)) {
> > > -        return buffer_accel(buf, len);
> > > -    }
> > > -    return buffer_zero_int(buf, len);
> > > -}
> > > -
> > >  #else
> > > -#define select_accel_fn  buffer_zero_int
> > > +#define select_accel_fn  buffer_is_zero_len_4_plus
> > >  bool test_buffer_is_zero_next_accel(void)
> > >  {
> > >      return false;
> > >  }
> > >  #endif
> > >  
> > > -/*
> > > - * Checks if a buffer is all zeroes
> > > - */
> > > -bool buffer_is_zero(const void *buf, size_t len)
> > > -{
> > > -    if (unlikely(len == 0)) {
> > > -        return true;
> > > -    }
> > > -
> > > -    /* Fetch the beginning of the buffer while we select the 
> > > accelerator.  */
> > > -    __builtin_prefetch(buf);
> > > -
> > > -    /* Use an optimized zero check if possible.  Note that this also
> > > -       includes a check for an unrolled loop over 64-bit integers.  */
> > > -    return select_accel_fn(buf, len);
> > > -}
> > > 
> > 
>