Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement

["Daniel P. Berrange" <berrange@redhat.com>]

On Tue, Jul 14, 2015 at 12:39:01PM +0300, Pavel Fedin wrote:
> Avoid repetitive lookup of every property in array starting from 0 by adding
> one more property which caches last used index. Every time an array is
> expanded the index is picked up from this cache.
> 
> The property is a uint32_t and its name is name of the array plus '#'
> ('name#'). It has getter function in order to allow to inspect it from
> within monitor.
> 
> Another optimization includes avoiding reallocation of 'full_name' every
> iteration. Instead, name_no_array buffer is extended and reused.
> 
> Signed-off-by: Pavel Fedin <p.fedin@samsung.com>
> Reviewed-by: Peter Crosthwaite <peter.crosthwaite@xilinx.com>

IIUC, the performance problem with object_property_add is caused by
the fact that every time we add a property we have to do a linear
search over every existing property running strcmp to see if the
new property already exists.


    QTAILQ_FOREACH(prop, &obj->properties, node) {
        if (strcmp(prop->name, name) == 0) {
            error_setg(errp, "attempt to add duplicate property '%s'"
                       " to object (type '%s')", name,
                       object_get_typename(obj));
            return NULL;
        }
    }

This is compounded by the array expansion code which does a linear
search trying index 0, then index 1, etc, until it is able to add
the property without error. So this code becomes O(n^2) complexity.

Your change is avoiding the problemm in array expansion code by
storing the max index, but is still leaving the linear search in
check for duplicate property name. So the code is still O(n) on
the number of properties. Better, but still poor.

I seems that we should also look at changing the 'properties'
field to use a hash table instead of linked list, so that we
have O(1) access in all the methods which add/remove/lookup
properties.

> ---
>  qom/object.c | 51 ++++++++++++++++++++++++++++++++++++++++-----------
>  1 file changed, 40 insertions(+), 11 deletions(-)
> 
> diff --git a/qom/object.c b/qom/object.c
> index ba63777..5820df2 100644
> --- a/qom/object.c
> +++ b/qom/object.c
> @@ -10,6 +10,8 @@
>   * See the COPYING file in the top-level directory.
>   */
>  
> +#include <glib/gprintf.h>
> +
>  #include "qom/object.h"
>  #include "qom/object_interfaces.h"
>  #include "qemu-common.h"
> @@ -862,6 +864,14 @@ object_property_add_single(Object *obj, const char *name, const char *type,
>      return prop;
>  }
>  
> +static void
> +property_get_uint32_opaque(Object *obj, Visitor *v, void *opaque,
> +                           const char *name, Error **errp)
> +{
> +    uint32_t value = (uintptr_t)opaque;
> +    visit_type_uint32(v, &value, name, errp);
> +}
> +
>  ObjectProperty *
>  object_property_add(Object *obj, const char *name, const char *type,
>                      ObjectPropertyAccessor *get,
> @@ -871,27 +881,46 @@ object_property_add(Object *obj, const char *name, const char *type,
>  {
>      size_t name_len = strlen(name);
>      char *name_no_array;
> -    ObjectProperty *ret;
> -    int i;
> +    ObjectProperty *ret, *count;
> +    uintptr_t i;
>  
>      if (name_len < 3 || memcmp(&name[name_len - 3], "[*]", 4)) {
>          return object_property_add_single(obj, name, type,
>                                            get, set, release, opaque, errp);
>      }
>  
> -    name_no_array = g_strdup(name);
> -
> -    name_no_array[name_len - 3] = '\0';
> -    for (i = 0; ; ++i) {
> -        char *full_name = g_strdup_printf("%s[%d]", name_no_array, i);
> -
> -        ret = object_property_add(obj, full_name, type, get, set,
> -                                  release, opaque, NULL);
> -        g_free(full_name);
> +    /* 20 characters for maximum possible uintptr_t (64-bit) */
> +    name_no_array = g_malloc(name_len + 20);
> +    name_len -= 3;
> +    memcpy(name_no_array, name, name_len);
> +
> +    name_no_array[name_len] = '#';
> +    name_no_array[name_len + 1] = '\0';

This code is really uneccessarily convoluted in trying to reuse
the same memory allocation for two different strings

You can rewrite this more clearly as:

  name_no_array = g_strndup_printf("%.s#", name_len - 3, name);


> +    count = object_property_find(obj, name_no_array, NULL);
> +    if (count == NULL) {
> +        /* This is very similar to object_property_add_uint32_ptr(), but:
> +         * - Returns pointer
> +         * - Will not recurse here, avoiding one condition check
> +         * - Allows us to use 'opaque' pointer itself as a storage, because
> +         *   we want to store only a single integer which should never be
> +         *   modified from outside.
> +         */
> +        count = object_property_add_single(obj, name_no_array, "uint32",
> +                                           property_get_uint32_opaque, NULL,
> +                                           NULL, NULL, &error_abort);
> +    }
> +
> +    for (i = (uintptr_t)count->opaque; ; ++i) {
> +        g_sprintf(&name_no_array[name_len], "[%zu]", i);

And here you could use

   g_strdup_printf("%.s[%zu]", name_len - 3, name, i)

avoiding the inherantly dangerious sprintf function

> +
> +        ret = object_property_add_single(obj, name_no_array, type, get, set,
> +                                         release, opaque, NULL);
>          if (ret) {
>              break;
>          }
>      }
> +
> +    count->opaque = (void *)i;
>      g_free(name_no_array);
>      return ret;

Regards,
Daniel
-- 
|: http://berrange.com      -o-    http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org              -o-             http://virt-manager.org :|
|: http://autobuild.org       -o-         http://search.cpan.org/~danberr/ :|
|: http://entangle-photo.org       -o-       http://live.gnome.org/gtk-vnc :|