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 <[email protected]>

Reviewed-by Peter Crosthwaite <[email protected]>

---
 qom/object.c | 51 ++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 40 insertions(+), 11 deletions(-)

qom/object.c +12 -8

index ba63777..5820df2 100644
@@ -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);
-

qom/object.c +6 -0

+    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

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.

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.

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.

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.

Quoted 7 lines · Pavel Fedin

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

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,

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

Quoted 2 lines

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.

Quoted 1 line

Quoted 1 line

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.

Quoted 3 lines · Andreas Färber

Quoted 1 line

Quoted 1 line

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.

Yes, I agree -max is better.

I'm just asking myself whether this is really necessary. Is the automagic [*] really needed in this case? Can it just do:

hw/core/qdev.c +3 -3

index b2f404a..19bfee1 100644
@@ -415,19 +415,19 @@ static NamedGPIOList *qdev_get_named_gpio_list(DeviceState *dev,
 void qdev_init_gpio_in_named(DeviceState *dev, qemu_irq_handler handler,
                              const char *name, int n)
 {
-    int i;
+    int i, j;
     NamedGPIOList *gpio_list = qdev_get_named_gpio_list(dev, name);
-    char *propname = g_strdup_printf("%s[*]", name ? name : "unnamed-gpio-in");
 
     assert(gpio_list->num_out == 0 || !name);
     gpio_list->in = qemu_extend_irqs(gpio_list->in, gpio_list->num_in, handler,
                                      dev, n);
 
     for (i = gpio_list->num_in; i < gpio_list->num_in + n; i++) {
+        char *propname = g_strdup_printf("%s[%d]", name ? name : "unnamed-gpio-in", j++);
         object_property_add_child(OBJECT(dev), propname,
                                   OBJECT(gpio_list->in[i]), &error_abort);
+        g_free(propname);
     }
-    g_free(propname);
 
     gpio_list->num_in += n;
 }

?

I'm just asking myself whether this is really necessary. Is the automagic [*] really needed in this case?

Quoted 2 lines

Quoted 2 lines

I'm just asking myself whether this is really necessary. Is the automagic [*] really needed in this case?

In this particular case, perhaps, not. However, this automagic is used not only with GPIOs. It is used also with memory regions, as well as with some other places. Also, i thought that there could be some hard to notice problems, when, for example, we first add unnamed-gpio-in[0...1023], then add another 1024 pins, where count again goes from 0 to 1023. And we would get collision and failure, unless we know, that we already have 1024 objects with this name.

So,
just for better safety, i decided to fix the mechanism itself instead of changing use cases.

Quoted 5 lines

Also, i thought that there could be
some hard to notice problems, when, for example, we first add unnamed-gpio-in[0...1023], then add another 1024 pins, where count again goes from 0 to 1023. And we would get collision and failure, unless we know, that we already have 1024 objects with this name.

But IIUC qdev_init_gpio_in/out (the non-named variants) should only be called once. So if it breaks it's a feature.

I can try to reengineer this and see what happens. If it works fine, will such rework be accepted? [*] expansion would still be slow, but we could deprecate it.

I have just done a search of "[*]" across all *.c files, and here is what i came up with:
1. memory_region_init()
2. xlnx_zynqmp_init()
3. qdev_init_gpio_in_named()
4. qdev_init_gpio_out_named()
5. qdev_connect_gpio_out_named()
6. spapr_dr_connector_new()

Cases 2, 3, 4 can be reengineered for sure. The rest - i don't know, however perhaps they are not common cases. I think (1) could also be problematic. How many regions with the same name can we have?

The function originally behaves very badly when adding properties with "[*]" suffix. Normally these are used for numbering IRQ pins. In order to find the correct starting number the function started from zero and checked for duplicates. This takes incredibly long time with large number of CPUs because number of IRQ pins on some architectures (like ARM GICv3) gets multiplied by number of CPUs.

The solution is to add one more property which caches last used index so that duplication check is not repeated thousands of times. Every time an array is expanded the index is picked up from this cache.

The modification decreases qemu startup time with 32 CPUs by a factor of 2 (~10 sec vs ~20 sec).