From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from [140.186.70.92] (port=53635 helo=eggs.gnu.org)
	by lists.gnu.org with esmtp (Exim 4.43) id 1PNeCI-0002OE-NT
	for qemu-devel@nongnu.org; Tue, 30 Nov 2010 23:22:06 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
	(envelope-from <quintela@redhat.com>) id 1PNT86-0004Uu-0k
	for qemu-devel@nongnu.org; Tue, 30 Nov 2010 11:32:35 -0500
Received: from mx1.redhat.com ([209.132.183.28]:53493)
	by eggs.gnu.org with esmtp (Exim 4.71)
	(envelope-from <quintela@redhat.com>) id 1PNT85-0004RA-Kc
	for qemu-devel@nongnu.org; Tue, 30 Nov 2010 11:32:33 -0500
From: Juan Quintela <quintela@redhat.com>
In-Reply-To: <20101130161032.GF20536@redhat.com> (Michael S. Tsirkin's message
	of "Tue, 30 Nov 2010 18:10:32 +0200")
References: <cover.1290552026.git.quintela@redhat.com>
	<a12e21918775e0c0ae23c373be1e35060b52031b.1290552026.git.quintela@redhat.com>
	<20101124104035.GB23493@redhat.com> <m3wro3dmdy.fsf@trasno.mitica>
	<4CF46012.2060804@codemonkey.ws> <m3hbezvxcw.fsf@trasno.mitica>
	<4CF50410.3080305@codemonkey.ws> <m31v62vmyu.fsf@trasno.mitica>
	<20101130161032.GF20536@redhat.com>
Date: Tue, 30 Nov 2010 17:32:22 +0100
Message-ID: <m3lj4au609.fsf@trasno.mitica>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Subject: [Qemu-devel] Re: [PATCH 02/10] Add buffered_file_internal constant
List-Id: qemu-devel.nongnu.org
List-Unsubscribe: <http://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=unsubscribe>
List-Archive: <http://lists.nongnu.org/archive/html/qemu-devel>
List-Post: <mailto:qemu-devel@nongnu.org>
List-Help: <mailto:qemu-devel-request@nongnu.org?subject=help>
List-Subscribe: <http://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=subscribe>
To: "Michael S. Tsirkin" <mst@redhat.com>
Cc: qemu-devel@nongnu.org

"Michael S. Tsirkin" <mst@redhat.com> wrote:
> On Tue, Nov 30, 2010 at 04:40:41PM +0100, Juan Quintela wrote:
>> Basically our bitmap handling code is "exponential" on memory size,
>
> I didn't realize this. What makes it exponential?

Well, 1st of all, it is "exponential" as you measure it.

stalls by default are:

1-2GB: milliseconds
2-4GB: 100-200ms
4-8GB: 1s
64GB: 59s
400GB: 24m (yes, minutes)

That sounds really exponential.

Now the other thing is the cache size.

with 64GB of RAM, we basically have a 16MB bitmap size, i.e. we blow the
cache each time that we run ram_save_live().

This is one of the reasons why I don't want to walk the bitmap on
ram_save_remaining().

ram_save_remaining() is linear with memory size (previous my changes).
ram_save_live is also linear on the memory size, so we are in a worse
case of n^n  (notice that this is the worst case, we normally do much
better n^2, n^3 or so).

Add to this that we are blowing the caches with big amounts of memory
(we don't do witch smaller sizes), and you can see that our behaviour is
clearly exponential.

As I need to fix them, I will work on them today/tomorrow.

Later, Juan.