buffer_is_zero / migration optimizations
v4 cover buffer_is_zero / migration optimizations
this is v4 of my patch series with various optimizations in zero buffer checking and migration tweaks.
thanks especially to Eric Blake for reviewing.
v4:
- do not inline buffer_find_nonzero_offset()
- inline can_usebuffer_find_nonzero_offset() correctly
- readd asserts in buffer_find_nonzero_offset() as profiling shows they do not hurt.
- change last occurences of scalar 8 by BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
- avoid deferencing p already in patch 5 where we know that the page (p) is zero
- explicitly set bytes_sent = 0 if we skip a zero page. bytes_sent was 0 before, but it was not obvious.
- add accounting information for skipped zero pages
- fix errors reported by checkpatch.pl
v3:
- remove asserts, inline functions and add a check function if buffer_find_nonzero_offset() can be used.
- use above check function in buffer_is_zero() and find_next_bit().
- use buffer_is_nonzero_offset() directly to find zero pages. we know that all requirements are met for memory pages.
- fix C89 violation in buffer_is_zero().
- avoid derefencing p in ram_save_block() if we already know the page is zero.
- fix initialization of last_offset in reset_ram_globals().
- avoid skipping pages with offset == 0 in bulk stage in migration_bitmap_find_and_reset_dirty().
- compared to v1 check for zero pages also after bulk ram migration as there are guests (e.g. Windows) which zero out large amount of memory while running.
v2:
- fix description, add trivial zero check and add asserts to buffer_find_nonzero_offset.
- add a constant for the unroll factor of buffer_find_nonzero_offset
- replace is_dup_page() by buffer_is_zero()
- added test results to xbzrle patch
- optimize descriptions
Peter Lieven (9):
move vector definitions to qemu-common.h
cutils: add a function to find non-zero content in a buffer
buffer_is_zero: use vector optimizations if possible
bitops: use vector algorithm to optimize find_next_bit()
migration: search for zero instead of dup pages
migration: add an indicator for bulk state of ram migration
migration: do not sent zero pages in bulk stage
migration: do not search dirty pages in bulk stage
migration: use XBZRLE only after bulk stage
arch_init.c | 74 +++++++++++++++++++---------------------- hmp.c | 2 ++ include/migration/migration.h | 2 ++ include/qemu-common.h | 37 +++++++++++++++++++++ migration.c | 3 +- qapi-schema.json | 6 ++-- qmp-commands.hx | 3 +- util/bitops.c | 24 +++++++++++-- util/cutils.c | 50 ++++++++++++++++++++++++++++ 9 files changed, 155 insertions(+), 46 deletions(-)
Signature · 1 line
1.7.9.5
PATCH v4 1/9 move vector definitions to qemu-common.h
vector optimizations will now be used at various places not just in is_dup_page() in arch_init.c
this patch also adds a zero splat vector.
--- arch_init.c | 20 -------------------- include/qemu-common.h | 24 ++++++++++++++++++++++++ 2 files changed, 24 insertions(+), 20 deletions(-)
arch_init.c +0 -20
@@ -114,26 +114,6 @@ const uint32_t arch_type = QEMU_ARCH;#define RAM_SAVE_FLAG_CONTINUE 0x20#define RAM_SAVE_FLAG_XBZRLE 0x40 -#ifdef __ALTIVEC__ -#include <altivec.h> -#define VECTYPE vector unsigned char -#define SPLAT (p) vec_splat(vec_ld(0, p), 0) -#define ALL_EQ (v1, v2) vec_all_eq(v1, v2) -/* altivec.h may redefine the bool macro as vector type. -* Reset it to POSIX semantics. */ -#undef bool -#define bool _Bool -#elif defined __SSE2__ -#include <emmintrin.h> -#define VECTYPE __m128i -#define SPLAT (p) _mm_set1_epi8(*(p)) -#define ALL_EQ (v1, v2) (_mm_movemask_epi8(_mm_cmpeq_epi8(v1, v2)) == 0xFFFF) -#else -#define VECTYPE unsigned long -#define SPLAT (p) (*(p) * (~0UL / 255)) -#define ALL_EQ (v1, v2) ((v1) == (v2)) -#endif - static struct defconfig_file { const char *filename;
include/qemu-common.h +24 -0
@@ -448,4 +448,28 @@ int uleb128_decode_small(const uint8_t *in, uint32_t *n);void hexdump (const char *buf,FILE *fp,const char *prefix,size_t size); +/* vector definitions */ +#ifdef __ALTIVEC__ +#include <altivec.h> +#define VECTYPE vector unsigned char +#define SPLAT (p) vec_splat(vec_ld(0, p), 0) +#define ZERO_SPLAT vec_splat(vec_ld(0, 0), 0) +#define ALL_EQ (v1, v2) vec_all_eq(v1, v2) +/* altivec.h may redefine the bool macro as vector type. +* Reset it to POSIX semantics. */ +#undef bool +#define bool _Bool +#elif defined __SSE2__ +#include <emmintrin.h> +#define VECTYPE __m128i +#define SPLAT (p) _mm_set1_epi8(*(p)) +#define ZERO_SPLAT _mm_setzero_si128() +#define ALL_EQ (v1, v2) (_mm_movemask_epi8(_mm_cmpeq_epi8(v1, v2)) == 0xFFFF) +#else +#define VECTYPE unsigned long +#define SPLAT (p) (*(p) * (~0UL / 255)) +#define ZERO_SPLAT 0x0UL +#define ALL_EQ (v1, v2) ((v1) == (v2)) +#endif +#endif
Signature · 1 line
1.7.9.5
Re: [Qemu-devel] [PATCHv4 1/9] move vector definitions to qemu-common.h
Quoted 48 lines · Peter Lieven
vector optimizations will now be used at various places not just in
is_dup_page()inarch_init.cthis patch also adds a zero splat vector.
Signed-off-by Peter Lieven <[email protected]>Reviewed-by Eric Blake <[email protected]>--- arch_init.c | 20 -------------------- include/qemu-common.h | 24 ++++++++++++++++++++++++ 2 files changed, 24 insertions(+), 20 deletions(-)arch_init.c +0
-20@@ -114,26 +114,6 @@ const uint32_t arch_type = QEMU_ARCH;#define RAM_SAVE_FLAG_CONTINUE 0x20#define RAM_SAVE_FLAG_XBZRLE 0x40 -#ifdef __ALTIVEC__ -#include <altivec.h> -#define VECTYPE vector unsigned char -#define SPLAT (p) vec_splat(vec_ld(0, p), 0) -#define ALL_EQ (v1, v2) vec_all_eq(v1, v2) -/* altivec.h may redefine the bool macro as vector type. -* Reset it to POSIX semantics. */ -#undef bool -#define bool _Bool -#elif defined __SSE2__ -#include <emmintrin.h> -#define VECTYPE __m128i -#define SPLAT (p) _mm_set1_epi8(*(p)) -#define ALL_EQ (v1, v2) (_mm_movemask_epi8(_mm_cmpeq_epi8(v1, v2)) == 0xFFFF) -#else -#define VECTYPE unsigned long -#define SPLAT (p) (*(p) * (~0UL / 255)) -#define ALL_EQ (v1, v2) ((v1) == (v2)) -#endif - static struct defconfig_file { const char *filename;include/qemu-common.h +0
-0
include/qemu-common.h int uleb128_decode_small(const uint8_t *in, uint32_t *n); · line 456
Quoted 9 lines
include/qemu-common.h +6
-0@@ -448,4 +448,28 @@ int uleb128_decode_small(const uint8_t *in, uint32_t *n);void hexdump (const char *buf,FILE *fp,const char *prefix,size_t size); +/* vector definitions */ +#ifdef __ALTIVEC__ +#include <altivec.h> +#define VECTYPE vector unsigned char +#define SPLAT (p) vec_splat(vec_ld(0, p), 0) +#define ZERO_SPLAT vec_splat(vec_ld(0, 0), 0)
This is new macro please move it to a separate patch Orit
Quoted 21 lines
include/qemu-common.h +18
-0+#define ALL_EQ (v1, v2) vec_all_eq(v1, v2) +/* altivec.h may redefine the bool macro as vector type. +* Reset it to POSIX semantics. */ +#undef bool +#define bool _Bool +#elif defined __SSE2__ +#include <emmintrin.h> +#define VECTYPE __m128i +#define SPLAT (p) _mm_set1_epi8(*(p)) +#define ZERO_SPLAT _mm_setzero_si128() +#define ALL_EQ (v1, v2) (_mm_movemask_epi8(_mm_cmpeq_epi8(v1, v2)) == 0xFFFF) +#else +#define VECTYPE unsigned long +#define SPLAT (p) (*(p) * (~0UL / 255)) +#define ZERO_SPLAT 0x0UL +#define ALL_EQ (v1, v2) ((v1) == (v2)) +#endif +#endif
PATCH v4 2/9 cutils: add a function to find non-zero content in a buffer
In reply to Peter Lieventhis adds buffer_find_nonzero_offset() which is a SSE2/Altivec optimized function that searches for non-zero content in a buffer.
due to the optimizations used in the function there are restrictions on buffer address and search length. the function can_use_buffer_find_nonzero_content() can be used to check if the function can be used safely.
--- include/qemu-common.h | 13 +++++++++++++ util/cutils.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 insertions(+)
include/qemu-common.h +13 -0
@@ -472,4 +472,17 @@ void hexdump(const char *buf, FILE *fp, const char *prefix, size_t size);#define ALL_EQ (v1, v2) ((v1) == (v2))#endif +#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8 +static inline bool +can_use_buffer_find_nonzero_offset (const void *buf,size_t len) +{ +if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 + && ((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ) { +return true; + } +return false; +} +size_t buffer_find_nonzero_offset (const void *buf,size_t len); +#endif
util/cutils.c +45 -0
51 lines not on this page · raw message
Signature · 1 line
1.7.9.5
Re: [Qemu-devel] [PATCHv4 2/9] cutils: add a function to find non-zero content in a buffer
Quoted 15 lines · Peter Lieven
this adds
buffer_find_nonzero_offset()which is a SSE2/Altivec optimized function that searches for non-zero content in a buffer.due to the optimizations used in the function there are restrictions on buffer address and search length. the function
can_use_buffer_find_nonzero_content()can be used to check if the function can be used safely.Signed-off-by Peter Lieven <[email protected]>--- include/qemu-common.h | 13 +++++++++++++ util/cutils.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 insertions(+)
include/qemu-common.h void hexdump(const char *buf, FILE *fp, const char *prefix, size_t size); · line 481
Quoted 7 lines
include/qemu-common.h +7
-0+#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8 +static inline bool +can_use_buffer_find_nonzero_offset (const void *buf,size_t len) +{ +if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 + && ((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ) {
I know that emacs tends to indent the second line to the column after the ( that it is associated with, as in:
+ if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
+ * sizeof(VECTYPE)) == 0
+ && ((uintptr_t) buf) % sizeof(VECTYPE) == 0) {
But since checkpatch.pl didn't complain, and since I'm not sure if there is a codified qemu indentation style, and since I _am_ sure that not everyone uses emacs [hi, vi guys], it's not worth respinning. A maintainer can touch it up if desired.
util/cutils.c int qemu_fdatasync(int fd) · line 169
Quoted 10 lines
util/cutils.c +10
-0+ +size_t buffer_find_nonzero_offset (const void *buf,size_t len) +{ +VECTYPE *p = (VECTYPE *)buf; +VECTYPE zero =ZERO_SPLAT ; +size_t i; + +assert (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 ); +assert (((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 );
I would have written this:
assert(can_use_buffer_find_nonzero_offset(buf, len));
But that's cosmetic, and compiles to the same code, so it's not worth a respin.
You've addressed my concerns on v3.
Signature · 2 lines
Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
Re: [Qemu-devel] [PATCHv4 2/9] cutils: add a function to find non-zero content in a buffer
Am 22.03.2013 20:37, schrieb Eric Blake:
Quoted 29 lines · Peter Lieven
Quoted 14 lines
this adds
buffer_find_nonzero_offset()which is a SSE2/Altivec optimized function that searches for non-zero content in a buffer.due to the optimizations used in the function there are restrictions on buffer address and search length. the function
can_use_buffer_find_nonzero_content()can be used to check if the function can be used safely.Signed-off-by Peter Lieven <[email protected]>--- include/qemu-common.h | 13 +++++++++++++ util/cutils.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 insertions(+)include/qemu-common.h void hexdump(const char *buf, FILE *fp, const char *prefix, size_t size); · line 481
Quoted 7 lines
include/qemu-common.h +7
-0+#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8 +static inline bool +can_use_buffer_find_nonzero_offset (const void *buf,size_t len) +{ +if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 + && ((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ) {I know that emacs tends to indent the second line to the column after the ( that it is associated with, as in:
include/qemu-common.h +3
-0+if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 + && ((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ) {
Quoted 4 lines
But since checkpatch.pl didn't complain, and since I'm not sure if there is a codified qemu indentation style, and since I _am_ sure that not everyone uses emacs [hi, vi guys], it's not worth respinning. A maintainer can touch it up if desired.
Actually, I was totally unsure how to indent this. Maybe just give a hint what you would like to see. As I will replace patch 4 with an earlier version that is not vector optimized, but uses loop unrolling, I will have to do a v5 and so I can fix this.
Quoted 13 lines
util/cutils.c int qemu_fdatasync(int fd) · line 169
Quoted 11 lines
util/cutils.c +10
-0+ +size_t buffer_find_nonzero_offset (const void *buf,size_t len) +{ +VECTYPE *p = (VECTYPE *)buf; +VECTYPE zero =ZERO_SPLAT ; +size_t i; + +assert (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 ); +assert (((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 );I would have written this:
Quoted 1 line
assert(can_use_buffer_find_nonzero_offset(buf, len));
Good point. Will be changed in v5.
Quoted 7 lines
But that's cosmetic, and compiles to the same code, so it's not worth a respin.
You've addressed my concerns on v3.
Reviewed-by Eric Blake <[email protected]>
Peter
[Qemu-devel] indentation hints [was: [PATCHv4 2/9] cutils: add a function to find non-zero content in a buffer]
Quoted 6 lines · Peter Lieven
Quoted 6 lines
include/qemu-common.h void hexdump(const char *buf, FILE *fp, const char *prefix, size_t size); · line 481
Quoted 3 lines
include/qemu-common.h +3
-0+if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 + && ((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ) {I know that emacs tends to indent the second line to the column after the ( that it is associated with, as in:
Quoted 8 lines
include/qemu-common.h void hexdump(const char *buf, FILE *fp, const char *prefix, size_t size); · line 481
Quoted 4 lines
include/qemu-common.h +3
-0+if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 + && ((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ) {Actually, I was totally unsure how to indent this. Maybe just give a hint what you would like to see.
I thought I did just that, with my rewrite of your line (best if you view the mail in fixed-width font) :)
Quoted 3 lines
As I will replace patch 4 with
an earlier version that is not vector optimized, but uses loop unrolling, I will have to do a v5 and so I can fix this.
Note that qemu.git already has a .exrc file that enables default vi settings for vim users; I'm not sure if there is a counterpart .dir-locals.el file to set up emacs settings, but someone probably has one. Ultimately, having instructions on how to set up your editor so that 'TAB' just magically indents to the preferred style seems like a tip worth having on the wiki page on contributing a patch, but I'm not sure I'm the one to provide such a patch (since I focus most of my qemu work on reviewing other's patches, and not writing my own, I don't really have my own preferred editor set up to indent in a qemu style).
Signature · 2 lines
Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
Re: [Qemu-devel] indentation hints [was: [PATCHv4 2/9] cutils: add a function to find non-zero content in a buffer]
Quoted 3 lines · Eric Blake
Note that qemu.git already has a .exrc file that enables default vi settings for vim users; I'm not sure if there is a counterpart .dir-locals.el file to set up emacs settings
My .emacs has the following config:
https://wiki.linaro.org/PeterMaydell/QemuEmacsStyle
(it doesn't get things perfect but it's pretty close.)
-- PMM
Re: [Qemu-devel] [PATCHv4 2/9] cutils: add a function to find non-zero content in a buffer
In reply to Peter LievenQuoted 65 lines · Peter Lieven
this adds
buffer_find_nonzero_offset()which is a SSE2/Altivec optimized function that searches for non-zero content in a buffer.due to the optimizations used in the function there are restrictions on buffer address and search length. the function
can_use_buffer_find_nonzero_content()can be used to check if the function can be used safely.Signed-off-by Peter Lieven <[email protected]>--- include/qemu-common.h | 13 +++++++++++++ util/cutils.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 insertions(+)include/qemu-common.h +13
-0@@ -472,4 +472,17 @@ void hexdump(const char *buf, FILE *fp, const char *prefix, size_t size);#define ALL_EQ (v1, v2) ((v1) == (v2))#endif +#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8 +static inline bool +can_use_buffer_find_nonzero_offset (const void *buf,size_t len) +{ +if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 + && ((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ) { +return true; + } +return false; +} +size_t buffer_find_nonzero_offset (const void *buf,size_t len); +#endif util/cutils.c +20
-0@@ -143,6 +143,51 @@ int qemu_fdatasync(int fd) }/* +* Searches for an area with non-zero content in a buffer +* +* Attention! The len must be a multiple of +* BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE) +* and addr must be a multiple of sizeof(VECTYPE) due to +* restriction of optimizations in this function. +* +* can_use_buffer_find_nonzero_offset() can be used to check +* these requirements. +* +* The return value is the offset of the non-zero area rounded +* down to BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE). +* If the buffer is all zero the return value is equal to len. +*/ + +size_t buffer_find_nonzero_offset (const void *buf,size_t len) +{ +VECTYPE *p = (VECTYPE *)buf; +VECTYPE zero =ZERO_SPLAT ; +size_t i;
util/cutils.c int qemu_fdatasync(int fd) · line 175
Quoted 10 lines
util/cutils.c +10
-0+ +assert (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 ); +assert (((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ); + +if (*((const long *) buf)) { +return 0 ; + } + + for (i = 0; i < len / sizeof(VECTYPE);
Why not put len/sizeof(VECTYPE) in a variable?
Orit
Quoted 19 lines
util/cutils.c +15
-0+ i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) { +VECTYPE tmp0 = p[i +0 ] | p[i +1 ]; +VECTYPE tmp1 = p[i +2 ] | p[i +3 ]; +VECTYPE tmp2 = p[i +4 ] | p[i +5 ]; +VECTYPE tmp3 = p[i +6 ] | p[i +7 ]; +VECTYPE tmp01 = tmp0 | tmp1; +VECTYPE tmp23 = tmp2 | tmp3; +if (!ALL_EQ (tmp01 | tmp23, zero)) { +break ; + } + } +return i *sizeof (VECTYPE ); +} + +/* * Checks if a buffer is all zeroes * * Attention! The len must be a multiple of 4 * sizeof(long) due to
Re: [Qemu-devel] [PATCHv4 2/9] cutils: add a function to find non-zero content in a buffer
Am 25.03.2013 um 09:53 schrieb Orit Wasserman <[email protected]>:
Quoted 69 lines · Peter Lieven
Quoted 68 lines
this adds
buffer_find_nonzero_offset()which is a SSE2/Altivec optimized function that searches for non-zero content in a buffer.due to the optimizations used in the function there are restrictions on buffer address and search length. the function
can_use_buffer_find_nonzero_content()can be used to check if the function can be used safely.Signed-off-by Peter Lieven <[email protected]>---
include/qemu-common.h | 13 +++++++++++++ util/cutils.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 insertions(+)include/qemu-common.h +13
-0@@ -472,4 +472,17 @@ void hexdump(const char *buf, FILE *fp, const char *prefix, size_t size);#define ALL_EQ (v1, v2) ((v1) == (v2))#endif +#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8 +static inline bool +can_use_buffer_find_nonzero_offset (const void *buf,size_t len) +{ +if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 + && ((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ) { +return true; + } +return false; +} +size_t buffer_find_nonzero_offset (const void *buf,size_t len); +#endif util/cutils.c +23
-0@@ -143,6 +143,51 @@ int qemu_fdatasync(int fd) }/* +* Searches for an area with non-zero content in a buffer +* +* Attention! The len must be a multiple of +* BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE) +* and addr must be a multiple of sizeof(VECTYPE) due to +* restriction of optimizations in this function. +* +* can_use_buffer_find_nonzero_offset() can be used to check +* these requirements. +* +* The return value is the offset of the non-zero area rounded +* down to BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE). +* If the buffer is all zero the return value is equal to len. +*/ + +size_t buffer_find_nonzero_offset (const void *buf,size_t len) +{ +VECTYPE *p = (VECTYPE *)buf; +VECTYPE zero =ZERO_SPLAT ; +size_t i; + +assert (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 );
Quoted 8 lines
util/cutils.c int qemu_fdatasync(int fd) · line 175
Quoted 7 lines
util/cutils.c +7
-0+assert (((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ); + +if (*((const long *) buf)) { +return 0 ; + } + + for (i = 0; i < len / sizeof(VECTYPE);Why not put len/sizeof(VECTYPE) in a variable?
are you afraid that there is a division at each iteration?
sizeof(VECTYPE) is a power of 2 so i think the compiler will optimize it to a >> at compile time.
I would also be ok with writing len /= sizeof(VECTYPE) before the loop.
Peter
Quoted 21 lines
Orit
Quoted 19 lines
util/cutils.c +15
-0+ i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) { +VECTYPE tmp0 = p[i +0 ] | p[i +1 ]; +VECTYPE tmp1 = p[i +2 ] | p[i +3 ]; +VECTYPE tmp2 = p[i +4 ] | p[i +5 ]; +VECTYPE tmp3 = p[i +6 ] | p[i +7 ]; +VECTYPE tmp01 = tmp0 | tmp1; +VECTYPE tmp23 = tmp2 | tmp3; +if (!ALL_EQ (tmp01 | tmp23, zero)) { +break ; + } + } +return i *sizeof (VECTYPE ); +} + +/* * Checks if a buffer is all zeroes * * Attention! The len must be a multiple of 4 * sizeof(long) due to
Re: [Qemu-devel] [PATCHv4 2/9] cutils: add a function to find non-zero content in a buffer
Quoted 81 lines · Peter Lieven
Am 25.03.2013 um 09:53 schrieb Orit Wasserman <[email protected]>:
Quoted 69 lines · Peter Lieven
Quoted 68 lines
this adds
buffer_find_nonzero_offset()which is a SSE2/Altivec optimized function that searches for non-zero content in a buffer.due to the optimizations used in the function there are restrictions on buffer address and search length. the function
can_use_buffer_find_nonzero_content()can be used to check if the function can be used safely.Signed-off-by Peter Lieven <[email protected]>---
include/qemu-common.h | 13 +++++++++++++ util/cutils.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 insertions(+)include/qemu-common.h +13
-0@@ -472,4 +472,17 @@ void hexdump(const char *buf, FILE *fp, const char *prefix, size_t size);#define ALL_EQ (v1, v2) ((v1) == (v2))#endif +#define BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR 8 +static inline bool +can_use_buffer_find_nonzero_offset (const void *buf,size_t len) +{ +if (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 + && ((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ) { +return true; + } +return false; +} +size_t buffer_find_nonzero_offset (const void *buf,size_t len); +#endif util/cutils.c +23
-0@@ -143,6 +143,51 @@ int qemu_fdatasync(int fd) }/* +* Searches for an area with non-zero content in a buffer +* +* Attention! The len must be a multiple of +* BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE) +* and addr must be a multiple of sizeof(VECTYPE) due to +* restriction of optimizations in this function. +* +* can_use_buffer_find_nonzero_offset() can be used to check +* these requirements. +* +* The return value is the offset of the non-zero area rounded +* down to BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE). +* If the buffer is all zero the return value is equal to len. +*/ + +size_t buffer_find_nonzero_offset (const void *buf,size_t len) +{ +VECTYPE *p = (VECTYPE *)buf; +VECTYPE zero =ZERO_SPLAT ; +size_t i; + +assert (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 );Quoted 8 lines
util/cutils.c int qemu_fdatasync(int fd) · line 175
Quoted 7 lines
util/cutils.c +7
-0+assert (((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ); + +if (*((const long *) buf)) { +return 0 ; + } + + for (i = 0; i < len / sizeof(VECTYPE);Why not put len/sizeof(VECTYPE) in a variable?
Quoted 4 lines
are you afraid that there is a division at each iteration?
sizeof(VECTYPE) is a power of 2 so i think the compiler will optimize it to a >> at compile time.
true, but it still is done every iteration.
Quoted 2 lines
I would also be ok with writing len /= sizeof(VECTYPE) before the loop.
I would prefer it :)
Orit
Quoted 25 lines
Peter
Quoted 21 lines
Orit
Quoted 19 lines
util/cutils.c +15
-0+ i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) { +VECTYPE tmp0 = p[i +0 ] | p[i +1 ]; +VECTYPE tmp1 = p[i +2 ] | p[i +3 ]; +VECTYPE tmp2 = p[i +4 ] | p[i +5 ]; +VECTYPE tmp3 = p[i +6 ] | p[i +7 ]; +VECTYPE tmp01 = tmp0 | tmp1; +VECTYPE tmp23 = tmp2 | tmp3; +if (!ALL_EQ (tmp01 | tmp23, zero)) { +break ; + } + } +return i *sizeof (VECTYPE ); +} + +/* * Checks if a buffer is all zeroes * * Attention! The len must be a multiple of 4 * sizeof(long) due to
Re: [Qemu-devel] [PATCHv4 2/9] cutils: add a function to find non-zero content in a buffer
Quoted 18 lines
Quoted 18 lines
Quoted 17 lines
Quoted 6 lines
util/cutils.c +5
-0+size_t buffer_find_nonzero_offset (const void *buf,size_t len) +{ +VECTYPE *p = (VECTYPE *)buf; +VECTYPE zero =ZERO_SPLAT ; +size_t i;util/cutils.c int qemu_fdatasync(int fd) · line 175
Quoted 10 lines
util/cutils.c +10
-0+ +assert (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 ); +assert (((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ); + +if (*((const long *) buf)) { +return 0 ; + } + + for (i = 0; i < len / sizeof(VECTYPE);Why not put len/sizeof(VECTYPE) in a variable?
Quoted 6 lines
Quoted 5 lines
are you afraid that there is a division at each iteration?
sizeof(VECTYPE) is a power of 2 so i think the compiler will optimize it
to a >> at compile time.true, but it still is done every iteration.
len is an invariant, the compiler will move it out of the loop automatically. Write readable code unless you have good clues that it is also slow.
Paolo
Re: [Qemu-devel] [PATCHv4 2/9] cutils: add a function to find non-zero content in a buffer
Quoted 20 lines · Paolo Bonzini
Quoted 20 lines
Quoted 20 lines
Quoted 17 lines
Quoted 6 lines
util/cutils.c +5
-0+size_t buffer_find_nonzero_offset (const void *buf,size_t len) +{ +VECTYPE *p = (VECTYPE *)buf; +VECTYPE zero =ZERO_SPLAT ; +size_t i;util/cutils.c int qemu_fdatasync(int fd) · line 175
Quoted 10 lines
util/cutils.c +10
-0+ +assert (len % (BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR + *sizeof (VECTYPE )) ==0 ); +assert (((uintptr_t ) buf) %sizeof (VECTYPE ) ==0 ); + +if (*((const long *) buf)) { +return 0 ; + } + + for (i = 0; i < len / sizeof(VECTYPE);Why not put len/sizeof(VECTYPE) in a variable?
are you afraid that there is a division at each iteration?
Quoted 9 lines
Quoted 4 lines
Quoted 3 lines
sizeof(VECTYPE) is a power of 2 so i think the compiler will optimize it
to a >> at compile time.true, but it still is done every iteration.
len is an invariant, the compiler will move it out of the loop automatically. Write readable code unless you have good clues that it is also slow.
I know it does for x86 but I wasn't sure for other platforms. I'm fine with as is.
Orit
Quoted 2 lines
Paolo
PATCH v4 3/9 buffer_is_zero: use vector optimizations if possible
In reply to Peter Lievenperformance gain on SSE2 is approx. 20-25%. altivec is not tested. performance for unsigned long arithmetic is unchanged.
--- util/cutils.c | 5 +++++ 1 file changed, 5 insertions(+)
util/cutils.c +5 -0
@@ -205,6 +205,11 @@ bool buffer_is_zero(const void *buf, size_t len)long d0, d1, d2, d3;const long *const data = buf; +/* use vector optimized zero check if possible */ +if (can_use_buffer_find_nonzero_offset (buf, len)) { +return buffer_find_nonzero_offset (buf, len) == len; + } +assert (len % (4 *sizeof (long )) ==0 ); len /=sizeof (long );
Signature · 1 line
1.7.9.5
Re: [Qemu-devel] [PATCHv4 3/9] buffer_is_zero: use vector optimizations if possible
Quoted 17 lines · Peter Lieven
performance gain on SSE2 is approx. 20-25%. altivec is not tested. performance for unsigned long arithmetic is unchanged.
Signed-off-by Peter Lieven <[email protected]>Reviewed-by Eric Blake <[email protected]>--- util/cutils.c | 5 +++++ 1 file changed, 5 insertions(+)util/cutils.c +0
-0@@ -205,6 +205,11 @@ bool buffer_is_zero(const void *buf, size_t len)long d0, d1, d2, d3;
util/cutils.c bool buffer_is_zero(const void *buf, size_t len) · line 215
Quoted 10 lines
util/cutils.c +5
-0const long *const data = buf; +/* use vector optimized zero check if possible */ +if (can_use_buffer_find_nonzero_offset (buf, len)) { +return buffer_find_nonzero_offset (buf, len) == len; + } +assert (len % (4 *sizeof (long )) ==0 ); len /=sizeof (long );
PATCH v4 4/9 bitops: use vector algorithm to optimize find_next_bit()
In reply to Peter Lieventhis patch adds the usage of buffer_find_nonzero_offset() to skip large areas of zeroes.
compared to loop unrolling presented in an earlier patch this adds another 50% performance benefit for skipping large areas of zeroes. loop unrolling alone added close to 100% speedup.
--- util/bitops.c | 24 +++++++++++++++++++++--- 1 file changed, 21 insertions(+), 3 deletions(-)
util/bitops.c +21 -3
@@ -42,10 +42,28 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size, size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; } -while (size & ~(BITS_PER_LONG -1 )) { -if ((tmp = *(p++))) { - goto found_middle; +while (size >=BITS_PER_LONG ) { + tmp = *p; +if (tmp) { + goto found_middle; + } +if (can_use_buffer_find_nonzero_offset (p, size /BITS_PER_BYTE )) { +size_t tmp2 = +buffer_find_nonzero_offset (p, size /BITS_PER_BYTE ); + result += tmp2 *BITS_PER_BYTE ; + size -= tmp2 *BITS_PER_BYTE ; + p += tmp2 /sizeof (unsigned long ); +if (!size) { +return result; + } +if (tmp2) { + tmp = *p; +if (tmp) { + goto found_middle; + } + } } + p++; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; }
Signature · 1 line
1.7.9.5
Re: [Qemu-devel] [PATCHv4 4/9] bitops: use vector algorithm to optimize find_next_bit()
Quoted 41 lines · Peter Lieven
this patch adds the usage of
buffer_find_nonzero_offset()to skip large areas of zeroes.compared to loop unrolling presented in an earlier patch this adds another 50% performance benefit for skipping large areas of zeroes. loop unrolling alone added close to 100% speedup.
Signed-off-by Peter Lieven <[email protected]>Reviewed-by Eric Blake <[email protected]>--- util/bitops.c | 24 +++++++++++++++++++++--- 1 file changed, 21 insertions(+), 3 deletions(-)util/bitops.c +15
-3@@ -42,10 +42,28 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size, size -=BITS_PER_LONG ; result +=BITS_PER_LONG ; } -while (size & ~(BITS_PER_LONG -1 )) { -if ((tmp = *(p++))) { - goto found_middle; +while (size >=BITS_PER_LONG ) { + tmp = *p; +if (tmp) { + goto found_middle; + } +if (can_use_buffer_find_nonzero_offset (p, size /BITS_PER_BYTE )) { +size_t tmp2 = +buffer_find_nonzero_offset (p, size /BITS_PER_BYTE ); + result += tmp2 *BITS_PER_BYTE ; + size -= tmp2 *BITS_PER_BYTE ; + p += tmp2 /sizeof (unsigned long ); +if (!size) { +return result; + } +if (tmp2) {
util/bitops.c unsigned long find_next_bit(const unsigned long *addr, unsigned long size, · line 69
Quoted 10 lines
util/bitops.c +6
-0+ tmp = *p; +if (tmp) { + goto found_middle; + } + } } + p++; result +=BITS_PER_LONG ; size -=BITS_PER_LONG ; }
PATCH v4 5/9 migration: search for zero instead of dup pages
In reply to Peter Lievenvirtually all dup pages are zero pages. remove the special is_dup_page() function and use the optimized buffer_find_nonzero_offset() function instead.
here buffer_find_nonzero_offset() is used directly to avoid the unnecssary additional checks in buffer_is_zero().
raw performace gain checking zeroed memory over is_dup_page() is approx. 15-20% with SSE2.
--- arch_init.c | 21 ++++++--------------- 1 file changed, 6 insertions(+), 15 deletions(-)
arch_init.c +6 -15
@@ -144,19 +144,10 @@ int qemu_read_default_config_files(bool userconfig)return 0 ; } -static int is_dup_page (uint8_t *page) +static inline bool is_zero_page (uint8_t *p) { -VECTYPE *p = (VECTYPE *)page; -VECTYPE val =SPLAT (page); -int i; - -for (i =0 ; i <TARGET_PAGE_SIZE /sizeof (VECTYPE ); i++) { -if (!ALL_EQ (val, p[i])) { -return 0 ; - } - } - -return 1 ; +return buffer_find_nonzero_offset (p,TARGET_PAGE_SIZE ) == +TARGET_PAGE_SIZE ; }/* struct contains XBZRLE cache and a static page
@@ -443,12 +434,12 @@ static int ram_save_block(QEMUFile *f, bool last_stage)/* In doubt sent page as normal */ bytes_sent =-1 ; -if (is_dup_page (p)) { +if (is_zero_page (p)) { acct_info.dup_pages++; bytes_sent =save_block_hdr (f, block, offset, cont,RAM_SAVE_FLAG_COMPRESS ); -qemu_put_byte (f, *p); - bytes_sent +=1 ; +qemu_put_byte (f,0 ); + bytes_sent++; }else if (migrate_use_xbzrle ()) { current_addr = block->offset + offset; bytes_sent = save_xbzrle_page(f, p, current_addr, block,
Signature · 1 line
1.7.9.5
Re: [Qemu-devel] [PATCHv4 5/9] migration: search for zero instead of dup pages
Quoted 9 lines · Peter Lieven
virtually all dup pages are zero pages. remove the special
is_dup_page()function and use the optimizedbuffer_find_nonzero_offset()function instead.here
buffer_find_nonzero_offset()is used directly to avoid the unnecssary additional checks inbuffer_is_zero().
Quoted 7 lines
raw performace gain checking zeroed memory over
is_dup_page()is approx. 15-20% with SSE2.Signed-off-by Peter Lieven <[email protected]>--- arch_init.c | 21 ++++++--------------- 1 file changed, 6 insertions(+), 15 deletions(-)
The code is sound, but I agree with Paolo's assessment that seeing a bit more benchmarking, such as on non-SSE2 seupts, wouldn't hurt.
Signature · 2 lines
Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
Re: [Qemu-devel] [PATCHv4 5/9] migration: search for zero instead of dup pages
Am 22.03.2013 20:49, schrieb Eric Blake:
Quoted 13 lines · Peter Lieven
Quoted 12 lines
virtually all dup pages are zero pages. remove the special
is_dup_page()function and use the optimizedbuffer_find_nonzero_offset()function instead.here
buffer_find_nonzero_offset()is used directly to avoid the unnecssary additional checks inbuffer_is_zero().raw performace gain checking zeroed memory over
is_dup_page()is approx. 15-20% with SSE2.
Quoted 9 lines
Quoted 4 lines
Signed-off-by Peter Lieven <[email protected]>--- arch_init.c | 21 ++++++--------------- 1 file changed, 6 insertions(+), 15 deletions(-)Reviewed-by Eric Blake <[email protected]>The code is sound, but I agree with Paolo's assessment that seeing a bit more benchmarking, such as on non-SSE2 seupts, wouldn't hurt.
The performance for checking zeroed memory is equal to the standard unrolled version of buffer_is_zero(). So this is a big gain over normal is_dup_page() which checks only one long per iteration. I can provide some numbers Monday.
However, if you have a good idea for a test case, please let me know. My first idea was how many pages are out there, that are non-zero, but zero in the first sizeof(long) bytes so that reading 128 Byte (on SSE2) seems to be a real disadvantage.
But with all your and especially Paolos concerns, please keep in mind, even if the setup costs are high, if we abort on the first 128Byte we will need all of them anyway, as we copy all this data either raw or through XBZRLE. So does it hurt if they are in the cache? Or am I wrong here?
Peter
Re: [Qemu-devel] [PATCHv4 5/9] migration: search for zero instead of dup pages
In reply to Peter LievenQuoted 51 lines · Peter Lieven
virtually all dup pages are zero pages. remove the special
is_dup_page()function and use the optimizedbuffer_find_nonzero_offset()function instead.here
buffer_find_nonzero_offset()is used directly to avoid the unnecssary additional checks inbuffer_is_zero().raw performace gain checking zeroed memory over
is_dup_page()is approx. 15-20% with SSE2.Signed-off-by Peter Lieven <[email protected]>--- arch_init.c | 21 ++++++--------------- 1 file changed, 6 insertions(+), 15 deletions(-)arch_init.c +4
-13@@ -144,19 +144,10 @@ int qemu_read_default_config_files(bool userconfig)return 0 ; } -static int is_dup_page (uint8_t *page) +static inline bool is_zero_page (uint8_t *p) { -VECTYPE *p = (VECTYPE *)page; -VECTYPE val =SPLAT (page); -int i; - -for (i =0 ; i <TARGET_PAGE_SIZE /sizeof (VECTYPE ); i++) { -if (!ALL_EQ (val, p[i])) { -return 0 ; - } - } - -return 1 ; +return buffer_find_nonzero_offset (p,TARGET_PAGE_SIZE ) == +TARGET_PAGE_SIZE ; }/* struct contains XBZRLE cache and a static page @@ -443,12 +434,12 @@ static int ram_save_block(QEMUFile *f, bool last_stage)/* In doubt sent page as normal */ bytes_sent =-1 ; -if (is_dup_page (p)) { +if (is_zero_page (p)) {
arch_init.c static int ram_save_block(QEMUFile *f, bool last_stage) · line 445
Quoted 10 lines
arch_init.c +2
-2acct_info.dup_pages++; bytes_sent =save_block_hdr (f, block, offset, cont,RAM_SAVE_FLAG_COMPRESS ); -qemu_put_byte (f, *p); - bytes_sent +=1 ; +qemu_put_byte (f,0 ); + bytes_sent++; }else if (migrate_use_xbzrle ()) { current_addr = block->offset + offset; bytes_sent = save_xbzrle_page(f, p, current_addr, block,
PATCH v4 6/9 migration: add an indicator for bulk state of ram migration
In reply to Peter Lieventhe first round of ram transfer is special since all pages are dirty and thus all memory pages are transferred to the target. this patch adds a boolean variable to track this stage.
--- arch_init.c | 3 +++ 1 file changed, 3 insertions(+)
arch_init.c +3 -0
@@ -317,6 +317,7 @@ static ram_addr_t last_offset;static unsigned long *migration_bitmap;static uint64_t migration_dirty_pages;static uint32_t last_version; +static bool ram_bulk_stage; static inline ram_addr_t migration_bitmap_find_and_reset_dirty(MemoryRegion *mr,
@@ -424,6 +425,7 @@ static int ram_save_block(QEMUFile *f, bool last_stage)if (!block) { block =QTAILQ_FIRST (&ram_list.blocks); complete_round = true; + ram_bulk_stage = false; } }else {uint8_t *p;
@@ -527,6 +529,7 @@ static void reset_ram_globals(void) last_sent_block =NULL ; last_offset =0 ; last_version = ram_list.version; + ram_bulk_stage = true; }#define MAX_WAIT 50/* ms, half buffered_file limit */
Signature · 1 line
1.7.9.5
Re: [Qemu-devel] [PATCHv4 6/9] migration: add an indicator for bulk state of ram migration
Quoted 33 lines · Peter Lieven
the first round of ram transfer is special since all pages are dirty and thus all memory pages are transferred to the target. this patch adds a boolean variable to track this stage.
Signed-off-by Peter Lieven <[email protected]>Reviewed-by Eric Blake <[email protected]>--- arch_init.c | 3 +++ 1 file changed, 3 insertions(+)arch_init.c +2
-0@@ -317,6 +317,7 @@ static ram_addr_t last_offset;static unsigned long *migration_bitmap;static uint64_t migration_dirty_pages;static uint32_t last_version; +static bool ram_bulk_stage; static inline ram_addr_t migration_bitmap_find_and_reset_dirty(MemoryRegion *mr,@@ -424,6 +425,7 @@ static int ram_save_block(QEMUFile *f, bool last_stage)if (!block) { block =QTAILQ_FIRST (&ram_list.blocks); complete_round = true; + ram_bulk_stage = false; } }else {uint8_t *p;
arch_init.c static void reset_ram_globals(void) · line 535
Quoted 7 lines
arch_init.c +1
-0@@ -527,6 +529,7 @@ static void reset_ram_globals(void) last_sent_block =NULL ; last_offset =0 ; last_version = ram_list.version; + ram_bulk_stage = true; }#define MAX_WAIT 50/* ms, half buffered_file limit */
PATCH v4 7/9 migration: do not sent zero pages in bulk stage
In reply to Peter Lievenduring bulk stage of ram migration if a page is a zero page do not send it at all.
the memory at the destination reads as zero anyway.
even if there is an madvise with QEMU_MADV_DONTNEED at the target upon receipt of a zero page I have observed that the target starts swapping if the memory is overcommitted. it seems that the pages are dropped asynchronously.
--- arch_init.c | 24 ++++++++++++++++++++---- hmp.c | 2 ++ include/migration/migration.h | 2 ++ migration.c | 3 ++- qapi-schema.json | 6 ++++-- qmp-commands.hx | 3 ++- 6 files changed, 32 insertions(+), 8 deletions(-)
arch_init.c +20 -4
@@ -181,6 +181,7 @@ int64_t xbzrle_cache_resize(int64_t new_size)/* accounting for migration statistics */ typedef struct AccountingInfo { uint64_t dup_pages; + uint64_t skipped_pages; uint64_t norm_pages; uint64_t iterations; uint64_t xbzrle_bytes;
@@ -206,6 +207,16 @@ uint64_t dup_mig_pages_transferred(void)return acct_info.dup_pages; } +uint64_t skipped_mig_bytes_transferred (void ) +{ +return acct_info.skipped_pages *TARGET_PAGE_SIZE ; +} + +uint64_t skipped_mig_pages_transferred (void ) +{ +return acct_info.skipped_pages; +} +uint64_t norm_mig_bytes_transferred (void ) {return acct_info.norm_pages *TARGET_PAGE_SIZE ;
@@ -438,10 +449,15 @@ static int ram_save_block(QEMUFile *f, bool last_stage) bytes_sent =-1 ;if (is_zero_page (p)) { acct_info.dup_pages++; - bytes_sent =save_block_hdr (f, block, offset, cont, -RAM_SAVE_FLAG_COMPRESS ); -qemu_put_byte (f,0 ); - bytes_sent++; +if (!ram_bulk_stage) { + bytes_sent =save_block_hdr (f, block, offset, cont, +RAM_SAVE_FLAG_COMPRESS ); +qemu_put_byte (f,0 ); + bytes_sent++; + }else { + acct_info.skipped_pages++; + bytes_sent =0 ; + } }else if (migrate_use_xbzrle ()) { current_addr = block->offset + offset; bytes_sent = save_xbzrle_page(f, p, current_addr, block,
hmp.c +2 -0
@@ -173,6 +173,8 @@ void hmp_info_migrate(Monitor *mon, const QDict *qdict) info->ram->total >> 10);monitor_printf (mon,"duplicate: %" PRIu64" pages\n" , info->ram->duplicate); +monitor_printf (mon,"skipped: %" PRIu64" pages\n" , + info->ram->skipped);monitor_printf (mon,"normal: %" PRIu64" pages\n" , info->ram->normal); monitor_printf(mon, "normal bytes: %" PRIu64 " kbytes\n",
include/migration/migration.h +2 -0
@@ -96,6 +96,8 @@ extern SaveVMHandlers savevm_ram_handlers;uint64_t dup_mig_bytes_transferred (void );uint64_t dup_mig_pages_transferred (void ); +uint64_t skipped_mig_bytes_transferred (void ); +uint64_t skipped_mig_pages_transferred (void );uint64_t norm_mig_bytes_transferred (void );uint64_t norm_mig_pages_transferred (void );uint64_t xbzrle_mig_bytes_transferred (void );
migration.c +2 -1
@@ -197,11 +197,11 @@ MigrationInfo *qmp_query_migrate(Error **errp) info->ram->remaining =ram_bytes_remaining (); info->ram->total =ram_bytes_total (); info->ram->duplicate =dup_mig_pages_transferred (); + info->ram->skipped =skipped_mig_pages_transferred (); info->ram->normal =norm_mig_pages_transferred (); info->ram->normal_bytes =norm_mig_bytes_transferred (); info->ram->dirty_pages_rate = s->dirty_pages_rate; -if (blk_mig_active ()) { info->has_disk = true; info->disk =g_malloc0 (sizeof (*info->disk));
@@ -227,6 +227,7 @@ MigrationInfo *qmp_query_migrate(Error **errp) info->ram->remaining =0 ; info->ram->total =ram_bytes_total (); info->ram->duplicate =dup_mig_pages_transferred (); + info->ram->skipped =skipped_mig_pages_transferred (); info->ram->normal =norm_mig_pages_transferred (); info->ram->normal_bytes =norm_mig_bytes_transferred ();break ;
qapi-schema.json +4 -2
@@ -496,7 +496,9 @@ # # @total: total amount of bytes involved in the migration process # -# @duplicate: number of duplicate pages (since 1.2) +# @duplicate: number of duplicate (zero) pages (since 1.2) +# +# @skipped: number of skipped zero pages (since 1.5) # # @normal : number of normal pages (since 1.2) #
@@ -510,7 +512,7 @@ { 'type': 'MigrationStats', 'data': {'transferred': 'int', 'remaining': 'int', 'total': 'int' , 'duplicate': 'int', 'normal': 'int', 'normal-bytes': 'int', - 'dirty-pages-rate' : 'int' } } + 'dirty-pages-rate' : 'int', 'skipped': 'int' } } ## # @XBZRLECacheStats
qmp-commands.hx +2 -1
@@ -2442,7 +2442,8 @@ The main json-object contains the following: - "transferred": amount transferred (json-int) - "remaining": amount remaining (json-int) - "total": total (json-int) - - "duplicate": number of duplicated pages (json-int) + - "duplicate": number of duplicated (zero) pages (json-int) + - "skipped": number of skipped zero pages (json-int) - "normal" : number of normal pages transferred (json-int) - "normal-bytes" : number of normal bytes transferred (json-int) - "disk": only present if "status" is "active" and it is a block migration,
Signature · 1 line
1.7.9.5
Re: [Qemu-devel] [PATCHv4 7/9] migration: do not sent zero pages in bulk stage
Quoted 8 lines · Peter Lieven
during bulk stage of ram migration if a page is a zero page do not send it at all.
the memory at the destination reads as zero anyway.even if there is an madvise with
QEMU_MADV_DONTNEEDat the target upon receipt of a zero page I have observed that the target starts swapping if the memory is overcommitted. it seems that the pages are dropped asynchronously.
Your commit message fails to mention that you are updating QMP to record a new stat, although I agree with what you've done. If you do respin, make mention of this fact in the commit message.
Quoted 25 lines
Signed-off-by Peter Lieven <[email protected]>--- arch_init.c | 24 ++++++++++++++++++++---- hmp.c | 2 ++ include/migration/migration.h | 2 ++ migration.c | 3 ++- qapi-schema.json | 6 ++++-- qmp-commands.hx | 3 ++- 6 files changed, 32 insertions(+), 8 deletions(-)+++
b/qapi-schema.jsonqapi-schema.json +3
-1@@ -496,7 +496,9 @@ # # @total: total amount of bytes involved in the migration process # -# @duplicate: number of duplicate pages (since 1.2) +# @duplicate: number of duplicate (zero) pages (since 1.2) +# +# @skipped: number of skipped zero pages (since 1.5) # # @normal : number of normal pages (since 1.2) #
qapi-schema.json line 515
Quoted 5 lines
qapi-schema.json +1
-1@@ -510,7 +512,7 @@ { 'type': 'MigrationStats', 'data': {'transferred': 'int', 'remaining': 'int', 'total': 'int' , 'duplicate': 'int', 'normal': 'int', 'normal-bytes': 'int', - 'dirty-pages-rate' : 'int' } } + 'dirty-pages-rate' : 'int', 'skipped': 'int' } }
Your layout here doesn't match the order that you documented things in.
But it is a dictionary of name-value pairs, so order is not significant
to the interface. About the only thing the order might affect is whether the rest of your code, which assigns fields in documentation order, is slightly less efficient because it is jumping around the C struct rather than hitting it in linear order, but that would be in the noise on a benchmark. So I won't insist on a respin. However, since you are touching QMP, it wouldn't hurt to have Luiz chime in.
I'm okay if this goes in as-is. Or, if you do spin a v5 for other reasons, then lay out MigrationStats in documentation order, and improve the commit message. If those are the only changes you make, then you can keep:
Signature · 2 lines
Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
Re: [Qemu-devel] [PATCHv4 7/9] migration: do not sent zero pages in bulk stage
In reply to Peter LievenQuoted 149 lines · Peter Lieven
during bulk stage of ram migration if a page is a zero page do not send it at all.
the memory at the destination reads as zero anyway.even if there is an madvise with
QEMU_MADV_DONTNEEDat the target upon receipt of a zero page I have observed that the target starts swapping if the memory is overcommitted. it seems that the pages are dropped asynchronously.Signed-off-by Peter Lieven <[email protected]>--- arch_init.c | 24 ++++++++++++++++++++---- hmp.c | 2 ++ include/migration/migration.h | 2 ++ migration.c | 3 ++- qapi-schema.json | 6 ++++-- qmp-commands.hx | 3 ++- 6 files changed, 32 insertions(+), 8 deletions(-)arch_init.c +20
-4@@ -181,6 +181,7 @@ int64_t xbzrle_cache_resize(int64_t new_size)/* accounting for migration statistics */ typedef struct AccountingInfo { uint64_t dup_pages; + uint64_t skipped_pages; uint64_t norm_pages; uint64_t iterations; uint64_t xbzrle_bytes;@@ -206,6 +207,16 @@ uint64_t dup_mig_pages_transferred(void)return acct_info.dup_pages; } +uint64_t skipped_mig_bytes_transferred (void ) +{ +return acct_info.skipped_pages *TARGET_PAGE_SIZE ; +} + +uint64_t skipped_mig_pages_transferred (void ) +{ +return acct_info.skipped_pages; +} +uint64_t norm_mig_bytes_transferred (void ) {return acct_info.norm_pages *TARGET_PAGE_SIZE ;@@ -438,10 +449,15 @@ static int ram_save_block(QEMUFile *f, bool last_stage) bytes_sent =-1 ;if (is_zero_page (p)) { acct_info.dup_pages++; - bytes_sent =save_block_hdr (f, block, offset, cont, -RAM_SAVE_FLAG_COMPRESS ); -qemu_put_byte (f,0 ); - bytes_sent++; +if (!ram_bulk_stage) { + bytes_sent =save_block_hdr (f, block, offset, cont, +RAM_SAVE_FLAG_COMPRESS ); +qemu_put_byte (f,0 ); + bytes_sent++; + }else { + acct_info.skipped_pages++; + bytes_sent =0 ; + } }else if (migrate_use_xbzrle ()) { current_addr = block->offset + offset; bytes_sent = save_xbzrle_page(f, p, current_addr, block,hmp.c +2
-0@@ -173,6 +173,8 @@ void hmp_info_migrate(Monitor *mon, const QDict *qdict) info->ram->total >> 10);monitor_printf (mon,"duplicate: %" PRIu64" pages\n" , info->ram->duplicate); +monitor_printf (mon,"skipped: %" PRIu64" pages\n" , + info->ram->skipped);monitor_printf (mon,"normal: %" PRIu64" pages\n" , info->ram->normal); monitor_printf(mon, "normal bytes: %" PRIu64 " kbytes\n",include/migration/migration.h +2
-0@@ -96,6 +96,8 @@ extern SaveVMHandlers savevm_ram_handlers;uint64_t dup_mig_bytes_transferred (void );uint64_t dup_mig_pages_transferred (void ); +uint64_t skipped_mig_bytes_transferred (void ); +uint64_t skipped_mig_pages_transferred (void );uint64_t norm_mig_bytes_transferred (void );uint64_t norm_mig_pages_transferred (void );uint64_t xbzrle_mig_bytes_transferred (void );migration.c +2
-1@@ -197,11 +197,11 @@ MigrationInfo *qmp_query_migrate(Error **errp) info->ram->remaining =ram_bytes_remaining (); info->ram->total =ram_bytes_total (); info->ram->duplicate =dup_mig_pages_transferred (); + info->ram->skipped =skipped_mig_pages_transferred (); info->ram->normal =norm_mig_pages_transferred (); info->ram->normal_bytes =norm_mig_bytes_transferred (); info->ram->dirty_pages_rate = s->dirty_pages_rate; -if (blk_mig_active ()) { info->has_disk = true; info->disk =g_malloc0 (sizeof (*info->disk));@@ -227,6 +227,7 @@ MigrationInfo *qmp_query_migrate(Error **errp) info->ram->remaining =0 ; info->ram->total =ram_bytes_total (); info->ram->duplicate =dup_mig_pages_transferred (); + info->ram->skipped =skipped_mig_pages_transferred (); info->ram->normal =norm_mig_pages_transferred (); info->ram->normal_bytes =norm_mig_bytes_transferred ();break ;qapi-schema.json +4
-2@@ -496,7 +496,9 @@ # # @total: total amount of bytes involved in the migration process # -# @duplicate: number of duplicate pages (since 1.2) +# @duplicate: number of duplicate (zero) pages (since 1.2) +# +# @skipped: number of skipped zero pages (since 1.5) # # @normal : number of normal pages (since 1.2) #@@ -510,7 +512,7 @@ { 'type': 'MigrationStats', 'data': {'transferred': 'int', 'remaining': 'int', 'total': 'int' , 'duplicate': 'int', 'normal': 'int', 'normal-bytes': 'int', - 'dirty-pages-rate' : 'int' } } + 'dirty-pages-rate' : 'int', 'skipped': 'int' } } ## # @XBZRLECacheStatsqmp-commands.hx +0
-0
qmp-commands.hx The main json-object contains the following: · line 2449
Quoted 9 lines
qmp-commands.hx +2
-1@@ -2442,7 +2442,8 @@ The main json-object contains the following: - "transferred": amount transferred (json-int) - "remaining": amount remaining (json-int) - "total": total (json-int) - - "duplicate": number of duplicated pages (json-int) + - "duplicate": number of duplicated (zero) pages (json-int) + - "skipped": number of skipped zero pages (json-int) - "normal" : number of normal pages transferred (json-int) - "normal-bytes" : number of normal bytes transferred (json-int) - "disk": only present if "status" is "active" and it is a block migration,
PATCH v4 8/9 migration: do not search dirty pages in bulk stage
In reply to Peter Lievenavoid searching for dirty pages just increment the page offset. all pages are dirty anyway.
--- arch_init.c | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-)
arch_init.c +7 -1
@@ -338,7 +338,13 @@ ram_addr_t migration_bitmap_find_and_reset_dirty(MemoryRegion *mr,unsigned long nr = base + (start >>TARGET_PAGE_BITS );unsigned long size = base + (int128_get64 (mr->size) >>TARGET_PAGE_BITS ); -unsigned long next =find_next_bit (migration_bitmap, size, nr); +unsigned long next; + +if (ram_bulk_stage && nr > base) { + next = nr +1 ; + }else { + next =find_next_bit (migration_bitmap, size, nr); + }if (next < size) {clear_bit (next, migration_bitmap);
Signature · 1 line
1.7.9.5
Re: [Qemu-devel] [PATCHv4 8/9] migration: do not search dirty pages in bulk stage
Quoted 19 lines · Peter Lieven
avoid searching for dirty pages just increment the page offset. all pages are dirty anyway.
Signed-off-by Peter Lieven <[email protected]>Reviewed-by Eric Blake <[email protected]>--- arch_init.c | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-)arch_init.c +0
-1@@ -338,7 +338,13 @@ ram_addr_t migration_bitmap_find_and_reset_dirty(MemoryRegion *mr,unsigned long nr = base + (start >>TARGET_PAGE_BITS );unsigned long size = base + (int128_get64 (mr->size) >>TARGET_PAGE_BITS ); -unsigned long next =find_next_bit (migration_bitmap, size, nr);
arch_init.c ram_addr_t migration_bitmap_find_and_reset_dirty(MemoryRegion *mr, · line 350
Quoted 10 lines
arch_init.c +7
-0+unsigned long next; + +if (ram_bulk_stage && nr > base) { + next = nr +1 ; + }else { + next =find_next_bit (migration_bitmap, size, nr); + }if (next < size) {clear_bit (next, migration_bitmap);
PATCH v4 9/9 migration: use XBZRLE only after bulk stage
In reply to Peter Lievenat the beginning of migration all pages are marked dirty and in the first round a bulk migration of all pages is performed.
currently all these pages are copied to the page cache regardless of whether they are frequently updated or not. this doesn't make sense since most of these pages are never transferred again.
this patch changes the XBZRLE transfer to only be used after the bulk stage has been completed. that means a page is added to the page cache the second time it is transferred and XBZRLE can benefit from the third time of transfer.
since the page cache is likely smaller than the number of pages it's also likely that in the second round the page is missing in the cache due to collisions in the bulk phase.
on the other hand a lot of unnecessary mallocs, memdups and frees are saved.
the following results have been taken earlier while executing the test program from docs/xbzrle.txt. (+) with the patch and (-) without. (thanks to Eric Blake for reformatting and comments)
+ total time: 22185 milliseconds
- total time: 22410 milliseconds
Shaved 0.3 seconds, better than 1%!
+ downtime: 29 milliseconds
- downtime: 21 milliseconds
Not sure why downtime seemed worse, but probably not the end of the world.
+ transferred ram: 706034 kbytes
- transferred ram: 721318 kbytes
Fewer bytes sent - good.
+ remaining ram: 0 kbytes
- remaining ram: 0 kbytes
+ total ram: 1057216 kbytes
- total ram: 1057216 kbytes
+ duplicate: 108556 pages
- duplicate: 105553 pages
+ normal: 175146 pages
- normal: 179589 pages
+ normal bytes: 700584 kbytes
- normal bytes: 718356 kbytes
Fewer normal bytes...
+ cache size: 67108864 bytes
- cache size: 67108864 bytes
+ xbzrle transferred: 3127 kbytes
- xbzrle transferred: 630 kbytes
...and more compressed pages sent - good.
+ xbzrle pages: 117811 pages
- xbzrle pages: 21527 pages
+ xbzrle cache miss: 18750
- xbzrle cache miss: 179589
And very good improvement on the cache miss rate.
+ xbzrle overflow : 0
- xbzrle overflow : 0
--- arch_init.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
arch_init.c +1 -1
@@ -464,7 +464,7 @@ static int ram_save_block(QEMUFile *f, bool last_stage) acct_info.skipped_pages++; bytes_sent =0 ; } - }else if (migrate_use_xbzrle ()) { + }else if (!ram_bulk_stage &&migrate_use_xbzrle ()) { current_addr = block->offset + offset; bytes_sent =save_xbzrle_page (f, p, current_addr, block, offset, cont, last_stage);
Signature · 1 line
1.7.9.5
Re: [Qemu-devel] [PATCHv4 9/9] migration: use XBZRLE only after bulk stage
Quoted 80 lines · Peter Lieven
at the beginning of migration all pages are marked dirty and in the first round a bulk migration of all pages is performed.
currently all these pages are copied to the page cache regardless of whether they are frequently updated or not. this doesn't make sense since most of these pages are never transferred again.
this patch changes the XBZRLE transfer to only be used after the bulk stage has been completed. that means a page is added to the page cache the second time it is transferred and XBZRLE can benefit from the third time of transfer.
since the page cache is likely smaller than the number of pages it's also likely that in the second round the page is missing in the cache due to collisions in the bulk phase.
on the other hand a lot of unnecessary mallocs, memdups and frees are saved.
the following results have been taken earlier while executing the test program from
docs/xbzrle.txt. (+) with the patch and (-) without. (thanks to Eric Blake for reformatting and comments)+ total time: 22185 milliseconds
- total time: 22410 millisecondsShaved 0.3 seconds, better than 1%!
+ downtime: 29 milliseconds
- downtime: 21 millisecondsNot sure why downtime seemed worse, but probably not the end of the world.
+ transferred ram: 706034 kbytes
- transferred ram: 721318 kbytesFewer bytes sent - good.
+ remaining ram: 0 kbytes
- remaining ram: 0 kbytes
+ total ram: 1057216 kbytes
- total ram: 1057216 kbytes
+ duplicate: 108556 pages
- duplicate: 105553 pages
+ normal: 175146 pages
- normal: 179589 pages
+ normal bytes: 700584 kbytes
- normal bytes: 718356 kbytesFewer normal bytes...
+ cache size: 67108864 bytes
- cache size: 67108864 bytes
+ xbzrle transferred: 3127 kbytes
- xbzrle transferred: 630 kbytes...and more compressed pages sent - good.
+ xbzrle pages: 117811 pages
- xbzrle pages: 21527 pages
+ xbzrle cache miss: 18750
- xbzrle cache miss: 179589And very good improvement on the cache miss rate.
+ xbzrle overflow : 0
- xbzrle overflow : 0Signed-off-by Peter Lieven <[email protected]>Reviewed-by Eric Blake <[email protected]>--- arch_init.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)arch_init.c +0
-0
arch_init.c static int ram_save_block(QEMUFile *f, bool last_stage) · line 470
Quoted 8 lines
arch_init.c +1
-1@@ -464,7 +464,7 @@ static int ram_save_block(QEMUFile *f, bool last_stage) acct_info.skipped_pages++; bytes_sent =0 ; } - }else if (migrate_use_xbzrle ()) { + }else if (!ram_bulk_stage &&migrate_use_xbzrle ()) { current_addr = block->offset + offset; bytes_sent =save_xbzrle_page (f, p, current_addr, block, offset, cont, last_stage);
Il 22/03/2013 13:46, Peter Lieven ha scritto:
Quoted 56 lines
this is v4 of my patch series with various optimizations in zero buffer checking and migration tweaks.
thanks especially to Eric Blake for reviewing.
v4:
- do not inlinebuffer_find_nonzero_offset()
- inlinecan_usebuffer_find_nonzero_offset()correctly
- readd asserts inbuffer_find_nonzero_offset()as profiling shows they do not hurt.
- change last occurences of scalar 8 byBUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
- avoid deferencing p already in patch 5 where we know that the page (p) is zero
- explicitly setbytes_sent= 0 if we skip a zero page.bytes_sentwas 0 before, but it was not obvious.
- add accounting information for skipped zero pages
- fix errors reported by checkpatch.plv3:
- remove asserts, inline functions and add a check function ifbuffer_find_nonzero_offset()can be used.
- use above check function inbuffer_is_zero()andfind_next_bit().
- usebuffer_is_nonzero_offset()directly to find zero pages. we know that all requirements are met for memory pages.
- fix C89 violation inbuffer_is_zero().
- avoid derefencing p inram_save_block()if we already know the page is zero.
- fix initialization oflast_offsetinreset_ram_globals().
- avoid skipping pages with offset == 0 in bulk stage inmigration_bitmap_find_and_reset_dirty().
- compared to v1 check for zero pages also after bulk ram migration as there are guests (e.g. Windows) which zero out large amount of memory while running.v2:
- fix description, add trivial zero check and add asserts tobuffer_find_nonzero_offset.
- add a constant for the unroll factor ofbuffer_find_nonzero_offset
- replaceis_dup_page()bybuffer_is_zero()
- added test results to xbzrle patch
- optimize descriptionsPeter Lieven (9):
move vector definitions toqemu-common.h
cutils: add a function to find non-zero content in a buffer
buffer_is_zero: use vector optimizations if possible
bitops: use vector algorithm to optimizefind_next_bit()
migration: search for zero instead of dup pages
migration: add an indicator for bulk state of ram migration
migration: do not sent zero pages in bulk stage
migration: do not search dirty pages in bulk stage
migration: use XBZRLE only after bulk stage
Quoted 11 lines
arch_init.c | 74 +++++++++++++++++++---------------------- hmp.c | 2 ++ include/migration/migration.h | 2 ++ include/qemu-common.h | 37 +++++++++++++++++++++ migration.c | 3 +- qapi-schema.json | 6 ++-- qmp-commands.hx | 3 +- util/bitops.c | 24 +++++++++++-- util/cutils.c | 50 ++++++++++++++++++++++++++++ 9 files changed, 155 insertions(+), 46 deletions(-)
I think patch 4 is a bit overengineered. I would prefer the simple patch you had using three/four non-vectorized accesses. The setup cost of the vectorized buffer_is_zero is quite high, and 64 bits are just 256k RAM; if the host doesn't touch 256k RAM, it will incur the overhead.
I would prefer some more benchmarking for patch 5, but it looks ok.
The rest are fine, thanks!
Paolo
Am 22.03.2013 18:25, schrieb Paolo Bonzini:
Quoted 68 lines
Il 22/03/2013 13:46, Peter Lieven ha scritto:
Quoted 56 lines
this is v4 of my patch series with various optimizations in zero buffer checking and migration tweaks.
thanks especially to Eric Blake for reviewing.
v4:
- do not inlinebuffer_find_nonzero_offset()
- inlinecan_usebuffer_find_nonzero_offset()correctly
- readd asserts inbuffer_find_nonzero_offset()as profiling shows they do not hurt.
- change last occurences of scalar 8 byBUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
- avoid deferencing p already in patch 5 where we know that the page (p) is zero
- explicitly setbytes_sent= 0 if we skip a zero page.bytes_sentwas 0 before, but it was not obvious.
- add accounting information for skipped zero pages
- fix errors reported by checkpatch.plv3:
- remove asserts, inline functions and add a check function ifbuffer_find_nonzero_offset()can be used.
- use above check function inbuffer_is_zero()andfind_next_bit().
- usebuffer_is_nonzero_offset()directly to find zero pages. we know that all requirements are met for memory pages.
- fix C89 violation inbuffer_is_zero().
- avoid derefencing p inram_save_block()if we already know the page is zero.
- fix initialization oflast_offsetinreset_ram_globals().
- avoid skipping pages with offset == 0 in bulk stage inmigration_bitmap_find_and_reset_dirty().
- compared to v1 check for zero pages also after bulk ram migration as there are guests (e.g. Windows) which zero out large amount of memory while running.v2:
- fix description, add trivial zero check and add asserts tobuffer_find_nonzero_offset.
- add a constant for the unroll factor ofbuffer_find_nonzero_offset
- replaceis_dup_page()bybuffer_is_zero()
- added test results to xbzrle patch
- optimize descriptionsPeter Lieven (9):
move vector definitions toqemu-common.h
cutils: add a function to find non-zero content in a buffer
buffer_is_zero: use vector optimizations if possible
bitops: use vector algorithm to optimizefind_next_bit()
migration: search for zero instead of dup pages
migration: add an indicator for bulk state of ram migration
migration: do not sent zero pages in bulk stage
migration: do not search dirty pages in bulk stage
migration: use XBZRLE only after bulk stageQuoted 11 lines
arch_init.c | 74 +++++++++++++++++++---------------------- hmp.c | 2 ++ include/migration/migration.h | 2 ++ include/qemu-common.h | 37 +++++++++++++++++++++ migration.c | 3 +- qapi-schema.json | 6 ++-- qmp-commands.hx | 3 +- util/bitops.c | 24 +++++++++++-- util/cutils.c | 50 ++++++++++++++++++++++++++++ 9 files changed, 155 insertions(+), 46 deletions(-)
Quoted 4 lines
I think patch 4 is a bit overengineered. I would prefer the simple patch you had using three/four non-vectorized accesses. The setup cost of the vectorized
buffer_is_zerois quite high, and 64 bits are just 256k RAM; if the host doesn't touch 256k RAM, it will incur the overhead.
I think you are right. I was a little to eager to utilize buffer_find_nonzero_offset() as much as possible. The performance gain by unrolling was impressive enough.
The gain by the vector functions is not that big that it would justify a possible
slow down by the high setup costs. My testings revealed that in most cases buffer_find_nonzero_offset() returns 0 or a big offset. All the 0 return values would have increased setup costs with the vectorized version of patch 4.
Quoted 2 lines
I would prefer some more benchmarking for patch 5, but it looks ok.
What would you like to see? Statistics how many pages of a real system are not zero, but zero in the first sizeof(long) bytes?
Quoted 2 lines
The rest are fine, thanks!
Thank you for reviewing. If we are done with this patches I will continue with the block migration optimizations next week.
Peter
Il 22/03/2013 20:20, Peter Lieven ha scritto:
Quoted 12 lines
Quoted 4 lines
I think patch 4 is a bit overengineered. I would prefer the simple patch you had using three/four non-vectorized accesses. The setup cost of the vectorized
buffer_is_zerois quite high, and 64 bits are just 256k RAM; if the host doesn't touch 256k RAM, it will incur the overhead.I think you are right. I was a little to eager to utilize
buffer_find_nonzero_offset()as much as possible. The performance gain by unrolling was impressive enough.
The gain by the vector functions is not that big that it would justify a possible
slow down by the high setup costs. My testings revealed that in most casesbuffer_find_nonzero_offset()returns 0 or a big offset. All the 0 return values would have increased setup costs with the vectorized version of patch 4.Quoted 1 line
Quoted 3 lines
Quoted 1 line
I would prefer some more benchmarking for patch 5, but it looks ok.
What would you like to see? Statistics how many pages of a real system are not zero, but zero in the first sizeof(long) bytes?
Yeah, more or less. Running the system for a while, migrating, and plotting a histogram of the return values of buffer_find_nonzero_offset (hmm, perhaps using a nonvectorized version is better for this experiment).
Paolo
Am 22.03.2013 um 22:24 schrieb Paolo Bonzini <[email protected]>:
Quoted 13 lines
Il 22/03/2013 20:20, Peter Lieven ha scritto:
Quoted 12 lines
Quoted 4 lines
I think patch 4 is a bit overengineered. I would prefer the simple patch you had using three/four non-vectorized accesses. The setup cost of the vectorized
buffer_is_zerois quite high, and 64 bits are just 256k RAM; if the host doesn't touch 256k RAM, it will incur the overhead.I think you are right. I was a little to eager to utilize
buffer_find_nonzero_offset()as much as possible. The performance gain by unrolling was impressive enough.
The gain by the vector functions is not that big that it would justify a possible
slow down by the high setup costs. My testings revealed that in most casesbuffer_find_nonzero_offset()returns 0 or a big offset. All the 0 return values would have increased setup costs with the vectorized version of patch 4.Quoted 1 line
Quoted 7 lines
Quoted 3 lines
Quoted 1 line
I would prefer some more benchmarking for patch 5, but it looks ok.
What would you like to see? Statistics how many pages of a real system are not zero, but zero in the first sizeof(long) bytes?
Yeah, more or less. Running the system for a while, migrating, and plotting a histogram of the return values of
buffer_find_nonzero_offset(hmm, perhaps using a nonvectorized version is better for this experiment).
I will follow up with this on Monday. Have you seen my concern, that the whole page is read anyway if it is non-zero?
Peter
Quoted 2 lines
Paolo
Quoted 12 lines · Paolo Bonzini
Il 22/03/2013 20:20, Peter Lieven ha scritto:
Quoted 11 lines
Quoted 4 lines
I think patch 4 is a bit overengineered. I would prefer the simple patch you had using three/four non-vectorized accesses. The setup cost of the vectorized
buffer_is_zerois quite high, and 64 bits are just 256k RAM; if the host doesn't touch 256k RAM, it will incur the overhead.I think you are right. I was a little to eager to utilize
buffer_find_nonzero_offset()as much as possible. The performance gain by unrolling was impressive enough.
The gain by the vector functions is not that big that it would justify a possible
slow down by the high setup costs. My testings revealed that in most casesbuffer_find_nonzero_offset()returns 0 or a big offset. All the 0 return values would have increased setup costs with the vectorized version of patch 4.
Quoted 6 lines
Quoted 3 lines
Quoted 1 line
I would prefer some more benchmarking for patch 5, but it looks ok.
What would you like to see? Statistics how many pages of a real system are not zero, but zero in the first sizeof(long) bytes?
Yeah, more or less. Running the system for a while, migrating, and plotting a histogram of the return values of
buffer_find_nonzero_offset(hmm, perhaps using a nonvectorized version is better for this experiment).
It seems that Paolos concern regarding only checking the first 64-bit where right. What I would propose is to check the first BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR * sizeof(VECTYPE) bytes in sizeof(VECTYPE) chunks and use the unrolled version afterwards.
basically this would result in sth like this:
size_t buffer_find_nonzero_offset(const void *buf, size_t len)
{
VECTYPE *p = (VECTYPE *)buf;
VECTYPE zero = ZERO_SPLAT;
size_t i;
assert(can_use_buffer_find_nonzero_offset(buf, len));
if (!len) {
return 0;
}
for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) {
if (!ALL_EQ(p[i], zero)) {
return 0;
}
}
for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR;
i < len / sizeof(VECTYPE);
i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
VECTYPE tmp0 = p[i + 0] | p[i + 1];
VECTYPE tmp1 = p[i + 2] | p[i + 3];
VECTYPE tmp2 = p[i + 4] | p[i + 5];
VECTYPE tmp3 = p[i + 6] | p[i + 7];
VECTYPE tmp01 = tmp0 | tmp1;
VECTYPE tmp23 = tmp2 | tmp3;
if (!ALL_EQ(tmp01 | tmp23, zero)) {
break;
}
}
return i * sizeof(VECTYPE);
}this version is approx. 1-2% slower than the first one, but still 15% faster than old is_dup_page() for zero pages. BUT, if the first 8 bytes are zero and afterwards non-zero, the first version is approx. 200% slower due to the high setup costs.
Paolo, with this one maybe you would also be fine witht he vectorized version of patch 4?
Peter
---
here are the results of the tests with the return values of buffer_find_nonzero_offset (64-bit chunks):
ubuntu 12.04 LTS 64-bit desktop with 1G memory shortly after boot:
return values: 83905 3281 1169 448 412 212 284 180 146 93 54 77 64 44 48 50 68 46 28 62 40 81 34 69 52 47 31 21 35 29 39 24 83 43 22 17 10 37 30 10 17 23 12 12 12 17 9 23 12 20 2 9 22 16 16 64 15 39 8 9 7 12 8 10 10 13 8 12 58 10 7 8 18 18 10 12 11 6 9 16 9 60 5 6 7 7 5 12 98 32 7 9 4 11 7 6 11 4 11 45 7 19 4 6 6 13 5 8 5 14 7 5 11 6 3 8 12 8 3 12 10 23 11 5 9 3 10 13 46 6 2 14 7 7 4 11 9 4 1 9 5 10 4 6 14 62 5 10 106 6 7 7 6 26 3 34 80 8 12 12 8 5 2 6 7 14 5 8 8 8 7 3 6 16 4 13 16 9 4 14 6 22 14 15 6 25 4 12 6 6 3 7 13 11 5 11 3 11 8 5 16 12 2 5 3 8 4 3 11 62 147 9 54 20 14 3 5 28 12 3 6 5 7 2 9 9 10 8 11 4 4 6 10 7 20 5 4 1 6 9 6 7 9 2 2 6 5 10 3 23 5 13 6 7 20 11 12 15 17 2 4 2 3 25 2 6 3 15 4 6 5 30 15 9 4 28 3 4 6 5 6 18 7 2 9 2 2 9 8 11 8 1 4 5 4 4 2 4 6 75 9 8 6 5 3 6 3 6 15 5 5 5 6 20 6 10 7 9 6 4 9 5 6 6 9 7 5 5 5 4 4 1 46 6 10 10 92 4 7 3 3 32 6 7 34 30 2 8 2 7 8 5 9 8 4 21 9 9 12 5 12 5 3 5 5 5 65 4 4 67 7 7 5 8 7 1 3 3 5 7 4 7 7 7 15 15 8 11 5 6 2 7 12 6 5 9 13 2 19 6 2 8 3 11 8 9 38 1 7 1 20 11 5 7 1 4 6 5 4 2 2 7 5 5 2 51 5 4 9 7 4 16 3 67 7 45 9 8 9 12 38 11 6 14 2 2 10 10 6 10 4 9 9 5 4 7 2 8 7 4 5 1 2 2 6 3 5 4 7 0 2 6 5 13 5 5 4 11 4 4 9 4 2 8 10 5 6 10 6 4 2 2 6 4 6 3 4 7 5 7 0 6 4 5 4 1 8 11 15 15 14 20 168432
histogram: 31.7% 32.9% 33.3% 33.5% 33.7% 33.7% 33.9% 33.9% 34.0% 34.0% 34.0% 34.1% 34.1% 34.1% 34.1% 34.1% 34.2% 34.2% 34.2% 34.2% 34.2% 34.3% 34.3% 34.3% 34.3% 34.3% 34.3% 34.4% 34.4% 34.4% 34.4% 34.4% 34.4% 34.5% 34.5% 34.5% 34.5% 34.5% 34.5% 34.5% 34.5% 34.5% 34.5% 34.5% 34.5% 34.5% 34.5% 34.5% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.6% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 35.9% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.0% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.1% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.2% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.3% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 36.4% 100.0%
---
opensuse 11.1 64-bit with 24GB ram (busy server)
return values: 7279752 30276 15074 8523 6218 4882 3998 2940 19212 1887 1408 1123 892 670 507 673 1284 362 306 214 201 760 232 148 1062 129 266 102 661 101 116 112 911 88 86 74 174 149 70 98 627 77 632 190 115 466 85 72 545 88 92 99 87 114 127 79 379 91 190 739 93 67 178 614 294 60 149 470 84 70 35 76 179 124 58 264 72 81 59 56 295 102 343 65 73 201 174 53 206 153 278 123 88 98 42 86 127 61 62 52 90 51 110 67 148 43 62 62 112 65 339 44 235 324 60 67 86 47 138 50 687 165 64 40 65 60 665 55 326 111 64 52 43 60 149 48 444 42 33 65 117 157 70 43 219 53 181 46 177 38 125 45 95 56 189 553 204 39 76 49 88 85 730 38 109 44 895 120 241 45 44 41 51 33 35 44 357 49 39 71 28 694 263 43 104 43 45 34 35 47 153 44 233 44 31 55 40 27 547 47 264 33 36 30 33 39 38 33 105 200 42 47 41 40 25 34 109 44 28 33 45 31 47 30 117 166 36 30 199 30 160 41 168 101 40 28 92 45 42 33 53 53 31 46 30 42 32 32 57 44 38 39 25 50 49 49 1392 30 157 294 35 58 36 35 45 38 29 32 32 31 36 27 61 42 24 31 35 85 61 26 43 19 35 36 26 26 87 33 34 34 37 31 28 39 35 27 131 20 30 35 27 31 24 33 39 41 21 32 26 32 17 18 38 21 163 39 30 29 29 20 40 43 26 39 24 39 23 19 38 48 38 33 99 21 142 57 46 39 50 31 26 37 44 28 42 23 29 63 413 27 22 22 125 30 24 348 34 46 43 40 39 34 25 145 15 26 14 32 39 29 22 26 23 31 11 29 159 215 19 77 41 24 85 42 46 23 19 59 24 32 18 83 146 24 22 22 32 32 20 25 32 30 16 27 36 26 24 22 30 31 15 27 27 33 15 23 27 16 27 29 173 38 34 39 451 17 30 24 26 77 18 21 29 22 24 157 26 29 19 24 38 30 32 35 18 37 20 16 53 97 23 25 24 29 31 27 36 21 20 26 22 29 13 26 27 35 21 10 11 26 17 28 30 16 29 33 34 45 25 7 29 31 21 14 21 28 17 17 53 16 9 20 26 17 13 11 15 32 25 32 32 26 16 20 10 24 31 25 46 33 42 47 38201
histogram:
97.5% 97.9% 98.1% 98.3% 98.3% 98.4% 98.5% 98.5% 98.8% 98.8% 98.8% 98.8% 98.8% 98.8% 98.8% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 98.9% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.0% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.1% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.2% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.3% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.4% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 99.5% 100.0%
---
windows server 2008 R2 with 8G ram running for 3 days:
return values: 440570 8602 1952 1424 678 728 518 517 562 439 316 723 247 280 235 320 351 263 300 207 186 177 113 170 147 186 90 151 56 146 62 145 181 97 64 114 66 114 49 91 109 77 70 82 52 88 76 146 98 70 47 83 62 91 41 57 86 81 40 68 47 73 30 58 136 83 18 45 38 45 17 86 36 80 247 301 27 75 20 55 93 51 32 38 42 41 16 41 54 50 29 40 41 303 15 61 80 42 19 25 13 29 15 33 24 52 18 42 19 28 16 28 109 16 25 43 30 31 13 40 22 24 18 34 10 20 43 27 62 19 18 22 12 33 17 23 24 14 12 23 14 22 24 26 44 33 20 21 23 22 25 26 54 18 16 25 16 23 9 22 76 20 11 30 6 24 17 16 32 23 8 18 7 20 8 28 65 11 18 15 20 15 11 9 25 19 16 18 12 14 12 12 53 25 13 24 18 17 7 20 7 29 18 34 19 21 13 13 69 32 23 22 14 26 8 20 22 27 15 31 8 23 16 18 47 34 14 39 43 15 13 14 32 22 8 40 13 22 8 22 25 19 13 15 9 13 10 17 11 19 18 22 20 13 6 15 98 15 12 12 16 17 13 13 46 15 6 29 10 19 12 17 38 9 8 15 14 19 5 17 9 16 13 14 9 14 13 18 51 22 13 12 11 105 12 20 15 21 8 12 13 12 5 13 54 23 24 34 9 19 48 11 26 18 7 19 8 22 10 4 56 21 11 18 12 11 10 14 13 12 9 12 17 11 6 14 47 26 21 19 16 13 6 12 23 20 24 22 6 8 1 7 48 10 16 6 17 10 9 12 12 4 12 5 20 31 6 7 39 27 6 57 4 5 9 9 5 9 4 11 5 13 5 7 32 3 7 13 7 12 4 18 15 15 9 12 10 18 7 11 25 8 6 20 17 17 4 9 19 18 11 6 7 12 7 8 36 12 7 12 7 15 10 11 15 11 12 24 20 13 10 10 42 14 5 10 9 15 5 14 12 14 10 12 4 37 8 11 27 11 10 30 7 8 8 21 22 14 16 13 15 18 19 12 53 17 15 16 5 12 5 13 92 15 8 18 6 13 26 27 109 10 8 10 6 15 11 12 15 13 12 12 15 9 14 12 89 7 11 15 10 16 7 18 24 179 13 58 48 47 28 68 1632222
histogram: 20.9% 21.3% 21.4% 21.5% 21.5% 21.6% 21.6% 21.6% 21.6% 21.7% 21.7% 21.7% 21.7% 21.7% 21.7% 21.8% 21.8% 21.8% 21.8% 21.8% 21.8% 21.8% 21.8% 21.8% 21.8% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 21.9% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.0% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.1% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.2% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.3% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.4% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 22.5% 100.0%
---
windows XP guest with 1G Ram running for approx. 1 hours
return values: 71567 1377 21943 339 422 132 134 110 151 56 72 53 72 49 66 40 90 55 32 57 54 25 53 30 38 21 29 27 61 13 23 67 79 23 20 19 18 22 16 12 12 19 182 11 8 11 11 11 17 21 5 5 4 10 6 4 11 8 11 15 11 5 4 10 41 5 13 7 9 2 23 10 18 43 6 6 6 2 14 5 33 5 6 5 9 2 6 3 5 4 3 10 5 2 4 2 43 6 2 4 7 4 4 5 5 14 5 5 4 7 2 3 20 4 3 1 3 21 5 4 7 3 3 1 0 1 14 6 84 8 6 5 21 4 6 2 3 9 4 1 4 0 0 1 12 7 4 9 2 8 2 0 4 4 3 10 3 4 1 2 15 0 1 2 0 5 0 2 7 18 4 8 1 5 9 0 3 1 1 2 2 1 9 3 4 1 2 1 0 3 1 1 18 1 2 2 2 0 7 3 3 0 0 6 3 2 1 0 27 1 0 1 3 1 2 2 8 4 0 1 0 9 0 2 12 0 1 3 2 5 1 1 2 2 3 3 18 3 12 6 60 3 1 0 7 11 2 1 16 1 1 1 16 2 6 1 49 4 1 54 0 2 0 1 1 3 1 2 3 0 1 0 18 1 0 1 2 0 2 1 1 3 0 1 1 2 0 0 14 4 15 0 0 7 6 0 12 2 0 3 1 0 1 1 5 0 1 2 3 1 1 0 2 2 0 2 1 0 1 3 9 2 3 2 1 0 5 2 2 1 1 0 2 3 2 0 3 0 0 2 0 0 2 1 3 0 0 3 3 2 1 0 26 0 2 4 2 2 5 3 1 2 1 2 2 3 4 3 11 4 2 1 1 4 4 3 3 2 1 3 5 3 1 2 14 3 2 3 14 2 1 2 3 10 4 1 4 2 1 4 21 8 4 1 2 1 1 2 10 3 3 2 4 4 2 4 18 3 5 9 4 3 3 7 6 4 1 3 5 1 3 3 29 2 2 1 2 2 6 1 5 1 2 1 4 1 0 0 6 1 2 2 2 1 5 3 0 0 3 2 0 2 4 0 14 0 8 1 2 0 0 0 0 2 0 3 4 5 1 2 12 3 6 3 3 0 1 3 0 1 1 2 4 2 0 0 7 1 3 0 1 2 1 0 2 4 2 1 4 7 7 0 179427
histogram: 25.6% 26.1% 34.0% 34.1% 34.2% 34.3% 34.3% 34.4% 34.4% 34.4% 34.5% 34.5% 34.5% 34.5% 34.6% 34.6% 34.6% 34.6% 34.6% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.7% 34.8% 34.8% 34.8% 34.8% 34.8% 34.8% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 34.9% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.0% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.1% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.2% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.3% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.4% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.5% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.6% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.7% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 35.8% 100.0%
Peter
Quoted 2 lines
Paolo
Signature · 16 lines
Mit freundlichen Grüßen Peter Lieven ........................................................... KAMP Netzwerkdienste GmbH Vestische Str. 89-91 | 46117 Oberhausen Tel: +49 (0) 208.89 402-50 | Fax: +49 (0) 208.89 402-40 [email protected] | http://www.kamp.de Geschäftsführer: Heiner Lante | Michael Lante Amtsgericht Duisburg | HRB Nr. 12154 USt-Id-Nr.: DE 120607556 ...........................................................
Quoted 10 lines
ubuntu 12.04 LTS 64-bit desktop with 1G memory shortly after boot:
histogram: 31.7% 32.9% [...] 36.4% 100.0%---
opensuse 11.1 64-bit with 24GB ram (busy server)
histogram: 97.5% 97.9% [...] 99.5% 100.0%---
Quoted 7 lines
windows server 2008 R2 with 8G ram running for 3 days:
histogram: 20.9% 21.3% [...] 22.5% 100.0%---
windows XP guest with 1G Ram running for approx. 1 hours
histogram: 25.6% [...] 35.8% 100.0%
Doesn't this suggest checking the first _and the last_ word, and using the vectorized loop if none is zero?
Paolo
Am 25.03.2013 um 11:53 schrieb Paolo Bonzini <[email protected]>:
Quoted 13 lines
Quoted 13 lines
ubuntu 12.04 LTS 64-bit desktop with 1G memory shortly after boot:
histogram: 31.7% 32.9% [...] 36.4% 100.0%---
opensuse 11.1 64-bit with 24GB ram (busy server)
histogram: 97.5% 97.9% [...] 99.5% 100.0%---
windows server 2008 R2 with 8G ram running for 3 days:
histogram: 20.9% 21.3% [...] 22.5% 100.0%
Quoted 7 lines
Quoted 4 lines
---
windows XP guest with 1G Ram running for approx. 1 hours
histogram: 25.6% [...] 35.8% 100.0%Doesn't this suggest checking the first
_andthelast_word, and using the vectorized loop if none is zero?
Maybe I should have explained the output more detailed. The percentages are added. 35.8% in the second last column means that 35.8% have a return value that is less than TARGET_PAGE_SIZE. This was meant to illustrate at how many 64-bit chunks you have to look to grab a certain percentage of non-zero pages.
25.6% 26.1% 34.0% 34.1% 34.2% 34.3% 34.3% 34.4% 34.4% 34.4% 34.5% 34.5% 34.5% [...] 35.8% 100%
Looking e.g. at the third value it means that looking at the first three 64-bit chunks it will catch 34.0% of all pages. It turns out that the non-zeroness of a page can be detected looking at the first 256 or so bits and only a low percentage turns out to be non-zero at a later position. So after having checked the first chunks one by one there is no big penalty looking at the remaining chunks with the vectorized loop.
Here is the distribution of return values for the Windows XP example:
25.62% 0.49% 7.86% 0.12% 0.15% 0.05% 0.05% 0.04% 0.05% 0.02% 0.03% 0.02% 0.03% 0.02% 0.02% 0.01% 0.03% 0.02% 0.01% 0.02% 0.02% 0.01% 0.02% 0.01% 0.01% 0.01% 0.01% 0.01% 0.02% 0.00% 0.01% 0.02% 0.03% 0.01% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00% 0.01% 0.07% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.01% 0.02% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.02% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.03% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.02% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.02% 0.00% 0.00% 0.02% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 64.23%
The last value is the percentage of return value of TARGET_PAGE_SIZE meaning the page is all zero.
Peter
Quoted 5 lines
Maybe I should have explained the output more detailed. The percentages are added. 35.8% in the second last column means that
35.8% have a return value that is less thanTARGET_PAGE_SIZE. This was meant to illustrate at how many 64-bit chunks you have to look to grab a certain percentage of non-zero pages.
Ok, I wrongly understood that many pages had 4088 zero bytes but the last 8 were not zero. Now it's clearer, and more logical too. :)
Quoted 8 lines
Looking e.g. at the third value it means that looking at the first three 64-bit chunks it will catch 34.0% of all pages.
It turns out that the non-zeroness of a page can be detected looking at the first 256 or so bits and only a low
percentage turns out to be non-zero at a later position. So after having checked the first chunks one by one
there is no big penalty looking at the remaining chunks with the vectorized loop.
I think it makes most sense to unroll the first four non-vectorized iterations, i.e. not use SSE and use three or four ifs. Either:
if (foo[0]) return 0; if (foo[1]) return 8; if (foo[2]) return 16; if (foo[3]) return 24;
or
if (foo[0]) return 0; if (foo[1] | foo[2] | foo[3]) return 8;
and then proceed on the remaining 4096-4*sizeof(long) bytes with the vectorized loop. foo+4 is aligned for SIMD operations on both 32- and 64-bit machines, which makes this a nice choice.
Paolo
Quoted 56 lines
Here is the distribution of return values for the Windows XP example:
25.62% 0.49% 7.86% 0.12% 0.15% 0.05% 0.05% 0.04% 0.05% 0.02% 0.03% 0.02% 0.03% 0.02% 0.02% 0.01% 0.03% 0.02% 0.01% 0.02% 0.02% 0.01% 0.02% 0.01% 0.01% 0.01% 0.01% 0.01% 0.02% 0.00% 0.01% 0.02% 0.03% 0.01% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00% 0.01% 0.07% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.01% 0.02% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.02% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.03% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.02% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.02% 0.00% 0.00% 0.02% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 64.23%
The last value is the percentage of return value of
TARGET_PAGE_SIZEmeaning the page is all zero.Peter
Am 25.03.2013 um 14:02 schrieb Paolo Bonzini <[email protected]>:
Quoted 26 lines
Quoted 5 lines
Maybe I should have explained the output more detailed. The percentages are added. 35.8% in the second last column means that
35.8% have a return value that is less thanTARGET_PAGE_SIZE. This was meant to illustrate at how many 64-bit chunks you have to look to grab a certain percentage of non-zero pages.Ok, I wrongly understood that many pages had 4088 zero bytes but the last 8 were not zero. Now it's clearer, and more logical too. :)
Quoted 8 lines
Looking e.g. at the third value it means that looking at the first three 64-bit chunks it will catch 34.0% of all pages.
It turns out that the non-zeroness of a page can be detected looking at the first 256 or so bits and only a low
percentage turns out to be non-zero at a later position. So after having checked the first chunks one by one
there is no big penalty looking at the remaining chunks with the vectorized loop.I think it makes most sense to unroll the first four non-vectorized iterations, i.e. not use SSE and use three or four ifs. Either:
if (foo[0]) return 0; if (foo[1]) return 8; if (foo[2]) return 16; if (foo[3]) return 24;
Quoted 8 lines
or
if (foo[0]) return 0; if (foo[1] | foo[2] | foo[3]) return 8;and then proceed on the remaining 4096-4*sizeof(long) bytes with the vectorized loop. foo+4 is aligned for SIMD operations on both 32- and 64-bit machines, which makes this a nice choice.
i can't start at foo+4 since the remaining X-4*sizeof(long) bytes are not dividable by 8*sizeof(VECTYPE).
I could just do sty like the following:
const unsigned long *tmp = buf;
for (i = 0;
i < sizeof(VECTYPE) * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR
/ sizeof(unsigned long);
i += 4) {
if (tmp[i + 0]) return i * sizeof(unsigned long);
if (tmp[i + 1]) return (i+1) * sizeof(unsigned long);
if (tmp[i + 2]) return (i+2) * sizeof(unsigned long);
if (tmp[i + 3]) return (i+3) * sizeof(unsigned long);
}
for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR;
i < len / sizeof(VECTYPE);
i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
…
}Peter
Quoted 59 lines
Paolo
Quoted 56 lines
Here is the distribution of return values for the Windows XP example:
25.62% 0.49% 7.86% 0.12% 0.15% 0.05% 0.05% 0.04% 0.05% 0.02% 0.03% 0.02% 0.03% 0.02% 0.02% 0.01% 0.03% 0.02% 0.01% 0.02% 0.02% 0.01% 0.02% 0.01% 0.01% 0.01% 0.01% 0.01% 0.02% 0.00% 0.01% 0.02% 0.03% 0.01% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00% 0.01% 0.07% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.01% 0.02% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.02% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.03% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.02% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.02% 0.00% 0.00% 0.02% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.01% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 64.23%
The last value is the percentage of return value of
TARGET_PAGE_SIZEmeaning the page is all zero.Peter
Am 25.03.2013 um 14:23 schrieb Peter Lieven <[email protected]>:
Quoted 52 lines
Am 25.03.2013 um 14:02 schrieb Paolo Bonzini <[email protected]>:
Quoted 26 lines
Quoted 5 lines
Maybe I should have explained the output more detailed. The percentages are added. 35.8% in the second last column means that
35.8% have a return value that is less thanTARGET_PAGE_SIZE. This was meant to illustrate at how many 64-bit chunks you have to look to grab a certain percentage of non-zero pages.Ok, I wrongly understood that many pages had 4088 zero bytes but the last 8 were not zero. Now it's clearer, and more logical too. :)
Quoted 8 lines
Looking e.g. at the third value it means that looking at the first three 64-bit chunks it will catch 34.0% of all pages.
It turns out that the non-zeroness of a page can be detected looking at the first 256 or so bits and only a low
percentage turns out to be non-zero at a later position. So after having checked the first chunks one by one
there is no big penalty looking at the remaining chunks with the vectorized loop.I think it makes most sense to unroll the first four non-vectorized iterations, i.e. not use SSE and use three or four ifs. Either:
if (foo[0]) return 0;
if (foo[1]) return 8;
if (foo[2]) return 16;
if (foo[3]) return 24;Quoted 8 lines
or
if (foo[0]) return 0;
if (foo[1] | foo[2] | foo[3]) return 8;and then proceed on the remaining 4096-4*sizeof(long) bytes with the vectorized loop. foo+4 is aligned for SIMD operations on both 32- and 64-bit machines, which makes this a nice choice.
i can't start at foo+4 since the remaining X-4*sizeof(long) bytes are not dividable by 8*sizeof(VECTYPE).
I could just do sty like the following:
const unsigned long *tmp = buf; for (i = 0; i < sizeof(VECTYPE) * BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR / sizeof(unsigned long); i += 4) { if (tmp[i + 0]) return i * sizeof(unsigned long); if (tmp[i + 1]) return (i+1) * sizeof(unsigned long); if (tmp[i + 2]) return (i+2) * sizeof(unsigned long);
Quoted 8 lines
if (tmp[i + 3]) return (i+3) * sizeof(unsigned long);
}
for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR;
i < len / sizeof(VECTYPE);
i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
…
}performance of the above is bad compared to:
for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) {
if (!ALL_EQ(p[i], zero)) {
return i * sizeof(VECTYPE);
}
}…
The above is basically what old is_dup_page is doing, but after the first 8 iterations the optimized version kicks in.
Peter
Il 25/03/2013 14:32, Peter Lieven ha scritto:
Quoted 43 lines
Am 25.03.2013 um 14:23 schrieb Peter Lieven <[email protected]>:
Quoted 40 lines
Am 25.03.2013 um 14:02 schrieb Paolo Bonzini <[email protected]>:
Quoted 26 lines
Quoted 5 lines
Maybe I should have explained the output more detailed. The percentages are added. 35.8% in the second last column means that
35.8% have a return value that is less thanTARGET_PAGE_SIZE. This was meant to illustrate at how many 64-bit chunks you have to look to grab a certain percentage of non-zero pages.Ok, I wrongly understood that many pages had 4088 zero bytes but the last 8 were not zero. Now it's clearer, and more logical too. :)
Quoted 8 lines
Looking e.g. at the third value it means that looking at the first three 64-bit chunks it will catch 34.0% of all pages.
It turns out that the non-zeroness of a page can be detected looking at the first 256 or so bits and only a low
percentage turns out to be non-zero at a later position. So after having checked the first chunks one by one
there is no big penalty looking at the remaining chunks with the vectorized loop.I think it makes most sense to unroll the first four non-vectorized iterations, i.e. not use SSE and use three or four ifs. Either:
if (foo[0]) return 0;
if (foo[1]) return 8;
if (foo[2]) return 16;
if (foo[3]) return 24;Quoted 8 lines
or
if (foo[0]) return 0;
if (foo[1] | foo[2] | foo[3]) return 8;and then proceed on the remaining 4096-4*sizeof(long) bytes with the vectorized loop. foo+4 is aligned for SIMD operations on both 32- and 64-bit machines, which makes this a nice choice.
i can't start at foo+4 since the remaining X-4*sizeof(long) bytes are not dividable by 8*sizeof(VECTYPE).
Hmm, right. What about just processing the first few longs twice, i.e. the above followed by "for (i = 0; i < len / sizeof(sizeof(VECTYPE); i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR)"?
Paolo
Quoted 24 lines
Quoted 6 lines
for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i < len / sizeof(VECTYPE); i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) { … }performance of the above is bad compared to:
for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) { if (!ALL_EQ(p[i], zero)) { return i * sizeof(VECTYPE); } }…
The above is basically what old
is_dup_pageis doing, but after the first 8 iterations the optimized version kicks in.Peter
Am 25.03.2013 um 15:34 schrieb Paolo Bonzini <[email protected]>:
Quoted 42 lines
Il 25/03/2013 14:32, Peter Lieven ha scritto:
Quoted 41 lines
Am 25.03.2013 um 14:23 schrieb Peter Lieven <[email protected]>:
Quoted 38 lines
Am 25.03.2013 um 14:02 schrieb Paolo Bonzini <[email protected]>:
Quoted 34 lines
Quoted 5 lines
Maybe I should have explained the output more detailed. The percentages are added. 35.8% in the second last column means that
35.8% have a return value that is less thanTARGET_PAGE_SIZE. This was meant to illustrate at how many 64-bit chunks you have to look to grab a certain percentage of non-zero pages.Ok, I wrongly understood that many pages had 4088 zero bytes but the last 8 were not zero. Now it's clearer, and more logical too. :)
Quoted 8 lines
Looking e.g. at the third value it means that looking at the first three 64-bit chunks it will catch 34.0% of all pages.
It turns out that the non-zeroness of a page can be detected looking at the first 256 or so bits and only a low
percentage turns out to be non-zero at a later position. So after having checked the first chunks one by one
there is no big penalty looking at the remaining chunks with the vectorized loop.I think it makes most sense to unroll the first four non-vectorized iterations, i.e. not use SSE and use three or four ifs. Either:
if (foo[0]) return 0;
if (foo[1]) return 8;
if (foo[2]) return 16;
if (foo[3]) return 24;or
if (foo[0]) return 0;
if (foo[1] | foo[2] | foo[3]) return 8;and then proceed on the remaining 4096-4*sizeof(long) bytes with the vectorized loop. foo+4 is aligned for SIMD operations on both 32- and 64-bit machines, which makes this a nice choice.
Quoted 7 lines
Quoted 2 lines
Quoted 2 lines
i can't start at foo+4 since the remaining X-4*sizeof(long) bytes are not dividable by 8*sizeof(VECTYPE).
Hmm, right. What about just processing the first few longs twice, i.e. the above followed by "for (i = 0; i < len /
sizeof(sizeof(VECTYPE); i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR)"?
i will profile it tomorrow.
what is bad about processing the first 8 vectors like described below?
Quoted 5 lines
Quoted 5 lines
for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) { if (!ALL_EQ(p[i], zero)) { return i * sizeof(VECTYPE); }}
this way it would not be necessary to process them twice.
Peter
Am 25.03.2013 um 15:34 schrieb Paolo Bonzini <[email protected]>:
Quoted 4 lines
Hmm, right. What about just processing the first few longs twice, i.e. the above followed by "for (i = 0; i < len /
sizeof(sizeof(VECTYPE); i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR)"?
I tested this version as v3:
size_t buffer_find_nonzero_offset_v3(const void *buf, size_t len)
{
VECTYPE *p = (VECTYPE *)buf;
unsigned long *tmp = (unsigned long *)buf;
VECTYPE zero = ZERO_SPLAT;
size_t i;
assert(can_use_buffer_find_nonzero_offset(buf, len));
if (!len) {
return 0;
}
if (tmp[0]) {
return 0;
}
if (tmp[1]) {
return 1 * sizeof(unsigned long);
}
if (tmp[2]) {
return 2 * sizeof(unsigned long);
}
if (tmp[3]) {
return 3 * sizeof(unsigned long);
}
for (i = 0; i < len / sizeof(VECTYPE);
i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
VECTYPE tmp0 = p[i + 0] | p[i + 1];
VECTYPE tmp1 = p[i + 2] | p[i + 3];
VECTYPE tmp2 = p[i + 4] | p[i + 5];
VECTYPE tmp3 = p[i + 6] | p[i + 7];
VECTYPE tmp01 = tmp0 | tmp1;
VECTYPE tmp23 = tmp2 | tmp3;
if (!ALL_EQ(tmp01 | tmp23, zero)) {
break;
}
}
return i * sizeof(VECTYPE);
}For reference this is v2:
size_t buffer_find_nonzero_offset_v2(const void *buf, size_t len)
{
VECTYPE *p = (VECTYPE *)buf;
VECTYPE zero = ZERO_SPLAT;
size_t i;
assert(can_use_buffer_find_nonzero_offset(buf, len));
if (!len) {
return 0;
}
for (i = 0; i < BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR; i++) {
if (!ALL_EQ(p[i], zero)) {
return i * sizeof(VECTYPE);
}
}
for (i = BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR;
i < len / sizeof(VECTYPE);
i += BUFFER_FIND_NONZERO_OFFSET_UNROLL_FACTOR) {
VECTYPE tmp0 = p[i + 0] | p[i + 1];
VECTYPE tmp1 = p[i + 2] | p[i + 3];
VECTYPE tmp2 = p[i + 4] | p[i + 5];
VECTYPE tmp3 = p[i + 6] | p[i + 7];
VECTYPE tmp01 = tmp0 | tmp1;
VECTYPE tmp23 = tmp2 | tmp3;
if (!ALL_EQ(tmp01 | tmp23, zero)) {
break;
}
}
return i * sizeof(VECTYPE);
}I ran 3*2 tests. Each with 1GB memory and 256 iterations of checking each 4k page for zero.
1) all pages zero
a) SSE2is_zero_page: res=67108864 (ticks 3289 user 1 system)is_zero_page_v2: res=67108864 (ticks 3326 user 0 system)is_zero_page_v3: res=67108864 (ticks 3305 user 3 system)is_dup_page: res=67108864 (ticks 3648 user 1 system)
b) unsigned long arithmetic
is_zero_page: res=67108864 (ticks 3474 user 3 system)is_zero_page_2: res=67108864 (ticks 3516 user 1 system)is_zero_page_3: res=67108864 (ticks 3525 user 3 system)is_dup_page: res=67108864 (ticks 3826 user 4 system)
2) all pages non-zero, but first 64-bit of each page zero
a) SSE2is_zero_page: res=0 (ticks 251 user 0 system)is_zero_page_v2: res=0 (ticks 87 user 0 system)is_zero_page_v3: res=0 (ticks 91 user 0 system)is_dup_page: res=0 (ticks 82 user 0 system)
b) unsigned long arithmeticis_zero_page: res=0 (ticks 209 user 0 system)is_zero_page_v2: res=0 (ticks 89 user 0 system)is_zero_page_v3: res=0 (ticks 88 user 0 system)is_dup_page: res=0 (ticks 88 user 0 system)
3) all pages non-zero, but first 256-bit of each page zero
a)is_zero_pages: res=0 (ticks 260 user 0 system)is_zero_pages_2: res=0 (ticks 199 user 0 system)is_zero_pages_3: res=0 (ticks 342 user 0 system)is_dup_pages: res=0 (ticks 223 user 0 system)
b) unsigned long arithmeticis_zero_pages: res=0 (ticks 230 user 0 system)is_zero_pages_2: res=0 (ticks 194 user 0 system)is_zero_pages_3: res=0 (ticks 280 user 0 system)is_dup_pages: res=0 (ticks 191 user 0 system)
---
is_zero_page is the version from patch set v4.is_zero_page_2 is checking the first 8 * sizeof(VECTYPE) chunks one by one and than continuing 8 chunks at once without double-checks is_zero_page_3 is the above version.is_dup_page the old implementation.
All compiled with gcc -O3
If noone objects I would use is_zero_page_2 and continue with v5 of the patch set. As I am ooo for the next 8 days from tomorrow. i prefer v3 as it has better performance if the non-zeroness is within the 8*sizeof(VECTYPE) bytes and not in the first 256-bit.
Paolo, with the version that has lower setup costs in mind shall I use the vectorized or the unrolled version of patch 4 (find_next_bit optimization)?
Peter
Il 26/03/2013 09:14, Peter Lieven ha scritto:
Quoted 4 lines
If noone objects I would use
is_zero_page_2and continue with v5 of the patch set. As I am ooo for the next 8 days from tomorrow. i prefer v3 as it has better performance if the non-zeroness is within the 8*sizeof(VECTYPE) bytes and not in the first 256-bit.
Either v2 or v3 is fine. v3 has slightly simpler code and v2 optimizes for a rare case, but v2 is indeed a bit faster and your benchmarking effort should be rewarded. :)
Quoted 3 lines
Paolo, with the version that has lower setup costs in mind shall I use the vectorized or the unrolled version of patch 4 (
find_next_bitoptimization)?
I think for that we should, at least for now, use the version we discussed a few weeks ago (with no SIMD and just unrolling).
Paolo