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: 2683 bytes --]

On Fri, Sep 11, 2015 at 02:43:43PM +0200, Paolo Bonzini wrote:
> 
> 
> On 10/09/2015 08:28, David Gibson 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.
> 
> That must consume quite some memory... I would guess 1K per object.

So, Bharata was right, it's only ~32k objects even for maxmem=4T.  I'm
not quite sure how I messed up my arithmetic there.

But still, yeah, it's a lot of objects :/.  Medium term I think we
should avoid creating so many objects for the connectors.  I'm
thinking a "connector array" object that handles a whole range of
connector indices them with a single QOM object should be possible.

> > 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.
> > 
> > For the specific case of DR connectors, we already have a sufficiently
> > unique index, so we don't need to use the [*] special behaviour.  That lets
> > us reduce the total time for creating the DR objects from O(n^3) to O(n^2).
> > 
> > O(n^2) is still kind of crappy, but it's enough to reduce the startup time
> > of qemu with maxmem=2T from ~20 minutes to ~4 seconds.
> 
> Thanks, I agree that even O(n^2) is crappy.  We need to add a hash table
> for properties, so that [*] is O(n^2) and the optimized case is
> O(n).

Right, so I had the impression that QOM isn't really built for
handling thousands of objects under one parent.  I don't have a wide
enough view to know if that's a reasonable goal for it ever to handle
well.  Using a hash table at every node might be pretty expensive in
memory for nodes with only a handful of children.

-- 
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 --]