[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v2 02/12] add hierarchical bitmap data type and
From: |
Kevin Wolf |
Subject: |
Re: [Qemu-devel] [PATCH v2 02/12] add hierarchical bitmap data type and test cases |
Date: |
Fri, 18 Jan 2013 14:21:03 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:13.0) Gecko/20120605 Thunderbird/13.0 |
Am 16.01.2013 18:31, schrieb Paolo Bonzini:
> HBitmaps provides an array of bits. The bits are stored as usual in an
> array of unsigned longs, but HBitmap is also optimized to provide fast
> iteration over set bits; going from one bit to the next is O(logB n)
> worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
> that the number of levels is in fact fixed.
>
> In order to do this, it stacks multiple bitmaps with progressively coarser
> granularity; in all levels except the last, bit N is set iff the N-th
> unsigned long is nonzero in the immediately next level. When iteration
> completes on the last level it can examine the 2nd-last level to quickly
> skip entire words, and even do so recursively to skip blocks of 64 words or
> powers thereof (32 on 32-bit machines).
>
> Given an index in the bitmap, it can be split in group of bits like
> this (for the 64-bit case):
>
> bits 0-57 => word in the last bitmap | bits 58-63 => bit in the word
> bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
> bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word
>
> So it is easy to move up simply by shifting the index right by
> log2(BITS_PER_LONG) bits. To move down, you shift the index left
> similarly, and add the word index within the group. Iteration uses
> ffs (find first set bit) to find the next word to examine; this
> operation can be done in constant time in most current architectures.
>
> Setting or clearing a range of m bits on all levels, the work to perform
> is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.
>
> When iterating on a bitmap, each bit (on any level) is only visited
> once. Hence, The total cost of visiting a bitmap with m bits in it is
> the number of bits that are set in all bitmaps. Unless the bitmap is
> extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
> cost of advancing from one bit to the next is usually constant.
>
> Reviewed-by: Laszlo Ersek <address@hidden>
> Signed-off-by: Paolo Bonzini <address@hidden>
This patch contains a few lines > 80 characters.
I think it looks good otherwise.
Kevin
- [Qemu-devel] [PATCH v2 00/12] Drive mirroring performance improvements, Paolo Bonzini, 2013/01/16
- [Qemu-devel] [PATCH v2 01/12] host-utils: add ffsl, Paolo Bonzini, 2013/01/16
- [Qemu-devel] [PATCH v2 03/12] block: implement dirty bitmap using HBitmap, Paolo Bonzini, 2013/01/16
- [Qemu-devel] [PATCH v2 02/12] add hierarchical bitmap data type and test cases, Paolo Bonzini, 2013/01/16
- [Qemu-devel] [PATCH v2 04/12] block: make round_to_clusters public, Paolo Bonzini, 2013/01/16
- [Qemu-devel] [PATCH v2 05/12] mirror: perform COW if the cluster size is bigger than the granularity, Paolo Bonzini, 2013/01/16
- Re: [Qemu-devel] [PATCH v2 05/12] mirror: perform COW if the cluster size is bigger than the granularity, Kevin Wolf, 2013/01/18
- Re: [Qemu-devel] [PATCH v2 05/12] mirror: perform COW if the cluster size is bigger than the granularity, Paolo Bonzini, 2013/01/18
- Re: [Qemu-devel] [PATCH v2 05/12] mirror: perform COW if the cluster size is bigger than the granularity, Kevin Wolf, 2013/01/18
- Re: [Qemu-devel] [PATCH v2 05/12] mirror: perform COW if the cluster size is bigger than the granularity, Paolo Bonzini, 2013/01/18
- Re: [Qemu-devel] [PATCH v2 05/12] mirror: perform COW if the cluster size is bigger than the granularity, Kevin Wolf, 2013/01/21
- Re: [Qemu-devel] [PATCH v2 05/12] mirror: perform COW if the cluster size is bigger than the granularity, Paolo Bonzini, 2013/01/21
- Re: [Qemu-devel] [PATCH v2 05/12] mirror: perform COW if the cluster size is bigger than the granularity, Stefan Hajnoczi, 2013/01/22
- Re: [Qemu-devel] [PATCH v2 05/12] mirror: perform COW if the cluster size is bigger than the granularity, Paolo Bonzini, 2013/01/21