[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v13 05/17] hbitmap: add hbitmap_merge
From: |
Stefan Hajnoczi |
Subject: |
Re: [Qemu-devel] [PATCH v13 05/17] hbitmap: add hbitmap_merge |
Date: |
Fri, 20 Feb 2015 09:34:41 +0000 |
User-agent: |
Mutt/1.5.23 (2014-03-12) |
On Fri, Feb 13, 2015 at 05:08:46PM -0500, 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 | 32 ++++++++++++++++++++++++++++++++
> 2 files changed, 43 insertions(+)
Reviewed-by: Stefan Hajnoczi <address@hidden>
pgpVvF4wfFtN_.pgp
Description: PGP signature
- [Qemu-devel] [PATCH v13 00/17] block: incremental backup series, John Snow, 2015/02/13
- [Qemu-devel] [PATCH v13 04/17] block: Introduce bdrv_dirty_bitmap_granularity(), John Snow, 2015/02/13
- [Qemu-devel] [PATCH v13 01/17] qapi: Add optional field "name" to block dirty bitmap, John Snow, 2015/02/13
- [Qemu-devel] [PATCH v13 02/17] qmp: Ensure consistent granularity type, John Snow, 2015/02/13
- [Qemu-devel] [PATCH v13 05/17] hbitmap: add hbitmap_merge, John Snow, 2015/02/13
- Re: [Qemu-devel] [PATCH v13 05/17] hbitmap: add hbitmap_merge,
Stefan Hajnoczi <=
- [Qemu-devel] [PATCH v13 07/17] block: Add bitmap successors, John Snow, 2015/02/13
- [Qemu-devel] [PATCH v13 09/17] qmp: add block-dirty-bitmap-clear, John Snow, 2015/02/13
- [Qemu-devel] [PATCH v13 06/17] qmp: Add block-dirty-bitmap-enable and block-dirty-bitmap-disable, John Snow, 2015/02/13
- [Qemu-devel] [PATCH v13 03/17] qmp: Add block-dirty-bitmap-add and block-dirty-bitmap-remove, John Snow, 2015/02/13
- [Qemu-devel] [PATCH v13 12/17] block: add BdrvDirtyBitmap documentation, John Snow, 2015/02/13
- [Qemu-devel] [PATCH v13 08/17] qmp: Add support of "dirty-bitmap" sync mode for drive-backup, John Snow, 2015/02/13