From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:38087) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YOlSg-00051o-QD for qemu-devel@nongnu.org; Fri, 20 Feb 2015 06:09:35 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YOlSf-0005tz-T3 for qemu-devel@nongnu.org; Fri, 20 Feb 2015 06:09:34 -0500 Received: from mx1.redhat.com ([209.132.183.28]:35317) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YOlSf-0005tk-JN for qemu-devel@nongnu.org; Fri, 20 Feb 2015 06:09:33 -0500 Date: Fri, 20 Feb 2015 09:34:41 +0000 From: Stefan Hajnoczi Message-ID: <20150220093441.GB3867@stefanha-thinkpad.redhat.com> References: <1423865338-8576-1-git-send-email-jsnow@redhat.com> <1423865338-8576-6-git-send-email-jsnow@redhat.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="VrqPEDrXMn8OVzN4" Content-Disposition: inline In-Reply-To: <1423865338-8576-6-git-send-email-jsnow@redhat.com> Subject: Re: [Qemu-devel] [PATCH v13 05/17] hbitmap: add hbitmap_merge List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: John Snow Cc: kwolf@redhat.com, famz@redhat.com, armbru@redhat.com, qemu-devel@nongnu.org, vsementsov@parallels.com, mreitz@redhat.com --VrqPEDrXMn8OVzN4 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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. >=20 > 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) ~=3D 1.01587 * bits >=20 > 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. >=20 > We present the simpler solution first, and we can refine it later > if needed. >=20 > Signed-off-by: John Snow > Reviewed-by: Max Reitz > --- > include/qemu/hbitmap.h | 11 +++++++++++ > util/hbitmap.c | 32 ++++++++++++++++++++++++++++++++ > 2 files changed, 43 insertions(+) Reviewed-by: Stefan Hajnoczi --VrqPEDrXMn8OVzN4 Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQEcBAEBAgAGBQJU5v+xAAoJEJykq7OBq3PIlI0H/2OE+oz0QF8rWgl7Wnz1ha3I xZMC/AlyEq9hsOGHJkGbXFb97b+HlY44Lz8RH0SDPzhzSj7wJliGecnqPsJMHkAO Nzja1pUsmtGuD+NRWCj6Ip6YHrFQr7+GLqyznPFwLmv/nlrvIgsgfBQ86XS6unDz TEOka9FPDeYAHsqKYYbnWZpx/HMq1fsK4eguBtd8f6sKlqfuGU2kMUOnbVO82Uhw YcIKpHA8Kq9ryuXyzR2hOItFSPGk9yUK5qOkyTV06gG9421i16NIHIX8ZpO9Br7x giVxsEftVS7vPFISqMB9jpqRp2yER3gE8HGHXuXtHG8xqc3cN4RHFs0XmCWMx6Y= =wPvd -----END PGP SIGNATURE----- --VrqPEDrXMn8OVzN4--