[Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Dmitry Konishchev]

[-- Attachment #1: Type: text/plain, Size: 1419 bytes --]

Hi! I was wondering why qemu-img consumes so much CPU when it converts
one partially allocated qcow2 image to another qcow2 image and I've
written a patch which improves the situation a little.

I have an image:
> $ qemu-img info ubuntu.10.04.qcow2
> image: ubuntu.10.04.qcow2
> file format: qcow2
> virtual size: 20G (21474836480 bytes)
> disk size: 2.2G
> cluster_size: 65536

I create a new copy on write image:
> $ qemu-img create -f qcow2 -o backing_file=ubuntu.10.04.qcow2 volume.qcow2 100G
... and use it for a while.

Then I want to create a non-copy on write image from it to send it to someone:
> qemu-img convert -O qcow2 volume.qcow2 snapshot.qcow2


The last operation consumes a lot of CPU, so I run qemu-img under
profiler and realized, that most of CPU time is consumed by
is_not_zero() function. I had made a couple of optimizations on it and
got the following output for `time qemu-img convert -O qcow2
volume.qcow2 snapshot.qcow2`:

x86_64 machine:

Original qemu-img:
real 0m56.159s
user 0m34.670s
sys  0m12.079s

Patched qemu-img:
real 0m34.805s
user 0m18.445s
sys  0m12.552s


x86 machine:

Original qemu-img:
real 1m13.991s
user 0m24.734s
sys  0m6.604s

Patched qemu-img:
real 1m6.898s
user 0m16.021s
sys  0m6.700s

Please, see on the consumed user CPU time. I think that the
optimization worth it, so it will be awesome if you accept this patch
(see the attachment).

Thanks for your attention.

[-- Attachment #2: 0001-is_not_zero-optimization-in-qemu-img.patch --]
[-- Type: text/x-patch, Size: 1239 bytes --]

From 61d228c0ea0d518de48a08577cd6d282e2f97759 Mon Sep 17 00:00:00 2001
From: Dmitry Konishchev <konishchev@gmail.com>
Date: Tue, 17 May 2011 16:29:48 +0400
Subject: [PATCH] is_not_zero() optimization in qemu-img

---
 qemu-img.c |   24 +++++++++++++++++++++---
 1 files changed, 21 insertions(+), 3 deletions(-)

diff --git a/qemu-img.c b/qemu-img.c
index e825123..41b4e32 100644
--- a/qemu-img.c
+++ b/qemu-img.c
@@ -498,12 +498,30 @@ static int img_commit(int argc, char **argv)
 
 static int is_not_zero(const uint8_t *sector, int len)
 {
+    /*
+     * Use long as the biggest available internal data type that fits into the
+     * CPU register and unroll the loop to smooth out the effect of memory
+     * latency.
+     */
+
     int i;
-    len >>= 2;
-    for(i = 0;i < len; i++) {
-        if (((uint32_t *)sector)[i] != 0)
+    len /= sizeof(long);
+
+    long d0;
+    long d1;
+    long d2;
+    long d3;
+
+    for(i = 0; i < len; i += 4) {
+        d0 = ((const long*) sector)[i + 0];
+        d1 = ((const long*) sector)[i + 1];
+        d2 = ((const long*) sector)[i + 2];
+        d3 = ((const long*) sector)[i + 3];
+
+        if (d0 || d1 || d2 || d3)
             return 1;
     }
+
     return 0;
 }
 
-- 
1.7.4.1

Re: [Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Stefan Hajnoczi]

On Tue, May 17, 2011 at 3:33 PM, Dmitry Konishchev <konishchev@gmail.com> wrote:
> Hi! I was wondering why qemu-img consumes so much CPU when it converts
> one partially allocated qcow2 image to another qcow2 image and I've
> written a patch which improves the situation a little.

Please see http://wiki.qemu.org/Contribute/SubmitAPatch, which asks
that patches are sent inline (not as attachments) for easy review and
that you follow the coding style (see the CODING_STYLE file).  Patches
also need a Signed-off-by: line.

The unrolled loop makes the function rely on len being a multiple of
sizeof(long) * 4, otherwise it accesses beyond the end of sector[].
So for this use case it's okay but the function is generic anymore.

GNU cp(1) tries to detect holes in files and image formats could tell
us about unallocated regions using bdrv_is_allocated().  So I think
there are ways to avoid comparing so much data in the first place, if
you are interested in looking into that.

Stefan

Re: [Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Dmitry Konishchev]

On Tue, May 17, 2011 at 7:35 PM, Stefan Hajnoczi <stefanha@gmail.com> wrote:
> Please see http://wiki.qemu.org/Contribute/SubmitAPatch, which asks
> that patches are sent inline (not as attachments) for easy review and
> that you follow the coding style (see the CODING_STYLE file).  Patches
> also need a Signed-off-by: line.
OK, thanks. I'll fix this in case you are willing to accept the patch.

On Tue, May 17, 2011 at 7:35 PM, Stefan Hajnoczi <stefanha@gmail.com> wrote:
> The unrolled loop makes the function rely on len being a multiple of
> sizeof(long) * 4, otherwise it accesses beyond the end of sector[].
> So for this use case it's okay but the function is generic anymore.
Yeah, but this function is static and within the whole file it is used
only for comparing clusters, so I think that we can sacrifice it's
universality for the sake of the performance.

On Tue, May 17, 2011 at 7:35 PM, Stefan Hajnoczi <stefanha@gmail.com> wrote:
> GNU cp(1) tries to detect holes in files and image formats could tell
> us about unallocated regions using bdrv_is_allocated().  So I think
> there are ways to avoid comparing so much data in the first place, if
> you are interested in looking into that.
OK, thanks, I'll look on this function (but sorry, only after 2 weeks,
since I'm on my vacation). But actually I think, that it will be
better to use the both ways, since they can give a boost in different
usecases.

So, if you are agreed with the said above, you can accept this patch
and then I'll write an enchancement for it with bdrv_is_allocated()
because it is going to include this patch.

--
Dmitry Konishchev
mailto:konishchev@gmail.com

Re: [Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Stefan Hajnoczi]

On Wed, May 18, 2011 at 7:55 AM, Dmitry Konishchev <konishchev@gmail.com> wrote:
> So, if you are agreed with the said above, you can accept this patch
> and then I'll write an enchancement for it with bdrv_is_allocated()
> because it is going to include this patch.

Yes, optimizing is_not_zero() is good.  The only additional thing I
suggest is adding a comment before the function to document the length
constraint.

Kevin Wolf is CCed, he's the QEMU block layer maintainer and may have
additional thoughts before accepting this patch.

Stefan

Re: [Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Kevin Wolf]

Am 18.05.2011 09:57, schrieb Stefan Hajnoczi:
> On Wed, May 18, 2011 at 7:55 AM, Dmitry Konishchev <konishchev@gmail.com> wrote:
>> So, if you are agreed with the said above, you can accept this patch
>> and then I'll write an enchancement for it with bdrv_is_allocated()
>> because it is going to include this patch.
> 
> Yes, optimizing is_not_zero() is good.  The only additional thing I
> suggest is adding a comment before the function to document the length
> constraint.
> 
> Kevin Wolf is CCed, he's the QEMU block layer maintainer and may have
> additional thoughts before accepting this patch.

For this one not really. Except for the coding style it looks good to me.

A future bdrv_is_allocated() patch must make sure that the conversion
falls back to a simple is_not_zero() when a backing file is used.

Kevin

Re: [Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Dmitry Konishchev]

On 18.05.2011 11:57, Stefan Hajnoczi wrote:
> Yes, optimizing is_not_zero() is good.  The only additional thing I
> suggest is adding a comment before the function to document the length
> constraint.

OK, fixed.


On 18.05.2011 12:05, Kevin Wolf wrote:
> A future bdrv_is_allocated() patch must make sure that the conversion
> falls back to a simple is_not_zero() when a backing file is used.

Thanks, I'll take this into account.


Signed-off-by: Dmitry Konishchev <konishchev@gmail.com>
---
  qemu-img.c |   30 +++++++++++++++++++++++++++---
  1 files changed, 27 insertions(+), 3 deletions(-)

diff --git a/qemu-img.c b/qemu-img.c
index e825123..7665c2f 100644
--- a/qemu-img.c
+++ b/qemu-img.c
@@ -496,14 +496,38 @@ static int img_commit(int argc, char **argv)
      return 0;
  }

+/*
+ * Checks whether the sector is not a zero sector.
+ *
+ * Attention! The len must be a multiple of 4 * sizeof(long) due to
+ * restriction of optimizations in this function.
+ */
  static int is_not_zero(const uint8_t *sector, int len)
  {
+    /*
+     * Use long as the biggest available internal data type that fits 
into the
+     * CPU register and unroll the loop to smooth out the effect of memory
+     * latency.
+     */
+
      int i;
-    len >>= 2;
-    for(i = 0;i < len; i++) {
-        if (((uint32_t *)sector)[i] != 0)
+    len /= sizeof(long);
+
+    long d0;
+    long d1;
+    long d2;
+    long d3;
+
+    for(i = 0; i < len; i += 4) {
+        d0 = ((const long*) sector)[i + 0];
+        d1 = ((const long*) sector)[i + 1];
+        d2 = ((const long*) sector)[i + 2];
+        d3 = ((const long*) sector)[i + 3];
+
+        if (d0 || d1 || d2 || d3)
              return 1;
      }
+
      return 0;
  }

-- 
1.7.4.1

Re: [Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Kevin Wolf]

Am 18.05.2011 11:18, schrieb Dmitry Konishchev:
> On 18.05.2011 11:57, Stefan Hajnoczi wrote:
>> Yes, optimizing is_not_zero() is good.  The only additional thing I
>> suggest is adding a comment before the function to document the length
>> constraint.
> 
> OK, fixed.
> 
> 
> On 18.05.2011 12:05, Kevin Wolf wrote:
>> A future bdrv_is_allocated() patch must make sure that the conversion
>> falls back to a simple is_not_zero() when a backing file is used.
> 
> Thanks, I'll take this into account.
> 
> 
> Signed-off-by: Dmitry Konishchev <konishchev@gmail.com>
> ---
>   qemu-img.c |   30 +++++++++++++++++++++++++++---
>   1 files changed, 27 insertions(+), 3 deletions(-)
> 
> diff --git a/qemu-img.c b/qemu-img.c
> index e825123..7665c2f 100644
> --- a/qemu-img.c
> +++ b/qemu-img.c
> @@ -496,14 +496,38 @@ static int img_commit(int argc, char **argv)
>       return 0;
>   }
> 
> +/*
> + * Checks whether the sector is not a zero sector.
> + *
> + * Attention! The len must be a multiple of 4 * sizeof(long) due to
> + * restriction of optimizations in this function.
> + */
>   static int is_not_zero(const uint8_t *sector, int len)
>   {
> +    /*
> +     * Use long as the biggest available internal data type that fits 
> into the
> +     * CPU register and unroll the loop to smooth out the effect of memory
> +     * latency.
> +     */
> +
>       int i;
> -    len >>= 2;
> -    for(i = 0;i < len; i++) {
> -        if (((uint32_t *)sector)[i] != 0)
> +    len /= sizeof(long);
> +
> +    long d0;
> +    long d1;
> +    long d2;
> +    long d3;

Please move the declarations to the start of the function.

I also would use a single line like "long d0, d1, d2, d3;", but that's
up to you.

> +
> +    for(i = 0; i < len; i += 4) {
> +        d0 = ((const long*) sector)[i + 0];
> +        d1 = ((const long*) sector)[i + 1];
> +        d2 = ((const long*) sector)[i + 2];
> +        d3 = ((const long*) sector)[i + 3];

I would suggest to declare a const long* variable so that you don't have
to cast each time you use, but that's probably a matter of taste.

> +
> +        if (d0 || d1 || d2 || d3)
>               return 1;

Coding style requires braces here.

>       }
> +
>       return 0;
>   }

Please make sure that your patch isn't line-wrapped when you send it for
inclusion. git send-email will do the right thing.

Kevin

Re: [Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Dmitry Konishchev]

On 18.05.2011 13:31, Kevin Wolf wrote:
> Please move the declarations to the start of the function.
>
> I also would use a single line like "long d0, d1, d2, d3;", but that's
> up to you.
>
>> +
>> +    for(i = 0; i<  len; i += 4) {
>> +        d0 = ((const long*) sector)[i + 0];
>> +        d1 = ((const long*) sector)[i + 1];
>> +        d2 = ((const long*) sector)[i + 2];
>> +        d3 = ((const long*) sector)[i + 3];
>
> I would suggest to declare a const long* variable so that you don't have
> to cast each time you use, but that's probably a matter of taste.
>
>> +
>> +        if (d0 || d1 || d2 || d3)
>>                return 1;
>
> Coding style requires braces here.
>
>>        }
>> +
>>        return 0;
>>    }

OK, fixed.


Signed-off-by: Dmitry Konishchev <konishchev@gmail.com>
---
  qemu-img.c |   29 ++++++++++++++++++++++++++---
  1 files changed, 26 insertions(+), 3 deletions(-)

diff --git a/qemu-img.c b/qemu-img.c
index e825123..c849c6f 100644
--- a/qemu-img.c
+++ b/qemu-img.c
@@ -496,14 +496,37 @@ static int img_commit(int argc, char **argv)
      return 0;
  }

+/*
+ * Checks whether the sector is not a zero sector.
+ *
+ * Attention! The len must be a multiple of 4 * sizeof(long) due to
+ * restriction of optimizations in this function.
+ */
  static int is_not_zero(const uint8_t *sector, int len)
  {
+    /*
+     * Use long as the biggest available internal data type that fits 
into the
+     * CPU register and unroll the loop to smooth out the effect of memory
+     * latency.
+     */
+
      int i;
-    len >>= 2;
-    for(i = 0;i < len; i++) {
-        if (((uint32_t *)sector)[i] != 0)
+    long d0, d1, d2, d3;
+    const long * const data = (const long *) sector;
+
+    len /= sizeof(long);
+
+    for(i = 0; i < len; i += 4) {
+        d0 = data[i + 0];
+        d1 = data[i + 1];
+        d2 = data[i + 2];
+        d3 = data[i + 3];
+
+        if (d0 || d1 || d2 || d3) {
              return 1;
+        }
      }
+
      return 0;
  }

-- 
1.7.4.1

[Qemu-devel] [PATCH] is_not_zero() optimization in qemu-img

[Dmitry Konishchev]

Please sorry - I've sent the previous email via Thunderbird which promised that won't wrap the lines but it did. :(
Sending this via git send-email.

Signed-off-by: Dmitry Konishchev <konishchev@gmail.com>
---
 qemu-img.c |   29 ++++++++++++++++++++++++++---
 1 files changed, 26 insertions(+), 3 deletions(-)

diff --git a/qemu-img.c b/qemu-img.c
index e825123..c849c6f 100644
--- a/qemu-img.c
+++ b/qemu-img.c
@@ -496,14 +496,37 @@ static int img_commit(int argc, char **argv)
     return 0;
 }
 
+/*
+ * Checks whether the sector is not a zero sector.
+ *
+ * Attention! The len must be a multiple of 4 * sizeof(long) due to
+ * restriction of optimizations in this function.
+ */
 static int is_not_zero(const uint8_t *sector, int len)
 {
+    /*
+     * Use long as the biggest available internal data type that fits into the
+     * CPU register and unroll the loop to smooth out the effect of memory
+     * latency.
+     */
+
     int i;
-    len >>= 2;
-    for(i = 0;i < len; i++) {
-        if (((uint32_t *)sector)[i] != 0)
+    long d0, d1, d2, d3;
+    const long * const data = (const long *) sector;
+
+    len /= sizeof(long);
+
+    for(i = 0; i < len; i += 4) {
+        d0 = data[i + 0];
+        d1 = data[i + 1];
+        d2 = data[i + 2];
+        d3 = data[i + 3];
+
+        if (d0 || d1 || d2 || d3) {
             return 1;
+        }
     }
+
     return 0;
 }
 
-- 
1.7.4.1

Re: [Qemu-devel] [PATCH] is_not_zero() optimization in qemu-img

[Kevin Wolf]

Am 18.05.2011 13:03, schrieb Dmitry Konishchev:
> Please sorry - I've sent the previous email via Thunderbird which promised that won't wrap the lines but it did. :(
> Sending this via git send-email.
> 
> Signed-off-by: Dmitry Konishchev <konishchev@gmail.com>

Thanks, applied to the block branch.

If you add a commit message that describes what the patch changes (and
why) next time, the patch would be perfect. ;-) For now I took some part
from your initial mail as the commit message.

Kevin

Re: [Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Peter Maydell]

On 18 May 2011 10:18, Dmitry Konishchev <konishchev@gmail.com> wrote:

> + * Attention! The len must be a multiple of 4 * sizeof(long) due to
> + * restriction of optimizations in this function.

You could assert() this:
 assert(argc % (4 * sizeof(long)) == 0);

-- PMM

Re: [Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Peter Maydell]

On 18 May 2011 10:40, Peter Maydell <peter.maydell@linaro.org> wrote:
> On 18 May 2011 10:18, Dmitry Konishchev <konishchev@gmail.com> wrote:
>
>> + * Attention! The len must be a multiple of 4 * sizeof(long) due to
>> + * restriction of optimizations in this function.
>
> You could assert() this:
>  assert(argc % (4 * sizeof(long)) == 0);

s/len/argc/, obviously!

-- PMM

Re: [Qemu-devel] [PATCH] [qemu-img] CPU consuming optimization

[Dmitry Konishchev]

On Wed, May 18, 2011 at 1:40 PM, Peter Maydell <peter.maydell@linaro.org> wrote:
> You could assert() this:
>  assert(argc % (4 * sizeof(long)) == 0);

Yeah, but actually I'm not really like the idea to include asserts in
the little bottleneck functions if the configuration script doesn't
include -DNDEBUG in the compiler cflags by default. Because in this
case it's yet additional instructions on which CPU pipeline is going
to stumble upon + it also decreases the chances for this function to
be inlined by the compiler. But inlining can give us an additional
boost + compiler will be able to understand that, in the place where
the function is inlined, it is always called with len == 512 and
optimize the code for this case by automatically unroll the loop and
so on.

But in the bottom line I don't really mind to include the assert -
just believe that it's not really worth it.

-- 
Dmitry Konishchev
mailto:konishchev@gmail.com