Re: [PATCH v2] Optimize buffer_is_zero

[Alexander Monakov]

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