| Message ID | 20240217003918.52229-7-richard.henderson@linaro.org |
|---|---|
| State | Superseded |
| Headers | show |
| Series | Optimize buffer_is_zero | expand |
On Fri, 16 Feb 2024, 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. I guess it did not carry typedef uint64_t uint64_a __attribute__((may_alias)); along the way, not a big deal since Qemu builds with -fno-strict-aliasing, but I felt it was nice to be explicit in the code about that. Am I expected to give Reviewed-by's to you? I did read the code to the best of my ability and did not spot any issues. Copies of the old comment will need updating: > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > util/bufferiszero.c | 86 +++++++++++++++++++++++++++------------------ > 1 file changed, 52 insertions(+), 34 deletions(-) > > diff --git a/util/bufferiszero.c b/util/bufferiszero.c > index 02df82b4ff..a904b747c7 100644 > --- a/util/bufferiszero.c > +++ b/util/bufferiszero.c > @@ -28,40 +28,58 @@ > > 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) > { [snip] > + /* > + * Use unaligned memory access functions to handle > + * the beginning and end of the buffer, with a couple > + * of loops handling the middle aligned section. > + */ ... here, there is only one loop now, not two, > + 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); > + > + 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, with a couple > + * of loops handling the middle aligned section. > + */ ... and likewise here. Alexander
On 2/17/24 02:13, Alexander Monakov wrote: > > On Fri, 16 Feb 2024, 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. > > I guess it did not carry > > typedef uint64_t uint64_a __attribute__((may_alias)); > > along the way, not a big deal since Qemu builds with -fno-strict-aliasing, > but I felt it was nice to be explicit in the code about that. I suppose. My thought was that because of -fno-strict-aliasing, we don't care about aliasing anywhere else in the code base, and then explicitly caring about it here could cause confusion. > > Am I expected to give Reviewed-by's to you? I did read the code to the > best of my ability and did not spot any issues. r-b is not necessary, though thanks for the review. >> + /* >> + * Use unaligned memory access functions to handle >> + * the beginning and end of the buffer, with a couple >> + * of loops handling the middle aligned section. >> + */ > > ... here, there is only one loop now, not two, Thanks. Fixed. r~
diff --git a/util/bufferiszero.c b/util/bufferiszero.c index 02df82b4ff..a904b747c7 100644 --- a/util/bufferiszero.c +++ b/util/bufferiszero.c @@ -28,40 +28,58 @@ 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, with a couple + * of loops handling the middle aligned section. + */ + 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); + + 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, with a couple + * of loops handling the middle aligned section. + */ + 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 +191,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 +229,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 +250,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 | 86 +++++++++++++++++++++++++++------------------ 1 file changed, 52 insertions(+), 34 deletions(-)