qemu-block
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Qemu-block] [PATCH v4 07/20] hbitmap: add hbitmap_merge


From: Stefan Hajnoczi
Subject: Re: [Qemu-block] [PATCH v4 07/20] hbitmap: add hbitmap_merge
Date: Thu, 2 Apr 2015 13:19:41 +0100
User-agent: Mutt/1.5.23 (2014-03-12)

On Fri, Mar 20, 2015 at 03:16:50PM -0400, John Snow wrote:
> We add a bitmap merge operation to assist in error cases
> where we wish to combine two bitmaps together.
> 
> This is algorithmically O(bits) provided HBITMAP_LEVELS remains
> constant. For a full bitmap on a 64bit machine:
> sum(bits/64^k, k, 0, HBITMAP_LEVELS) ~= 1.01587 * bits
> 
> We may be able to improve running speed for particularly sparse
> bitmaps by using iterators, but the running time for dense maps
> will be worse.
> 
> We present the simpler solution first, and we can refine it later
> if needed.
> 
> Signed-off-by: John Snow <address@hidden>
> Reviewed-by: Max Reitz <address@hidden>
> ---
>  include/qemu/hbitmap.h | 11 +++++++++++
>  util/hbitmap.c         | 29 +++++++++++++++++++++++++++++
>  2 files changed, 40 insertions(+)

Reviewed-by: Stefan Hajnoczi <address@hidden>

Attachment: pgpyiFX_r8pMM.pgp
Description: PGP signature


reply via email to

[Prev in Thread] Current Thread [Next in Thread]