[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);
> > -}
> >
>
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Re: [PATCH v2] Optimize buffer_is_zero,
Alexander Monakov <=