[Qemu-devel] [PATCH for-1.5] qom: optimize casting to leaf class and parent class

[Qemu-devel] [PATCH for-1.5] qom: optimize casting to leaf class and parent class

[Anthony Liguori]

Most QOM types use type_register_static but we still strdup the
passed data.  However, the original pointers are useful because
GCC is pretty good about collapsing strings so its very likely any
use of the pointer will end up being that same address.

IOW, with a little trickery, we can compare types by just comparing
strings and in fact that's what we do here.

We do this for the two most common cases, casting to a leaf class
or to the parent class.

With these two changes, I see a decrease from around 2 hash table
lookups to only a thousand with no run time lookups at all.

Cc: Paolo Bonzini <pbonzini@redhat.com>
Cc: Aurelien Jarno <aurelien@aurel32.net>
Cc: Andreas Färber <afaerber@suse.de>
Reported-by: Aurelien Jarno <aurelien@aurel32.net>
Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
---
Aurelien, could you please try this patch with your PPC test case?
---
 qom/object.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)

diff --git a/qom/object.c b/qom/object.c
index 75e6aac..5ecfd28 100644
--- a/qom/object.c
+++ b/qom/object.c
@@ -132,7 +132,13 @@ TypeImpl *type_register(const TypeInfo *info)
 
 TypeImpl *type_register_static(const TypeInfo *info)
 {
-    return type_register(info);
+    TypeImpl *impl;
+
+    impl = type_register(info);
+    impl->name = info->name;
+    impl->parent = info->parent;
+
+    return impl;
 }
 
 static TypeImpl *type_get_by_name(const char *name)
@@ -449,10 +455,16 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename)
 ObjectClass *object_class_dynamic_cast(ObjectClass *class,
                                        const char *typename)
 {
-    TypeImpl *target_type = type_get_by_name(typename);
+    TypeImpl *target_type;
     TypeImpl *type = class->type;
     ObjectClass *ret = NULL;
 
+    if (type->name == typename || type->parent == typename) {
+        return class;
+    }
+
+    target_type = type_get_by_name(typename);
+
     if (!target_type) {
         /* target class type unknown, so fail the cast */
         return NULL;
-- 
1.8.0

Re: [Qemu-devel] [PATCH for-1.5] qom: optimize casting to leaf class and parent class

[Aurelien Jarno]

On Fri, May 10, 2013 at 01:47:55PM -0500, Anthony Liguori wrote:
> Most QOM types use type_register_static but we still strdup the
> passed data.  However, the original pointers are useful because
> GCC is pretty good about collapsing strings so its very likely any
> use of the pointer will end up being that same address.
> 
> IOW, with a little trickery, we can compare types by just comparing
> strings and in fact that's what we do here.
> 
> We do this for the two most common cases, casting to a leaf class
> or to the parent class.
> 
> With these two changes, I see a decrease from around 2 hash table
> lookups to only a thousand with no run time lookups at all.
> 
> Cc: Paolo Bonzini <pbonzini@redhat.com>
> Cc: Aurelien Jarno <aurelien@aurel32.net>
> Cc: Andreas Färber <afaerber@suse.de>
> Reported-by: Aurelien Jarno <aurelien@aurel32.net>
> Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
> ---
> Aurelien, could you please try this patch with your PPC test case?
> ---
>  qom/object.c | 16 ++++++++++++++--
>  1 file changed, 14 insertions(+), 2 deletions(-)
> 
> diff --git a/qom/object.c b/qom/object.c
> index 75e6aac..5ecfd28 100644
> --- a/qom/object.c
> +++ b/qom/object.c
> @@ -132,7 +132,13 @@ TypeImpl *type_register(const TypeInfo *info)
>  
>  TypeImpl *type_register_static(const TypeInfo *info)
>  {
> -    return type_register(info);
> +    TypeImpl *impl;
> +
> +    impl = type_register(info);
> +    impl->name = info->name;
> +    impl->parent = info->parent;
> +
> +    return impl;
>  }
>  
>  static TypeImpl *type_get_by_name(const char *name)
> @@ -449,10 +455,16 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename)
>  ObjectClass *object_class_dynamic_cast(ObjectClass *class,
>                                         const char *typename)
>  {
> -    TypeImpl *target_type = type_get_by_name(typename);
> +    TypeImpl *target_type;
>      TypeImpl *type = class->type;
>      ObjectClass *ret = NULL;
>  
> +    if (type->name == typename || type->parent == typename) {
> +        return class;
> +    }
> +
> +    target_type = type_get_by_name(typename);
> +
>      if (!target_type) {
>          /* target class type unknown, so fail the cast */
>          return NULL;

Unfortunately it doesn't fix the problem. I only see a 0.5% improvement,
which might be in the noise. I still see g_hash_table_lookup and
g_str_hash quite high in perf top.

-- 
Aurelien Jarno	                        GPG: 1024D/F1BCDB73
aurelien@aurel32.net                 http://www.aurel32.net

Re: [Qemu-devel] [PATCH for-1.5] qom: optimize casting to leaf class and parent class

[Anthony Liguori]

[-- Attachment #1: Type: text/plain, Size: 2837 bytes --]

Aurelien Jarno <aurelien@aurel32.net> writes:

> On Fri, May 10, 2013 at 01:47:55PM -0500, Anthony Liguori wrote:
>> Most QOM types use type_register_static but we still strdup the
>> passed data.  However, the original pointers are useful because
>> GCC is pretty good about collapsing strings so its very likely any
>> use of the pointer will end up being that same address.
>> 
>> IOW, with a little trickery, we can compare types by just comparing
>> strings and in fact that's what we do here.
>> 
>> We do this for the two most common cases, casting to a leaf class
>> or to the parent class.
>> 
>> With these two changes, I see a decrease from around 2 hash table
>> lookups to only a thousand with no run time lookups at all.
>> 
>> Cc: Paolo Bonzini <pbonzini@redhat.com>
>> Cc: Aurelien Jarno <aurelien@aurel32.net>
>> Cc: Andreas Färber <afaerber@suse.de>
>> Reported-by: Aurelien Jarno <aurelien@aurel32.net>
>> Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
>> ---
>> Aurelien, could you please try this patch with your PPC test case?
>> ---
>>  qom/object.c | 16 ++++++++++++++--
>>  1 file changed, 14 insertions(+), 2 deletions(-)
>> 
>> diff --git a/qom/object.c b/qom/object.c
>> index 75e6aac..5ecfd28 100644
>> --- a/qom/object.c
>> +++ b/qom/object.c
>> @@ -132,7 +132,13 @@ TypeImpl *type_register(const TypeInfo *info)
>>  
>>  TypeImpl *type_register_static(const TypeInfo *info)
>>  {
>> -    return type_register(info);
>> +    TypeImpl *impl;
>> +
>> +    impl = type_register(info);
>> +    impl->name = info->name;
>> +    impl->parent = info->parent;
>> +
>> +    return impl;
>>  }
>>  
>>  static TypeImpl *type_get_by_name(const char *name)
>> @@ -449,10 +455,16 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename)
>>  ObjectClass *object_class_dynamic_cast(ObjectClass *class,
>>                                         const char *typename)
>>  {
>> -    TypeImpl *target_type = type_get_by_name(typename);
>> +    TypeImpl *target_type;
>>      TypeImpl *type = class->type;
>>      ObjectClass *ret = NULL;
>>  
>> +    if (type->name == typename || type->parent == typename) {
>> +        return class;
>> +    }
>> +
>> +    target_type = type_get_by_name(typename);
>> +
>>      if (!target_type) {
>>          /* target class type unknown, so fail the cast */
>>          return NULL;
>
> Unfortunately it doesn't fix the problem. I only see a 0.5% improvement,
> which might be in the noise. I still see g_hash_table_lookup and
> g_str_hash quite high in perf top.

I was afraid of this.  I assume the cast comes somewhere other than
where the type was registered.

This patch should address that.  Could you post an image too?  Then I
don't have to keep bugging you with updated patches.


[-- Attachment #2: 0001-qom-optimize-casting-to-leaf-class-and-parent-class-.patch --]
[-- Type: text/x-diff, Size: 2466 bytes --]

>From 269442decf0f137cf7d09c32442fcd16dd319901 Mon Sep 17 00:00:00 2001
From: Anthony Liguori <aliguori@us.ibm.com>
Date: Fri, 10 May 2013 13:43:11 -0500
Subject: [PATCH] qom: optimize casting to leaf class and parent class (v2)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Most QOM types use type_register_static but we still strdup the
passed data.  However, the original pointers are useful because
GCC is pretty good about collapsing strings so its very likely any
use of the pointer will end up being that same address.

IOW, with a little trickery, we can compare types by just comparing
strings and in fact that's what we do here.

We do this for the two most common cases, casting to a leaf class
or to the parent class.

With these two changes, I see a decrease from around 2 hash table
lookups to only a thousand with no run time lookups at all.

Cc: Paolo Bonzini <pbonzini@redhat.com>
Cc: Aurelien Jarno <aurelien@aurel32.net>
Cc: Andreas Färber <afaerber@suse.de>
Reported-by: Aurelien Jarno <aurelien@aurel32.net>
Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
---
v1 -> v2:
 - use strcmp() instead of ==
---
 qom/object.c | 17 +++++++++++++++--
 1 file changed, 15 insertions(+), 2 deletions(-)

diff --git a/qom/object.c b/qom/object.c
index 75e6aac..99b5b33 100644
--- a/qom/object.c
+++ b/qom/object.c
@@ -132,7 +132,13 @@ TypeImpl *type_register(const TypeInfo *info)
 
 TypeImpl *type_register_static(const TypeInfo *info)
 {
-    return type_register(info);
+    TypeImpl *impl;
+
+    impl = type_register(info);
+    impl->name = info->name;
+    impl->parent = info->parent;
+
+    return impl;
 }
 
 static TypeImpl *type_get_by_name(const char *name)
@@ -449,10 +455,17 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename)
 ObjectClass *object_class_dynamic_cast(ObjectClass *class,
                                        const char *typename)
 {
-    TypeImpl *target_type = type_get_by_name(typename);
+    TypeImpl *target_type;
     TypeImpl *type = class->type;
     ObjectClass *ret = NULL;
 
+    if (strcmp(type->name, typename) == 0 ||
+        strcmp(type->parent, typename) == 0) {
+        return class;
+    }
+
+    target_type = type_get_by_name(typename);
+
     if (!target_type) {
         /* target class type unknown, so fail the cast */
         return NULL;
-- 
1.8.0


[-- Attachment #3: Type: text/plain, Size: 159 bytes --]


Regards,

Anthony Liguori

>
> -- 
> Aurelien Jarno	                        GPG: 1024D/F1BCDB73
> aurelien@aurel32.net                 http://www.aurel32.net

Re: [Qemu-devel] [PATCH for-1.5] qom: optimize casting to leaf class and parent class

[Aurelien Jarno]

On Fri, May 10, 2013 at 05:58:23PM -0500, Anthony Liguori wrote:
> Aurelien Jarno <aurelien@aurel32.net> writes:
> 
> > On Fri, May 10, 2013 at 01:47:55PM -0500, Anthony Liguori wrote:
> >> Most QOM types use type_register_static but we still strdup the
> >> passed data.  However, the original pointers are useful because
> >> GCC is pretty good about collapsing strings so its very likely any
> >> use of the pointer will end up being that same address.
> >> 
> >> IOW, with a little trickery, we can compare types by just comparing
> >> strings and in fact that's what we do here.
> >> 
> >> We do this for the two most common cases, casting to a leaf class
> >> or to the parent class.
> >> 
> >> With these two changes, I see a decrease from around 2 hash table
> >> lookups to only a thousand with no run time lookups at all.
> >> 
> >> Cc: Paolo Bonzini <pbonzini@redhat.com>
> >> Cc: Aurelien Jarno <aurelien@aurel32.net>
> >> Cc: Andreas Färber <afaerber@suse.de>
> >> Reported-by: Aurelien Jarno <aurelien@aurel32.net>
> >> Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
> >> ---
> >> Aurelien, could you please try this patch with your PPC test case?
> >> ---
> >>  qom/object.c | 16 ++++++++++++++--
> >>  1 file changed, 14 insertions(+), 2 deletions(-)
> >> 
> >> diff --git a/qom/object.c b/qom/object.c
> >> index 75e6aac..5ecfd28 100644
> >> --- a/qom/object.c
> >> +++ b/qom/object.c
> >> @@ -132,7 +132,13 @@ TypeImpl *type_register(const TypeInfo *info)
> >>  
> >>  TypeImpl *type_register_static(const TypeInfo *info)
> >>  {
> >> -    return type_register(info);
> >> +    TypeImpl *impl;
> >> +
> >> +    impl = type_register(info);
> >> +    impl->name = info->name;
> >> +    impl->parent = info->parent;
> >> +
> >> +    return impl;
> >>  }
> >>  
> >>  static TypeImpl *type_get_by_name(const char *name)
> >> @@ -449,10 +455,16 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename)
> >>  ObjectClass *object_class_dynamic_cast(ObjectClass *class,
> >>                                         const char *typename)
> >>  {
> >> -    TypeImpl *target_type = type_get_by_name(typename);
> >> +    TypeImpl *target_type;
> >>      TypeImpl *type = class->type;
> >>      ObjectClass *ret = NULL;
> >>  
> >> +    if (type->name == typename || type->parent == typename) {
> >> +        return class;
> >> +    }
> >> +
> >> +    target_type = type_get_by_name(typename);
> >> +
> >>      if (!target_type) {
> >>          /* target class type unknown, so fail the cast */
> >>          return NULL;
> >
> > Unfortunately it doesn't fix the problem. I only see a 0.5% improvement,
> > which might be in the noise. I still see g_hash_table_lookup and
> > g_str_hash quite high in perf top.
> 
> I was afraid of this.  I assume the cast comes somewhere other than
> where the type was registered.
> 
> This patch should address that.  Could you post an image too?  Then I
> don't have to keep bugging you with updated patches.
> 

It doesn't fix the issue, I don't really see any improvement, and
g_hash_table_lookup + g_str_hash + __strcmp_sse42 are still high in 
perf top.

I have uploaded an image to reproduce the issue:

  http://temp.aurel32.net/debian_squeeze_powerpc_qom_casts.qcow2

You can run it with:

  qemu-system-ppc -snapshot -hda debian_squeeze_powerpc_qom_casts.qcow2

You can also add -nographic if you don't want the graphical interface,
the boot process won't show up, but after half a minute, you should get
to the login prompt. You can then login as user/user and run bench.sh,
though if you are using perf top, the libglib-2.0 functions are visible
even during the boot process.

It's a different image than the one I am using to test your patches, as
I didn't have a small ppc64 image ready. That said the issue is also
visible there.

-- 
Aurelien Jarno	                        GPG: 1024D/F1BCDB73
aurelien@aurel32.net                 http://www.aurel32.net

Re: [Qemu-devel] [PATCH for-1.5] qom: optimize casting to leaf class and parent class

[Paolo Bonzini]

Il 11/05/2013 00:58, Anthony Liguori ha scritto:
> Aurelien Jarno <aurelien@aurel32.net> writes:
> 
>> On Fri, May 10, 2013 at 01:47:55PM -0500, Anthony Liguori wrote:
>>> Most QOM types use type_register_static but we still strdup the
>>> passed data.  However, the original pointers are useful because
>>> GCC is pretty good about collapsing strings so its very likely any
>>> use of the pointer will end up being that same address.
>>>
>>> IOW, with a little trickery, we can compare types by just comparing
>>> strings and in fact that's what we do here.
>>>
>>> We do this for the two most common cases, casting to a leaf class
>>> or to the parent class.
>>>
>>> With these two changes, I see a decrease from around 2 hash table
>>> lookups to only a thousand with no run time lookups at all.
>>>
>>> Cc: Paolo Bonzini <pbonzini@redhat.com>
>>> Cc: Aurelien Jarno <aurelien@aurel32.net>
>>> Cc: Andreas Färber <afaerber@suse.de>
>>> Reported-by: Aurelien Jarno <aurelien@aurel32.net>
>>> Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
>>> ---
>>> Aurelien, could you please try this patch with your PPC test case?
>>> ---
>>>  qom/object.c | 16 ++++++++++++++--
>>>  1 file changed, 14 insertions(+), 2 deletions(-)
>>>
>>> diff --git a/qom/object.c b/qom/object.c
>>> index 75e6aac..5ecfd28 100644
>>> --- a/qom/object.c
>>> +++ b/qom/object.c
>>> @@ -132,7 +132,13 @@ TypeImpl *type_register(const TypeInfo *info)
>>>  
>>>  TypeImpl *type_register_static(const TypeInfo *info)
>>>  {
>>> -    return type_register(info);
>>> +    TypeImpl *impl;
>>> +
>>> +    impl = type_register(info);
>>> +    impl->name = info->name;
>>> +    impl->parent = info->parent;
>>> +
>>> +    return impl;
>>>  }

This is ok with a comment.

>>>  static TypeImpl *type_get_by_name(const char *name)
>>> @@ -449,10 +455,16 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename)
>>>  ObjectClass *object_class_dynamic_cast(ObjectClass *class,
>>>                                         const char *typename)
>>>  {
>>> -    TypeImpl *target_type = type_get_by_name(typename);
>>> +    TypeImpl *target_type;
>>>      TypeImpl *type = class->type;
>>>      ObjectClass *ret = NULL;
>>>  
>>> +    if (type->name == typename || type->parent == typename) {
>>> +        return class;
>>> +    }

I prefer my patch 3/9.  With the hunk above, it works fine for the
simple case of casts in a device model's callbacks (testing type->parent
would almost always fail, so it is not worthwhile).

Unfortunately, strcmp is just as bad as a hashtable lookup (both are
O(n) in the size the string, instead of O(1)).

Paolo

>>> +    target_type = type_get_by_name(typename);
>>> +
>>>      if (!target_type) {
>>>          /* target class type unknown, so fail the cast */
>>>          return NULL;
>>
>> Unfortunately it doesn't fix the problem. I only see a 0.5% improvement,
>> which might be in the noise. I still see g_hash_table_lookup and
>> g_str_hash quite high in perf top.
> 
> I was afraid of this.  I assume the cast comes somewhere other than
> where the type was registered.
> 
> This patch should address that.  Could you post an image too?  Then I
> don't have to keep bugging you with updated patches.
> 
> 
> 
> 
> Regards,
> 
> Anthony Liguori
> 
>>
>> -- 
>> Aurelien Jarno	                        GPG: 1024D/F1BCDB73
>> aurelien@aurel32.net                 http://www.aurel32.net

Re: [Qemu-devel] [PATCH for-1.5] qom: optimize casting to leaf class and parent class

[Anthony Liguori]

Paolo Bonzini <pbonzini@redhat.com> writes:

> Il 11/05/2013 00:58, Anthony Liguori ha scritto:
>> Aurelien Jarno <aurelien@aurel32.net> writes:
>> 
>>> On Fri, May 10, 2013 at 01:47:55PM -0500, Anthony Liguori wrote:
>>>> Most QOM types use type_register_static but we still strdup the
>>>> passed data.  However, the original pointers are useful because
>>>> GCC is pretty good about collapsing strings so its very likely any
>>>> use of the pointer will end up being that same address.
>>>>
>>>> IOW, with a little trickery, we can compare types by just comparing
>>>> strings and in fact that's what we do here.
>>>>
>>>> We do this for the two most common cases, casting to a leaf class
>>>> or to the parent class.
>>>>
>>>> With these two changes, I see a decrease from around 2 hash table
>>>> lookups to only a thousand with no run time lookups at all.
>>>>
>>>> Cc: Paolo Bonzini <pbonzini@redhat.com>
>>>> Cc: Aurelien Jarno <aurelien@aurel32.net>
>>>> Cc: Andreas Färber <afaerber@suse.de>
>>>> Reported-by: Aurelien Jarno <aurelien@aurel32.net>
>>>> Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
>>>> ---
>>>> Aurelien, could you please try this patch with your PPC test case?
>>>> ---
>>>>  qom/object.c | 16 ++++++++++++++--
>>>>  1 file changed, 14 insertions(+), 2 deletions(-)
>>>>
>>>> diff --git a/qom/object.c b/qom/object.c
>>>> index 75e6aac..5ecfd28 100644
>>>> --- a/qom/object.c
>>>> +++ b/qom/object.c
>>>> @@ -132,7 +132,13 @@ TypeImpl *type_register(const TypeInfo *info)
>>>>  
>>>>  TypeImpl *type_register_static(const TypeInfo *info)
>>>>  {
>>>> -    return type_register(info);
>>>> +    TypeImpl *impl;
>>>> +
>>>> +    impl = type_register(info);
>>>> +    impl->name = info->name;
>>>> +    impl->parent = info->parent;
>>>> +
>>>> +    return impl;
>>>>  }
>
> This is ok with a comment.
>
>>>>  static TypeImpl *type_get_by_name(const char *name)
>>>> @@ -449,10 +455,16 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename)
>>>>  ObjectClass *object_class_dynamic_cast(ObjectClass *class,
>>>>                                         const char *typename)
>>>>  {
>>>> -    TypeImpl *target_type = type_get_by_name(typename);
>>>> +    TypeImpl *target_type;
>>>>      TypeImpl *type = class->type;
>>>>      ObjectClass *ret = NULL;
>>>>  
>>>> +    if (type->name == typename || type->parent == typename) {
>>>> +        return class;
>>>> +    }
>
> I prefer my patch 3/9.  With the hunk above, it works fine for the
> simple case of casts in a device model's callbacks (testing type->parent
> would almost always fail, so it is not worthwhile).
>
> Unfortunately, strcmp is just as bad as a hashtable lookup (both are
> O(n) in the size the string, instead of O(1)).

FWIW, I've been experimenting with Aurelien's image.

The issue here is that the PPC CPUs are 4 levels deep consisting of the
leaf model, a PPC base model, the PPC CPU model, then the CPU object.

So these checks (regardless of how they're done) will never catch
because we're attempting to cast the object to either the PPC CPU model
or CPU object model.

I've been experimenting with a front side cache on top of the hash
table.  I see a nice improvement but still not as good as your patch.

I'll continue experimenting.   I fear that the only way to get parity is
to expose the TypeImpl to the cast macro to avoid the hash lookup
entirely.  Unfortunately that's a touch every change.

Regards,

Anthony Liguori

>
> Paolo
>
>>>> +    target_type = type_get_by_name(typename);
>>>> +
>>>>      if (!target_type) {
>>>>          /* target class type unknown, so fail the cast */
>>>>          return NULL;
>>>
>>> Unfortunately it doesn't fix the problem. I only see a 0.5% improvement,
>>> which might be in the noise. I still see g_hash_table_lookup and
>>> g_str_hash quite high in perf top.
>> 
>> I was afraid of this.  I assume the cast comes somewhere other than
>> where the type was registered.
>> 
>> This patch should address that.  Could you post an image too?  Then I
>> don't have to keep bugging you with updated patches.
>> 
>> 
>> 
>> 
>> Regards,
>> 
>> Anthony Liguori
>> 
>>>
>>> -- 
>>> Aurelien Jarno	                        GPG: 1024D/F1BCDB73
>>> aurelien@aurel32.net                 http://www.aurel32.net