qemu-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [PATCH v2] Optimize buffer_is_zero


From: Alexander Monakov
Subject: Re: [PATCH v2] Optimize buffer_is_zero
Date: Thu, 14 Dec 2023 19:48:37 +0300 (MSK)

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);
> > -}
> > 
> 



reply via email to

[Prev in Thread] Current Thread [Next in Thread]