From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:56990) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YC9WD-00022z-5E for qemu-devel@nongnu.org; Fri, 16 Jan 2015 11:13:06 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YC9W8-0003pj-2O for qemu-devel@nongnu.org; Fri, 16 Jan 2015 11:13:05 -0500 Received: from mx1.redhat.com ([209.132.183.28]:36381) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YC9W7-0003pX-Ql for qemu-devel@nongnu.org; Fri, 16 Jan 2015 11:12:59 -0500 Message-ID: <54B93888.9070209@redhat.com> Date: Fri, 16 Jan 2015 11:12:56 -0500 From: Max Reitz MIME-Version: 1.0 References: <1421080265-2228-1-git-send-email-jsnow@redhat.com> <1421080265-2228-7-git-send-email-jsnow@redhat.com> In-Reply-To: <1421080265-2228-7-git-send-email-jsnow@redhat.com> Content-Type: text/plain; charset=iso-8859-15; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH v11 06/13] hbitmap: add hbitmap_merge List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: John Snow , qemu-devel@nongnu.org Cc: kwolf@redhat.com, famz@redhat.com, armbru@redhat.com, vsementsov@parallels.com, stefanha@redhat.com On 2015-01-12 at 11:30, John Snow wrote: > We add a bitmap merge operation to assist in error cases > where we wish to combine two bitmaps together. > > 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) ~= 1.01587 * bits > > 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. > > We present the simpler solution first, and we can refine it later > if needed. > > Signed-off-by: John Snow > --- > include/qemu/hbitmap.h | 11 +++++++++++ > util/hbitmap.c | 28 ++++++++++++++++++++++++++++ > 2 files changed, 39 insertions(+) Reviewed-by: Max Reitz