From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49407) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZjgPK-0004Wd-0q for qemu-devel@nongnu.org; Wed, 07 Oct 2015 00:32:51 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZjgPI-0002eM-49 for qemu-devel@nongnu.org; Wed, 07 Oct 2015 00:32:49 -0400 Received: from ozlabs.org ([2401:3900:2:1::2]:49057) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZjgPH-0002dY-FX for qemu-devel@nongnu.org; Wed, 07 Oct 2015 00:32:48 -0400 Date: Wed, 7 Oct 2015 10:56:06 +1100 From: David Gibson Message-ID: <20151006235606.GQ3861@voom.fritz.box> References: <016801d10034$6356fe40$2a04fac0$@samsung.com> <5613C659.5070108@redhat.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="QVgWX4+QEldMe/r9" Content-Disposition: inline In-Reply-To: <5613C659.5070108@redhat.com> Subject: Re: [Qemu-devel] [PATCH] qobject: Replace property list with GHashTable List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Laszlo Ersek Cc: David Gibson , Pavel Fedin , qemu-devel@nongnu.org, 'Paolo Bonzini' --QVgWX4+QEldMe/r9 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Tue, Oct 06, 2015 at 03:02:17PM +0200, Laszlo Ersek wrote: > David, >=20 > On 10/06/15 14:41, Pavel Fedin wrote: > > ARM GICv3 systems with large number of CPUs create lots of IRQ pins. Si= nce > > every pin is represented as a property, number of these properties beco= mes > > very large. Every property add first makes sure there's no duplicates. > > Traversing the list becomes very slow, therefore qemu initialization ta= kes > > significant time (several seconds for e. g. 16 CPUs). > >=20 > > This patch replaces list with GHashTable, making lookup very fast. The = only > > drawback is that object_child_foreach() and object_child_foreach_recurs= ive() > > cannot modify their objects during traversal, since GHashTableIter does= not > > have modify-safe version. However, the code seems not to modify objects= via > > these functions. > >=20 > > Signed-off-by: Pavel Fedin > > --- > > include/qom/object.h | 4 +-- > > qmp.c | 8 +++-- > > qom/object.c | 98 +++++++++++++++++++++++---------------------= -------- > > vl.c | 4 ++- > > 4 files changed, 54 insertions(+), 60 deletions(-) >=20 > Shouldn't this help similarly with the problem that 94649d423e worked > around? (Although that patch has standalone merits of course.) Yes it will. The change to hash table would reduce my nasty O(n^3) case to O(n^2) without 94649d423e, and to O(n) with it.. >=20 > Thanks > Laszlo >=20 > > diff --git a/include/qom/object.h b/include/qom/object.h > > index be7280c..b100923 100644 > > --- a/include/qom/object.h > > +++ b/include/qom/object.h > > @@ -345,7 +345,7 @@ typedef struct ObjectProperty > > ObjectPropertyRelease *release; > > void *opaque; > > =20 > > - QTAILQ_ENTRY(ObjectProperty) node; > > + Object *obj; > > } ObjectProperty; > > =20 > > /** > > @@ -405,7 +405,7 @@ struct Object > > /*< private >*/ > > ObjectClass *class; > > ObjectFree *free; > > - QTAILQ_HEAD(, ObjectProperty) properties; > > + GHashTable *properties; > > uint32_t ref; > > Object *parent; > > }; > > diff --git a/qmp.c b/qmp.c > > index 057a7cb..683f427 100644 > > --- a/qmp.c > > +++ b/qmp.c > > @@ -207,6 +207,7 @@ ObjectPropertyInfoList *qmp_qom_list(const char *pa= th, Error **errp) > > Object *obj; > > bool ambiguous =3D false; > > ObjectPropertyInfoList *props =3D NULL; > > + GHashTableIter iter; > > ObjectProperty *prop; > > =20 > > obj =3D object_resolve_path(path, &ambiguous); > > @@ -220,7 +221,8 @@ ObjectPropertyInfoList *qmp_qom_list(const char *pa= th, Error **errp) > > return NULL; > > } > > =20 > > - QTAILQ_FOREACH(prop, &obj->properties, node) { > > + g_hash_table_iter_init(&iter, obj->properties); > > + while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) { > > ObjectPropertyInfoList *entry =3D g_malloc0(sizeof(*entry)); > > =20 > > entry->value =3D g_malloc0(sizeof(ObjectPropertyInfo)); > > @@ -499,6 +501,7 @@ DevicePropertyInfoList *qmp_device_list_properties(= const char *typename, > > { > > ObjectClass *klass; > > Object *obj; > > + GHashTableIter iter; > > ObjectProperty *prop; > > DevicePropertyInfoList *prop_list =3D NULL; > > =20 > > @@ -517,7 +520,8 @@ DevicePropertyInfoList *qmp_device_list_properties(= const char *typename, > > =20 > > obj =3D object_new(typename); > > =20 > > - QTAILQ_FOREACH(prop, &obj->properties, node) { > > + g_hash_table_iter_init(&iter, obj->properties); > > + while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) { > > DevicePropertyInfo *info; > > DevicePropertyInfoList *entry; > > =20 > > diff --git a/qom/object.c b/qom/object.c > > index 4805328..9649243 100644 > > --- a/qom/object.c > > +++ b/qom/object.c > > @@ -326,6 +326,20 @@ static void object_post_init_with_type(Object *obj= , TypeImpl *ti) > > } > > } > > =20 > > +static void property_destroy(gpointer data) > > +{ > > + ObjectProperty *prop =3D data; > > + > > + if (prop->release) { > > + prop->release(prop->obj, prop->name, prop->opaque); > > + } > > + > > + g_free(prop->name); > > + g_free(prop->type); > > + g_free(prop->description); > > + g_free(prop); > > +} > > + > > void object_initialize_with_type(void *data, size_t size, TypeImpl *ty= pe) > > { > > Object *obj =3D data; > > @@ -340,7 +354,8 @@ void object_initialize_with_type(void *data, size_t= size, TypeImpl *type) > > memset(obj, 0, type->instance_size); > > obj->class =3D type->class; > > object_ref(obj); > > - QTAILQ_INIT(&obj->properties); > > + obj->properties =3D g_hash_table_new_full(g_str_hash, g_str_equal, > > + NULL, property_destroy); > > object_init_with_type(obj, type); > > object_post_init_with_type(obj, type); > > } > > @@ -357,40 +372,19 @@ static inline bool object_property_is_child(Objec= tProperty *prop) > > return strstart(prop->type, "child<", NULL); > > } > > =20 > > -static void object_property_del_all(Object *obj) > > +static gboolean object_property_del_child(gpointer key, gpointer value, > > + gpointer child) > > { > > - while (!QTAILQ_EMPTY(&obj->properties)) { > > - ObjectProperty *prop =3D QTAILQ_FIRST(&obj->properties); > > - > > - QTAILQ_REMOVE(&obj->properties, prop, node); > > + ObjectProperty *prop =3D value; > > =20 > > - if (prop->release) { > > - prop->release(obj, prop->name, prop->opaque); > > - } > > - > > - g_free(prop->name); > > - g_free(prop->type); > > - g_free(prop->description); > > - g_free(prop); > > - } > > -} > > - > > -static void object_property_del_child(Object *obj, Object *child, Erro= r **errp) > > -{ > > - ObjectProperty *prop; > > - > > - QTAILQ_FOREACH(prop, &obj->properties, node) { > > - if (object_property_is_child(prop) && prop->opaque =3D=3D chil= d) { > > - object_property_del(obj, prop->name, errp); > > - break; > > - } > > - } > > + return object_property_is_child(prop) && prop->opaque =3D=3D child; > > } > > =20 > > void object_unparent(Object *obj) > > { > > if (obj->parent) { > > - object_property_del_child(obj->parent, obj, NULL); > > + g_hash_table_foreach_remove(obj->properties, > > + object_property_del_child, obj); > > } > > } > > =20 > > @@ -410,7 +404,7 @@ static void object_finalize(void *data) > > Object *obj =3D data; > > TypeImpl *ti =3D obj->class->type; > > =20 > > - object_property_del_all(obj); > > + g_hash_table_unref(obj->properties); > > object_deinit(obj, ti); > > =20 > > g_assert(obj->ref =3D=3D 0); > > @@ -779,10 +773,12 @@ static int do_object_child_foreach(Object *obj, > > int (*fn)(Object *child, void *opaq= ue), > > void *opaque, bool recurse) > > { > > - ObjectProperty *prop, *next; > > + GHashTableIter iter; > > + ObjectProperty *prop; > > int ret =3D 0; > > =20 > > - QTAILQ_FOREACH_SAFE(prop, &obj->properties, node, next) { > > + g_hash_table_iter_init(&iter, obj->properties); > > + while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) { > > if (object_property_is_child(prop)) { > > Object *child =3D prop->opaque; > > =20 > > @@ -879,13 +875,11 @@ object_property_add(Object *obj, const char *name= , const char *type, > > return ret; > > } > > =20 > > - QTAILQ_FOREACH(prop, &obj->properties, node) { > > - if (strcmp(prop->name, name) =3D=3D 0) { > > - error_setg(errp, "attempt to add duplicate property '%s'" > > + if (g_hash_table_contains(obj->properties, name)) { > > + error_setg(errp, "attempt to add duplicate property '%s'" > > " to object (type '%s')", name, > > object_get_typename(obj)); > > - return NULL; > > - } > > + return NULL; > > } > > =20 > > prop =3D g_malloc0(sizeof(*prop)); > > @@ -897,8 +891,9 @@ object_property_add(Object *obj, const char *name, = const char *type, > > prop->set =3D set; > > prop->release =3D release; > > prop->opaque =3D opaque; > > + prop->obj =3D obj; > > =20 > > - QTAILQ_INSERT_TAIL(&obj->properties, prop, node); > > + g_hash_table_insert(obj->properties, prop->name, prop); > > return prop; > > } > > =20 > > @@ -907,10 +902,9 @@ ObjectProperty *object_property_find(Object *obj, = const char *name, > > { > > ObjectProperty *prop; > > =20 > > - QTAILQ_FOREACH(prop, &obj->properties, node) { > > - if (strcmp(prop->name, name) =3D=3D 0) { > > - return prop; > > - } > > + prop =3D g_hash_table_lookup(obj->properties, name); > > + if (prop) { > > + return prop; > > } > > =20 > > error_setg(errp, "Property '.%s' not found", name); > > @@ -919,21 +913,11 @@ ObjectProperty *object_property_find(Object *obj,= const char *name, > > =20 > > void object_property_del(Object *obj, const char *name, Error **errp) > > { > > - ObjectProperty *prop =3D object_property_find(obj, name, errp); > > - if (prop =3D=3D NULL) { > > + if (g_hash_table_remove(obj->properties, name)) { > > return; > > } > > =20 > > - if (prop->release) { > > - prop->release(obj, name, prop->opaque); > > - } > > - > > - QTAILQ_REMOVE(&obj->properties, prop, node); > > - > > - g_free(prop->name); > > - g_free(prop->type); > > - g_free(prop->description); > > - g_free(prop); > > + error_setg(errp, "Property '.%s' not found", name); > > } > > =20 > > void object_property_get(Object *obj, Visitor *v, const char *name, > > @@ -1453,11 +1437,13 @@ void object_property_add_const_link(Object *obj= , const char *name, > > gchar *object_get_canonical_path_component(Object *obj) > > { > > ObjectProperty *prop =3D NULL; > > + GHashTableIter iter; > > =20 > > g_assert(obj); > > g_assert(obj->parent !=3D NULL); > > =20 > > - QTAILQ_FOREACH(prop, &obj->parent->properties, node) { > > + g_hash_table_iter_init(&iter, obj->parent->properties); > > + while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) { > > if (!object_property_is_child(prop)) { > > continue; > > } > > @@ -1541,11 +1527,13 @@ static Object *object_resolve_partial_path(Obje= ct *parent, > > bool *ambiguous) > > { > > Object *obj; > > + GHashTableIter iter; > > ObjectProperty *prop; > > =20 > > obj =3D object_resolve_abs_path(parent, parts, typename, 0); > > =20 > > - QTAILQ_FOREACH(prop, &parent->properties, node) { > > + g_hash_table_iter_init(&iter, parent->properties); > > + while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) { > > Object *found; > > =20 > > if (!object_property_is_child(prop)) { > > diff --git a/vl.c b/vl.c > > index e211f6a..7065d5f 100644 > > --- a/vl.c > > +++ b/vl.c > > @@ -1506,13 +1506,15 @@ MachineInfoList *qmp_query_machines(Error **err= p) > > =20 > > static int machine_help_func(QemuOpts *opts, MachineState *machine) > > { > > + GHashTableIter iter; > > ObjectProperty *prop; > > =20 > > if (!qemu_opt_has_help_opt(opts)) { > > return 0; > > } > > =20 > > - QTAILQ_FOREACH(prop, &OBJECT(machine)->properties, node) { > > + g_hash_table_iter_init(&iter, OBJECT(machine)->properties); > > + while (g_hash_table_iter_next(&iter, NULL, (gpointer *)&prop)) { > > if (!prop->set) { > > continue; > > } > >=20 >=20 >=20 --=20 David Gibson | I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ | _way_ _around_! http://www.ozlabs.org/~dgibson --QVgWX4+QEldMe/r9 Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQIcBAEBAgAGBQJWFF+WAAoJEGw4ysog2bOS/1YQAJpB9gQdOKlSYk6QcpJJW31d TRYX/fOEAg97CwhuyPzvS9elhV+f0QtVGFSrwksZoa2jRQJz3EWLGWJFuIZoSAqw nrtcYRFECdE8xdnreQDdi0QwlixccAk3x9Epb4w2iG41/qNMA7BeQH6zyR1/PWaL OjqZoLZ26DgQ20Dsjf4M86CmqP/4Ldc0Y/icaCAe3HPXQIHYjrU9BD9xZUN7Dyx0 CqJrZ01JRe9D797E+P/Xd8lF9YAk2oJWB4+90xrF+8FzOCxylE+effgBHMPWY2yf Y3675oam96hSW4axjef5WO9HelrbEYh+NqAvrnF66nRQ2r7npvNzDox6mrUWLBVM onDAx4w+EtJGvHYA3xtO6VZX2+JT13stvnEtnDJ2WMkSDF+youySotjqo4xkcssr sLb8nvzH8VWgwFDGzKdEPS1LMRtTBe5vVhYjECGKCGjqnaJvREIPjBrM/oMYNMHz x4W2KbP4yQwHxsBjyo9pfgxqjbo8WzvM7USm5VtL67dNLIuSBGtgy37lov8oqkoN 6ImjfNpfIvzMvW81gLJPd7ysLQ6zZcleAmWkgNG8YLdlyQ5IqZZAFMvY3oc4zWGG 5x41xWGPubyYkEcx8s1V7VzN/7vZVVP93OsNJVkFtK68UiNI7LqNdBR4ZwHxu/ZX uI3CY9RapKEWG/JO1EQ4 =wStF -----END PGP SIGNATURE----- --QVgWX4+QEldMe/r9--