[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v6 07/21] hbitmap: add hbitmap_merge
From: |
Eric Blake |
Subject: |
Re: [Qemu-devel] [PATCH v6 07/21] hbitmap: add hbitmap_merge |
Date: |
Wed, 22 Apr 2015 16:00:01 -0600 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0 |
On 04/17/2015 05:49 PM, 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: Eric Blake <address@hidden>
--
Eric Blake eblake redhat com +1-919-301-3266
Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
- [Qemu-devel] [PATCH v6 05/21] block: Introduce bdrv_dirty_bitmap_granularity(), (continued)
- [Qemu-devel] [PATCH v6 05/21] block: Introduce bdrv_dirty_bitmap_granularity(), John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 01/21] docs: incremental backup documentation, John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 02/21] qapi: Add optional field "name" to block dirty bitmap, John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 04/21] qmp: Add block-dirty-bitmap-add and block-dirty-bitmap-remove, John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 06/21] hbitmap: cache array lengths, John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 07/21] hbitmap: add hbitmap_merge, John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 08/21] block: Add bitmap disabled status, John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 13/21] block: add BdrvDirtyBitmap documentation, John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 12/21] qmp: Add dirty bitmap status field in query-block, John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 11/21] qmp: add block-dirty-bitmap-clear, John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 09/21] block: Add bitmap successors, John Snow, 2015/04/17
- [Qemu-devel] [PATCH v6 10/21] qmp: Add support of "dirty-bitmap" sync mode for drive-backup, John Snow, 2015/04/17