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

[Paolo Bonzini <pbonzini@redhat.com>]

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.

> 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).

Paolo

> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
> Cc: Bharata B Rao <bharata@linux.vnet.ibm.com>
> ---
>  hw/ppc/spapr_drc.c | 4 +++-
>  1 file changed, 3 insertions(+), 1 deletion(-)
> 
> diff --git a/hw/ppc/spapr_drc.c b/hw/ppc/spapr_drc.c
> index c1f664f..4cf3a9b 100644
> --- a/hw/ppc/spapr_drc.c
> +++ b/hw/ppc/spapr_drc.c
> @@ -463,14 +463,16 @@ sPAPRDRConnector *spapr_dr_connector_new(Object *owner,
>  {
>      sPAPRDRConnector *drc =
>          SPAPR_DR_CONNECTOR(object_new(TYPE_SPAPR_DR_CONNECTOR));
> +    char *prop_name = g_strdup_printf("dr-connector[%"PRIu32"]", id);
>  
>      g_assert(type);
>  
>      drc->type = type;
>      drc->id = id;
>      drc->owner = owner;
> -    object_property_add_child(owner, "dr-connector[*]", OBJECT(drc), NULL);
> +    object_property_add_child(owner, prop_name, OBJECT(drc), NULL);
>      object_property_set_bool(OBJECT(drc), true, "realized", NULL);
> +    g_free(prop_name);
>  
>      /* human-readable name for a DRC to encode into the DT
>       * description. this is mainly only used within a guest in place
>