This is an archived copy of the Xen.org mailing list, which we have preserved to ensure that existing links to archives are not broken. The live archive, which contains the latest emails, can be found at http://lists.xen.org/
Home Products Support Community News


[Xen-devel] Xmalloc worst case performance and bad corner cases

To: "Xen-Devel (E-mail)" <xen-devel@xxxxxxxxxxxxxxxxxxx>
Subject: [Xen-devel] Xmalloc worst case performance and bad corner cases
From: Dan Magenheimer <dan.magenheimer@xxxxxxxxxx>
Date: Fri, 26 Sep 2008 22:34:53 +0000 (GMT)
Delivery-date: Fri, 26 Sep 2008 15:36:37 -0700
Envelope-to: www-data@xxxxxxxxxxxxxxxxxxx
List-help: <mailto:xen-devel-request@lists.xensource.com?subject=help>
List-id: Xen developer discussion <xen-devel.lists.xensource.com>
List-post: <mailto:xen-devel@lists.xensource.com>
List-subscribe: <http://lists.xensource.com/mailman/listinfo/xen-devel>, <mailto:xen-devel-request@lists.xensource.com?subject=subscribe>
List-unsubscribe: <http://lists.xensource.com/mailman/listinfo/xen-devel>, <mailto:xen-devel-request@lists.xensource.com?subject=unsubscribe>
Sender: xen-devel-bounces@xxxxxxxxxxxxxxxxxxx
It appears that if xmalloc (Xen heap allocator) is
used for a long sequence of n memory requests with
the size of each request greater than a half-page,
but less than a page, performance will be O(n**2).


And because of space for a header and alignment,
the interval is actually from slightly less than
a half-page to slightly less than a full-page...
and xmalloc of a few bytes less than a full-page will
actually end up allocating two full pages!


(Yes, I realize that xmalloc'ing a "long sequence"
from Xen heap is not a good idea because the Xen
heap is rather small, but I currently have a veneer
using the xmalloc/xfree routines on top of the
domain heap, and "future versions" of 64-bit combined
heap allocation may reuse the existing allocation


Xen-devel mailing list

<Prev in Thread] Current Thread [Next in Thread>