qemu-devel
[Top][All Lists]
Advanced

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

Re: [Qemu-devel] [PATCH v6 07/21] hbitmap: add hbitmap_merge


From: Max Reitz
Subject: Re: [Qemu-devel] [PATCH v6 07/21] hbitmap: add hbitmap_merge
Date: Wed, 22 Apr 2015 18:22:55 +0200
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0

On 18.04.2015 01:49, 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>
---
  include/qemu/hbitmap.h | 13 +++++++++++++
  util/hbitmap.c         | 33 +++++++++++++++++++++++++++++++++
  2 files changed, 46 insertions(+)

Reviewed-by: Max Reitz <address@hidden>



reply via email to

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