Re: [Qemu-devel] [RFC PATCH] spapr: Reduce creation of LMB DR connectors from O(n^3) to O(n^2)

[David Gibson <david@gibson.dropbear.id.au>]

[-- Attachment #1: Type: text/plain, Size: 1619 bytes --]

On Thu, Sep 10, 2015 at 01:42:57AM -0700, Peter Crosthwaite wrote:
> On Wed, Sep 9, 2015 at 11:28 PM, David Gibson
> <david@gibson.dropbear.id.au> wrote:
> > The dynamic reconfiguration (hotplug) code for the pseries machine type
> > uses a "DR connector" QOM object for each resource it will be possible
> > to hotplug.  Each of these is added to its owner using
> >     object_property_add_child(owner, "dr-connector[*], ...);
> >
> 
> > This works ok for most cases, but gets ugly when allowing large amounts of
> > hotplugged RAM.  For RAM, there's a DR connector object for every 256MB of
> > potential memory.  So if maxmem=2T, for example, there are >250,000 objects
> > under the same parent.
> >
> > The QOM interfaces aren't really designed for this.  In particular
> > object_property_add() has O(n^2) time complexity (in the number of existing
> > children) for the [*] case.  First it has a linear search through array
> > indices to find a free slot, each of which is attempted to a recursive call
> > to object_property_add() with a specific [N].  Those calls are O(n) because
> > there's a linear search through all properties to check for duplicates.
> >
> 
> Does this help? I think it's already queued:
> 
>
>http://lists.nongnu.org/archive/html/qemu-devel/2015-07/msg05790.html


It doesn't help our case; it's basically a fix for a different
instance of the same problem.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #2: Type: application/pgp-signature, Size: 819 bytes --]