From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:44033) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YlHU6-0004Ha-1T for qemu-devel@nongnu.org; Thu, 23 Apr 2015 09:48:06 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YlHU5-00023U-5K for qemu-devel@nongnu.org; Thu, 23 Apr 2015 09:48:05 -0400 Date: Thu, 23 Apr 2015 14:40:00 +0100 From: Stefan Hajnoczi Message-ID: <20150423134000.GE20959@stefanha-thinkpad.redhat.com> References: <1429314609-29776-1-git-send-email-jsnow@redhat.com> <1429314609-29776-8-git-send-email-jsnow@redhat.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="10jrOL3x2xqLmOsH" Content-Disposition: inline In-Reply-To: <1429314609-29776-8-git-send-email-jsnow@redhat.com> 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 Cc: kwolf@redhat.com, famz@redhat.com, qemu-block@nongnu.org, qemu-devel@nongnu.org, armbru@redhat.com, vsementsov@parallels.com, stefanha@redhat.com, mreitz@redhat.com --10jrOL3x2xqLmOsH Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, Apr 17, 2015 at 07:49:55PM -0400, 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: Stefan Hajnoczi --10jrOL3x2xqLmOsH Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQEcBAEBAgAGBQJVOPYwAAoJEJykq7OBq3PIoawH/Rgokp7CRCGKgCTnQAP3KqwM BCClljJPbfy7wPzr2qpwnJysVsYDou9yMLWly5pe9pzPaIk5Y/qwhh18zkDuwwzu kit0d9Ofpczd4KtRHn/9OElEuRVPSMd5TTF4AWFkQkdndCQQqDo+YClps6hBGPjr DxA/M0czWSZy+diB+njPE8zEGxxPv6xLXYHfXZcQWDWznmCttlC0TdtJEqMBxMsN QbfNJfy8/iuJh30tXir3YZNN5nG7lNXsOx+7OYYNdyWi7TPb4h/N9ThoG5dcUQMn FOBHBQbipEymNgbeLHkRboq2+iEhUi1enjbgYcP2tWGh6djzTgqHV9YZdHLSlrA= =xUZD -----END PGP SIGNATURE----- --10jrOL3x2xqLmOsH--