Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
On 28/07/2015 08:45, Pavel Fedin wrote: > 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? Just worry about 3 and 4, they are the big offenders. Paolo
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
> > 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. Ok ok ok... 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? Kind regards, Pavel Fedin Expert Engineer Samsung Electronics Research center Russia
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
On 27/07/2015 17:19, Pavel Fedin wrote: >>> 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. But IIUC qdev_init_gpio_in/out (the non-named variants) should only be called once. So if it breaks it's a feature. Paolo > So, > just for better safety, i decided to fix the mechanism itself instead > of changing use cases.
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
Hello! > 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. Kind regards, Pavel Fedin Expert Engineer Samsung Electronics Research center Russia
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
On 27/07/2015 17:06, Paolo Bonzini wrote:
>
>
> On 27/07/2015 16:57, Andreas Färber wrote:
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:
>
> diff --git a/hw/core/qdev.c b/hw/core/qdev.c
> index b2f404a..19bfee1 100644
> --- a/hw/core/qdev.c
> +++ b/hw/core/qdev.c
> @@ -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;
> }
>
> ?
... and the same in qdev_init_gpio_out_named.
Paolo
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
On 27/07/2015 16:57, Andreas Färber wrote:
>> > 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:
diff --git a/hw/core/qdev.c b/hw/core/qdev.c
index b2f404a..19bfee1 100644
--- a/hw/core/qdev.c
+++ b/hw/core/qdev.c
@@ -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;
}
?
Paolo
> 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.
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
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 -- SUSE Linux GmbH, Maxfeldstr. 5, 90409 Nürnberg, Germany GF: Felix Imendörffer, Jane Smithard, Dilip Upmanyu, Graham Norton; HRB 21284 (AG Nürnberg)
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
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
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
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
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
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
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
On Mon, Jul 27, 2015 at 03:03:26PM +0200, Markus Armbruster wrote:
> Pavel Fedin 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
--
|: 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 :|
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
Pavel Fedin 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
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement
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
> Reviewed-by: Peter Crosthwaite
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
> +
> #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
[Qemu-devel] [PATCH 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
Reviewed-by: Peter Crosthwaite
---
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
+
#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';
+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);
+
+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;
}
--
1.9.5.msysgit.0
