From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([208.118.235.92]:60962) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TR29Q-0006rU-UF for qemu-devel@nongnu.org; Wed, 24 Oct 2012 10:41:50 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TR29K-0008Ra-Qn for qemu-devel@nongnu.org; Wed, 24 Oct 2012 10:41:44 -0400 Received: from mx1.redhat.com ([209.132.183.28]:23725) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TR29K-0008RT-Id for qemu-devel@nongnu.org; Wed, 24 Oct 2012 10:41:38 -0400 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id q9OEfbf9011096 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Wed, 24 Oct 2012 10:41:37 -0400 Message-ID: <5087FE1F.9090806@redhat.com> Date: Wed, 24 Oct 2012 16:41:35 +0200 From: Kevin Wolf MIME-Version: 1.0 References: <1348675011-8794-1-git-send-email-pbonzini@redhat.com> <1348675011-8794-36-git-send-email-pbonzini@redhat.com> In-Reply-To: <1348675011-8794-36-git-send-email-pbonzini@redhat.com> Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH v2 35/45] add hierarchical bitmap data type and test cases List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Paolo Bonzini Cc: jcody@redhat.com, qemu-devel@nongnu.org Am 26.09.2012 17:56, 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 > Signed-off-by: Paolo Bonzini I'll continue (or actually only start really) reviewing this tomorrow, but let me ask one question now so that I won't forget it: > +struct HBitmapIter { > + const HBitmap *hb; > + > + /* Copied from hb for access in the inline functions (hb is opaque). */ > + int granularity; > + > + /* Entry offset into the last-level array of longs. */ > + size_t pos; Other places, for example HBitmap.size/count and the local pos variable in hbitmap_iter_skip_words(), use uint64_t. Why is size_t here enough? > + > + /* The currently-active path in the tree. Each item of cur[i] stores > + * the bits (i.e. the subtrees) yet to be processed under that node. > + */ > + unsigned long cur[HBITMAP_LEVELS]; > +}; Kevin