[v4,2/2] QOM: object_property_add() performance improvement

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>
---
 qom/object.c | 51 ++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 40 insertions(+), 11 deletions(-)

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

Pavel Fedin <p.fedin@samsung.com> writes:

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

Do we really want '#' in property names?  Elsewhere, we require names to
be id_wellformed().  I've long argued for doing that consistently[*],
but QOM still doesn't.

I've always hated "automatic arrayification", not least because it
encodes semantics in property names.  I tried to replace it[**], but
Paolo opposed it.  Which makes him the go-to guy for reviewing anything
that touches it ;-P


[*] http://lists.gnu.org/archive/html/qemu-devel/2014-10/msg00030.html
[**] http://lists.gnu.org/archive/html/qemu-devel/2014-10/msg00030.html

On Mon, Jul 27, 2015 at 03:03:26PM +0200, Markus Armbruster wrote:
> Pavel Fedin <p.fedin@samsung.com> writes:
> 
> > 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.
> 
> Do we really want '#' in property names?  Elsewhere, we require names to
> be id_wellformed().  I've long argued for doing that consistently[*],
> but QOM still doesn't.
> 
> I've always hated "automatic arrayification", not least because it
> encodes semantics in property names.  I tried to replace it[**], but
> Paolo opposed it.  Which makes him the go-to guy for reviewing anything
> that touches it ;-P

Yeah, I think the magic arrayification behaviour is pretty unpleasant.
It feels like a poor hack to deal with fact that we've not got support
for setting non-scalar properties. Since we're representing arrays
implicitly, we have in turned created the performance problem that
we're facing now because we don't explicitly track the size of the
array. Now we're going to add yet more magic properties to deal this :-(
Not to mention the fact that we've no type safety on the array elements
we're storing eg  propname[0] could be an int16, propname[1] could be
a string, and so on with no checking.

Regards,
Daniel

On 27/07/2015 15:23, Daniel P. Berrange wrote:
> It feels like a poor hack to deal with fact that we've not got support
> for setting non-scalar properties. Since we're representing arrays
> implicitly,

See http://lists.gnu.org/archive/html/qemu-devel/2014-10/msg00623.html:

------------------
"Automatic arrayification" isn't about array-valued properties, it's a
convenience feature for creating a bunch of properties with a common
type, accessors and so forth, named in a peculiar way: "foo[0]",
"foo[1]", ...

The feature saves the caller the trouble of generating the names.
That's all there is to it.
------------------

Paolo

Hello!

> Do we really want '#' in property names?  Elsewhere, we require names to
> be id_wellformed().

 I already asked this question to Andreas but got no single reply from him. My initial idea was to leave '[*]' as a suffix for this magic property. He only told that he doesn't like it.
 I am absolutely fine with absolutely anything. Suggest what you like and i'll change it.

Kind regards,
Pavel Fedin
Expert Engineer
Samsung Electronics Research center Russia

Hello!

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

 Yes, exactly. And this linear search gets extremely slow with lots of CPUs multipled by lots of interrupts.

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

 Yes.

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

 Absolutely. This would be different change, but i decided to postpone it until i can upstream this one.

Kind regards,
Pavel Fedin
Expert Engineer
Samsung Electronics Research center Russia

Hi,

Am 27.07.2015 um 16:36 schrieb Pavel Fedin:
>> Do we really want '#' in property names?  Elsewhere, we require names to
>> be id_wellformed().
> 
>  I already asked this question to Andreas but got no single reply from him. My initial idea was to leave '[*]' as a suffix for this magic property. He only told that he doesn't like it.

And I was waiting for replies on your suggestion, as I had concerns
about that '#'.

>  I am absolutely fine with absolutely anything. Suggest what you like and i'll change it.

Paolo suggested ...-count on #qemu, but I would prefer ...-max or so, as
the number could differ when some property gets deleted.

On the other hand, since this is not a user-added property, using a
reserved character such as '#' would avoid clashes with user-added
properties, as long as tools handle accessing that property okay.

Regards,
Andreas