From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:60287) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yl2h1-0000tA-Kv for qemu-devel@nongnu.org; Wed, 22 Apr 2015 18:00:31 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Yl2h0-00036e-IQ for qemu-devel@nongnu.org; Wed, 22 Apr 2015 18:00:27 -0400 Message-ID: <553819E1.4030404@redhat.com> Date: Wed, 22 Apr 2015 16:00:01 -0600 From: Eric Blake MIME-Version: 1.0 References: <1429314609-29776-1-git-send-email-jsnow@redhat.com> <1429314609-29776-8-git-send-email-jsnow@redhat.com> In-Reply-To: <1429314609-29776-8-git-send-email-jsnow@redhat.com> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="CL5H6u7bLeoFhxFhL2MMmQ2x43ANmCEXv" Subject: Re: [Qemu-devel] [PATCH v6 07/21] hbitmap: add hbitmap_merge List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: John Snow , qemu-block@nongnu.org Cc: kwolf@redhat.com, famz@redhat.com, qemu-devel@nongnu.org, armbru@redhat.com, vsementsov@parallels.com, stefanha@redhat.com, mreitz@redhat.com This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --CL5H6u7bLeoFhxFhL2MMmQ2x43ANmCEXv Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable 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. >=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 > --- > include/qemu/hbitmap.h | 13 +++++++++++++ > util/hbitmap.c | 33 +++++++++++++++++++++++++++++++++ > 2 files changed, 46 insertions(+) Reviewed-by: Eric Blake --=20 Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --CL5H6u7bLeoFhxFhL2MMmQ2x43ANmCEXv Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBCAAGBQJVOBnhAAoJEKeha0olJ0Nq3qsH/3W0IMa5TtoEEZ5lGC3HCV9Y w4NNRdkqvmE14oQkmIF14mnYNMrrxUDBJ/e8AHHHHRo4UE2zmikIMvWQ0agYD6cw 8h07Zq0kS9xh0KIrEc1DDF3mp12Y4xpf6vWvj0bat9DXPORprJh15fDjP594WOD1 1wRW3kIzTHmQttexa1NKxEd3bzQVQYIo5ZC8j8amKEJkT0H3gtUrJI6bFfnfmdBj 0hoBMTYvREJHWcj+U6XleiqeaMdnAkCd/zM5Ijw6wv1tpItJOfI3koZQXa2LZbjv oABcGN8GNU8k6svYbtJaB11u+Z9CNnw1y2kgsymQ30SXK2YQ7H+0sMrKxdMoSC0= =WcQk -----END PGP SIGNATURE----- --CL5H6u7bLeoFhxFhL2MMmQ2x43ANmCEXv--