| Message ID | 20240424225705.929812-7-richard.henderson@linaro.org |
|---|---|
| State | Superseded |
| Headers | show |
| Series | Optimize buffer_is_zero | expand |
On 25/4/24 00:57, Richard Henderson wrote: > Split less-than and greater-than 256 cases. > Use unaligned accesses for head and tail. > Avoid using out-of-bounds pointers in loop boundary conditions. > > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > util/bufferiszero.c | 85 +++++++++++++++++++++++++++------------------ > 1 file changed, 51 insertions(+), 34 deletions(-) > > diff --git a/util/bufferiszero.c b/util/bufferiszero.c > index 02df82b4ff..c9a7ded016 100644 > --- a/util/bufferiszero.c > +++ b/util/bufferiszero.c > @@ -28,40 +28,57 @@ > > static bool (*buffer_is_zero_accel)(const void *, size_t); > > -static bool buffer_is_zero_integer(const void *buf, size_t len) > +static bool buffer_is_zero_int_lt256(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; > + uint64_t t; > + const uint64_t *p, *e; > > - do { > - t |= *p++; > - } while (p < e); > - > - return t == 0; > - } else { > - /* Otherwise, use the 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); > - > - for (; p + 8 <= e; p += 8) { > - if (t) { > - return false; > - } > - t = p[0] | p[1] | p[2] | p[3] | p[4] | p[5] | p[6] | p[7]; > - } > - while (p < e) { > - t |= *p++; > - } > - t |= ldq_he_p(buf + len - 8); > - > - return t == 0; > + /* > + * Use unaligned memory access functions to handle > + * the beginning and end of the buffer. > + */ > + if (unlikely(len <= 8)) { > + return (ldl_he_p(buf) | ldl_he_p(buf + len - 4)) == 0; > } > + > + t = ldq_he_p(buf) | ldq_he_p(buf + len - 8); Here we read #0 and #31, ... > + p = QEMU_ALIGN_PTR_DOWN(buf + 8, 8); > + e = QEMU_ALIGN_PTR_DOWN(buf + len - 1, 8); > + > + /* Read 0 to 31 aligned words from the middle. */ ... so here is #1 to #30? > + while (p < e) { > + t |= *p++; > + } > + return t == 0; > +} Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org>
On 4/29/24 05:18, Philippe Mathieu-Daudé wrote: >> + >> + t = ldq_he_p(buf) | ldq_he_p(buf + len - 8); > > Here we read #0 and #31, ... > >> + p = QEMU_ALIGN_PTR_DOWN(buf + 8, 8); >> + e = QEMU_ALIGN_PTR_DOWN(buf + len - 1, 8); >> + >> + /* Read 0 to 31 aligned words from the middle. */ > > ... so here is #1 to #30? Not indexes, but count. There may be zero words remaining in the middle, etc. r~
On 29/4/24 14:31, Richard Henderson wrote: > On 4/29/24 05:18, Philippe Mathieu-Daudé wrote: >>> + >>> + t = ldq_he_p(buf) | ldq_he_p(buf + len - 8); >> >> Here we read #0 and #31, ... >> >>> + p = QEMU_ALIGN_PTR_DOWN(buf + 8, 8); >>> + e = QEMU_ALIGN_PTR_DOWN(buf + len - 1, 8); >>> + >>> + /* Read 0 to 31 aligned words from the middle. */ >> >> ... so here is #1 to #30? > > Not indexes, but count. There may be zero words remaining in the > middle, etc. Oh, got it, thanks!
diff --git a/util/bufferiszero.c b/util/bufferiszero.c index 02df82b4ff..c9a7ded016 100644 --- a/util/bufferiszero.c +++ b/util/bufferiszero.c @@ -28,40 +28,57 @@ static bool (*buffer_is_zero_accel)(const void *, size_t); -static bool buffer_is_zero_integer(const void *buf, size_t len) +static bool buffer_is_zero_int_lt256(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; + uint64_t t; + const uint64_t *p, *e; - do { - t |= *p++; - } while (p < e); - - return t == 0; - } else { - /* Otherwise, use the 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); - - for (; p + 8 <= e; p += 8) { - if (t) { - return false; - } - t = p[0] | p[1] | p[2] | p[3] | p[4] | p[5] | p[6] | p[7]; - } - while (p < e) { - t |= *p++; - } - t |= ldq_he_p(buf + len - 8); - - return t == 0; + /* + * Use unaligned memory access functions to handle + * the beginning and end of the buffer. + */ + if (unlikely(len <= 8)) { + return (ldl_he_p(buf) | ldl_he_p(buf + len - 4)) == 0; } + + t = ldq_he_p(buf) | ldq_he_p(buf + len - 8); + p = QEMU_ALIGN_PTR_DOWN(buf + 8, 8); + e = QEMU_ALIGN_PTR_DOWN(buf + len - 1, 8); + + /* Read 0 to 31 aligned words from the middle. */ + while (p < e) { + t |= *p++; + } + return t == 0; +} + +static bool buffer_is_zero_int_ge256(const void *buf, size_t len) +{ + /* + * Use unaligned memory access functions to handle + * the beginning and end of the buffer. + */ + uint64_t t = ldq_he_p(buf) | ldq_he_p(buf + len - 8); + const uint64_t *p = QEMU_ALIGN_PTR_DOWN(buf + 8, 8); + const uint64_t *e = QEMU_ALIGN_PTR_DOWN(buf + len - 1, 8); + + /* Collect a partial block at the tail end. */ + t |= e[-7] | e[-6] | e[-5] | e[-4] | e[-3] | e[-2] | e[-1]; + + /* + * Loop over 64 byte blocks. + * With the head and tail removed, e - p >= 30, + * so the loop must iterate at least 3 times. + */ + do { + if (t) { + return false; + } + t = p[0] | p[1] | p[2] | p[3] | p[4] | p[5] | p[6] | p[7]; + p += 8; + } while (p < e - 7); + + return t == 0; } #if defined(CONFIG_AVX2_OPT) || defined(__SSE2__) @@ -173,7 +190,7 @@ select_accel_cpuinfo(unsigned info) { CPUINFO_AVX2, buffer_zero_avx2 }, #endif { CPUINFO_SSE2, buffer_zero_sse2 }, - { CPUINFO_ALWAYS, buffer_is_zero_integer }, + { CPUINFO_ALWAYS, buffer_is_zero_int_ge256 }, }; for (unsigned i = 0; i < ARRAY_SIZE(all); ++i) { @@ -211,7 +228,7 @@ bool test_buffer_is_zero_next_accel(void) return false; } -#define INIT_ACCEL buffer_is_zero_integer +#define INIT_ACCEL buffer_is_zero_int_ge256 #endif static bool (*buffer_is_zero_accel)(const void *, size_t) = INIT_ACCEL; @@ -232,7 +249,7 @@ bool buffer_is_zero_ool(const void *buf, size_t len) if (likely(len >= 256)) { return buffer_is_zero_accel(buf, len); } - return buffer_is_zero_integer(buf, len); + return buffer_is_zero_int_lt256(buf, len); } bool buffer_is_zero_ge256(const void *buf, size_t len)
Split less-than and greater-than 256 cases. Use unaligned accesses for head and tail. Avoid using out-of-bounds pointers in loop boundary conditions. Signed-off-by: Richard Henderson <richard.henderson@linaro.org> --- util/bufferiszero.c | 85 +++++++++++++++++++++++++++------------------ 1 file changed, 51 insertions(+), 34 deletions(-)