[Qemu-devel] [PATCH for-1.5 1/2] qom: aggressively optimize qom casting

[Qemu-devel] [PATCH for-1.5 1/2] qom: aggressively optimize qom casting

[Anthony Liguori]

This patch adds a small typename cache to ObjectClass.  This allows
caching positive casts within each ObjectClass.  Benchmarking a
PPC workload provided by Aurelien, this patch eliminates every
single g_hash_table_lookup() happening during the benchmark (which
was about 2 million per-second).

With this patch applied, I get exactly the same performance (within
the margin of error) as with --disable-qom-cast-debug.

N.B. it's safe to cache typenames only from the _assert() macros
because they are always called with string literals.

Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
---
 include/qom/object.h |  4 ++++
 qom/object.c         | 40 ++++++++++++++++++++++++++++++++++++++--
 2 files changed, 42 insertions(+), 2 deletions(-)

diff --git a/include/qom/object.h b/include/qom/object.h
index 63e2a40..23fc048 100644
--- a/include/qom/object.h
+++ b/include/qom/object.h
@@ -344,6 +344,8 @@ typedef void (ObjectUnparent)(Object *obj);
  */
 typedef void (ObjectFree)(void *obj);
 
+#define OBJECT_CLASS_CAST_CACHE 4
+
 /**
  * ObjectClass:
  *
@@ -356,6 +358,8 @@ struct ObjectClass
     Type type;
     GSList *interfaces;
 
+    const char *cast_cache[OBJECT_CLASS_CAST_CACHE];
+
     ObjectUnparent *unparent;
 };
 
diff --git a/qom/object.c b/qom/object.c
index f5f416b..ec88231 100644
--- a/qom/object.c
+++ b/qom/object.c
@@ -439,7 +439,16 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename,
                                      typename, file, line, func);
 
 #ifdef CONFIG_QOM_CAST_DEBUG
-    Object *inst = object_dynamic_cast(obj, typename);
+    int i;
+    Object *inst;
+
+    for (i = 0; i < OBJECT_CLASS_CAST_CACHE; i++) {
+        if (obj->class->cast_cache[i] == typename) {
+            goto out;
+        }
+    }
+
+    inst = object_dynamic_cast(obj, typename);
 
     if (!inst && obj) {
         fprintf(stderr, "%s:%d:%s: Object %p is not an instance of type %s\n",
@@ -448,6 +457,15 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename,
     }
 
     assert(obj == inst);
+
+    if (obj == inst) {
+        for (i = 1; i < OBJECT_CLASS_CAST_CACHE; i++) {
+            obj->class->cast_cache[i - 1] = obj->class->cast_cache[i];
+        }
+        obj->class->cast_cache[i - 1] = typename;
+    }
+
+out:
 #endif
     return obj;
 }
@@ -510,7 +528,16 @@ ObjectClass *object_class_dynamic_cast_assert(ObjectClass *class,
     trace_object_class_dynamic_cast_assert(class ? class->type->name : "(null)",
                                            typename, file, line, func);
 
-#ifndef CONFIG_QOM_CAST_DEBUG
+#ifdef CONFIG_QOM_CAST_DEBUG
+    int i;
+
+    for (i = 0; i < OBJECT_CLASS_CAST_CACHE; i++) {
+        if (class->cast_cache[i] == typename) {
+            ret = class;
+            goto out;
+        }
+    }
+#else
     if (!class->interfaces) {
         return class;
     }
@@ -523,6 +550,15 @@ ObjectClass *object_class_dynamic_cast_assert(ObjectClass *class,
         abort();
     }
 
+#ifdef CONFIG_QOM_CAST_DEBUG
+    if (ret == class) {
+        for (i = 1; i < OBJECT_CLASS_CAST_CACHE; i++) {
+            class->cast_cache[i - 1] = class->cast_cache[i];
+        }
+        class->cast_cache[i - 1] = typename;
+    }
+out:
+#endif
     return ret;
 }
 
-- 
1.8.0

[Qemu-devel] [PATCH for-1.5 2/2] qom: add casting statistics

[Anthony Liguori]

This is not meant to be applied but included as a reference.

Signed-off-by: Anthony Liguori <aliguori@us.ibm.com>
---
 qom/object.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 88 insertions(+)

diff --git a/qom/object.c b/qom/object.c
index ec88231..2bfdcda 100644
--- a/qom/object.c
+++ b/qom/object.c
@@ -136,12 +136,33 @@ TypeImpl *type_register_static(const TypeInfo *info)
     return type_register(info);
 }
 
+#ifdef CONFIG_QOM_CAST_STATS
+typedef struct CastStats
+{
+    uint64_t total;
+    uint64_t miss;
+    uint64_t hit;
+    uint64_t rebalance;
+    uint64_t lookups;
+    uint64_t class;
+} CastStats;
+
+#define CAST_STATS_DUMP_INTERVAL 1000000
+
+static CastStats cast_stats;
+static qemu_timeval cast_stats_ts;
+#endif
+
 static TypeImpl *type_get_by_name(const char *name)
 {
     if (name == NULL) {
         return NULL;
     }
 
+#ifdef CONFIG_QOM_CAST_STATS
+    cast_stats.lookups++;
+#endif
+
     return type_table_lookup(name);
 }
 
@@ -432,6 +453,43 @@ Object *object_dynamic_cast(Object *obj, const char *typename)
     return NULL;
 }
 
+#ifdef CONFIG_QOM_CAST_STATS
+static void cast_stats_dump(void)
+{
+    qemu_timeval ts;
+    uint64_t delta;
+    int64_t udelta;
+
+    qemu_gettimeofday(&ts);
+
+    delta = ts.tv_sec - cast_stats_ts.tv_sec;
+    udelta = ts.tv_usec - cast_stats_ts.tv_usec;
+    if (udelta < 0) {
+        delta += 1;
+        udelta += 1000000;
+    }
+
+    delta *= 1000000;
+    delta += udelta;
+
+    printf("casts/sec: %f\n", (double)(cast_stats.total * 1000000) / delta);
+    printf("hit/sec: %f\n", (double)(cast_stats.hit * 1000000) / delta);
+    printf("miss/sec: %f\n", (double)(cast_stats.miss * 1000000) / delta);
+    printf("rebalance/sec: %f\n", (double)(cast_stats.rebalance * 1000000) / delta);
+    printf("classes/sec: %f\n", (double)(cast_stats.class * 1000000) / delta);
+    printf("lookups/sec: %f\n", (double)(cast_stats.lookups * 1000000) / delta);
+    printf("\n");
+
+    cast_stats.total = 1;
+    cast_stats.lookups = 0;
+    cast_stats.miss = 0;
+    cast_stats.hit = 0;
+    cast_stats.rebalance = 0;
+    cast_stats.class = 0;
+    cast_stats_ts = ts;
+}
+#endif
+
 Object *object_dynamic_cast_assert(Object *obj, const char *typename,
                                    const char *file, int line, const char *func)
 {
@@ -442,8 +500,17 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename,
     int i;
     Object *inst;
 
+#ifdef CONFIG_QOM_CAST_STATS
+    if (cast_stats.total == 0) {
+        qemu_gettimeofday(&cast_stats_ts);
+    }
+#endif
+
     for (i = 0; i < OBJECT_CLASS_CAST_CACHE; i++) {
         if (obj->class->cast_cache[i] == typename) {
+#ifdef CONFIG_QOM_CAST_STATS
+            cast_stats.hit++;
+#endif
             goto out;
         }
     }
@@ -463,9 +530,19 @@ Object *object_dynamic_cast_assert(Object *obj, const char *typename,
             obj->class->cast_cache[i - 1] = obj->class->cast_cache[i];
         }
         obj->class->cast_cache[i - 1] = typename;
+#ifdef CONFIG_QOM_CAST_STATS
+        cast_stats.miss++;
+#endif
     }
 
 out:
+#ifdef CONFIG_QOM_CAST_STATS
+    cast_stats.total++;
+
+    if (cast_stats.total == CAST_STATS_DUMP_INTERVAL) {
+        cast_stats_dump();
+    }
+#endif
 #endif
     return obj;
 }
@@ -531,8 +608,15 @@ ObjectClass *object_class_dynamic_cast_assert(ObjectClass *class,
 #ifdef CONFIG_QOM_CAST_DEBUG
     int i;
 
+#ifdef CONFIG_QOM_CAST_STATS
+    cast_stats.class++;
+#endif
+
     for (i = 0; i < OBJECT_CLASS_CAST_CACHE; i++) {
         if (class->cast_cache[i] == typename) {
+#ifdef CONFIG_QOM_CAST_STATS
+            cast_stats.hit++;
+#endif
             ret = class;
             goto out;
         }
@@ -556,6 +640,10 @@ ObjectClass *object_class_dynamic_cast_assert(ObjectClass *class,
             class->cast_cache[i - 1] = class->cast_cache[i];
         }
         class->cast_cache[i - 1] = typename;
+
+#ifdef CONFIG_QOM_CAST_STATS
+        cast_stats.miss++;
+#endif
     }
 out:
 #endif
-- 
1.8.0

Re: [Qemu-devel] [PATCH for-1.5 1/2] qom: aggressively optimize qom casting

[Paolo Bonzini]

Il 13/05/2013 22:31, Anthony Liguori ha scritto:
> This patch adds a small typename cache to ObjectClass.  This allows
> caching positive casts within each ObjectClass.  Benchmarking a
> PPC workload provided by Aurelien, this patch eliminates every
> single g_hash_table_lookup() happening during the benchmark (which
> was about 2 million per-second).
> 
> With this patch applied, I get exactly the same performance (within
> the margin of error) as with --disable-qom-cast-debug.
> 
> N.B. it's safe to cache typenames only from the _assert() macros
> because they are always called with string literals.

Nice!  Perhaps (for 1.6?) we can cache other results than class, so that
interfaces are sped up as well.

Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>

Re: [Qemu-devel] [PATCH for-1.5 1/2] qom: aggressively optimize qom casting

[Anthony Liguori]

Paolo Bonzini <pbonzini@redhat.com> writes:

> Il 13/05/2013 22:31, Anthony Liguori ha scritto:
>> This patch adds a small typename cache to ObjectClass.  This allows
>> caching positive casts within each ObjectClass.  Benchmarking a
>> PPC workload provided by Aurelien, this patch eliminates every
>> single g_hash_table_lookup() happening during the benchmark (which
>> was about 2 million per-second).
>> 
>> With this patch applied, I get exactly the same performance (within
>> the margin of error) as with --disable-qom-cast-debug.
>> 
>> N.B. it's safe to cache typenames only from the _assert() macros
>> because they are always called with string literals.
>
> Nice!  Perhaps (for 1.6?) we can cache other results than class, so that
> interfaces are sped up as well.

Yes, there's no reason not to store any computed data within a class.
There are very few of them within QEMU and it's very easy to get to.

> Reviewed-by: Paolo Bonzini <pbonzini@redhat.com>

Thanks.  We should leave the --disable-qom-casts present for 1.5 but I'd
like to discuss reverting it for 1.6.  I'll send patches once 1.6 opens
up.

Regards,

Anthony Liguori

Re: [Qemu-devel] [PATCH for-1.5 1/2] qom: aggressively optimize qom casting

[Paolo Bonzini]

Il 13/05/2013 23:04, Anthony Liguori ha scritto:
> We should leave the --disable-qom-casts present for 1.5 but I'd like
> to discuss reverting it for 1.6.  I'll send patches once 1.6 opens up.

I disagree, the cost is small but still provably nonzero.

We should only remove it once interfaces start to be more pervasive (it
would be nice for example to replace the RTC's #ifdef TARGET_I386 with
an interface).

Paolo

Re: [Qemu-devel] [PATCH for-1.5 1/2] qom: aggressively optimize qom casting

[Peter Maydell]

On 13 May 2013 21:31, Anthony Liguori <aliguori@us.ibm.com> wrote:
> This patch adds a small typename cache to ObjectClass.  This allows
> caching positive casts within each ObjectClass.  Benchmarking a
> PPC workload provided by Aurelien, this patch eliminates every
> single g_hash_table_lookup() happening during the benchmark (which
> was about 2 million per-second).

That's a lot of hashtable lookups...

> --- a/include/qom/object.h
> +++ b/include/qom/object.h
> @@ -344,6 +344,8 @@ typedef void (ObjectUnparent)(Object *obj);
>   */
>  typedef void (ObjectFree)(void *obj);
>
> +#define OBJECT_CLASS_CAST_CACHE 4

Total nitpick, but shouldn't this be
OBJECT_CLASS_CAST_CACHE_SIZE ?

thanks
-- PMM

Re: [Qemu-devel] [PATCH for-1.5 1/2] qom: aggressively optimize qom casting

[Anthony Liguori]

Peter Maydell <peter.maydell@linaro.org> writes:

> On 13 May 2013 21:31, Anthony Liguori <aliguori@us.ibm.com> wrote:
>> This patch adds a small typename cache to ObjectClass.  This allows
>> caching positive casts within each ObjectClass.  Benchmarking a
>> PPC workload provided by Aurelien, this patch eliminates every
>> single g_hash_table_lookup() happening during the benchmark (which
>> was about 2 million per-second).
>
> That's a lot of hashtable lookups...

I suspect it's due to a cast somewhere in a path checking for pending
interrupts or something like that.  That would get called quite often.

>
>> --- a/include/qom/object.h
>> +++ b/include/qom/object.h
>> @@ -344,6 +344,8 @@ typedef void (ObjectUnparent)(Object *obj);
>>   */
>>  typedef void (ObjectFree)(void *obj);
>>
>> +#define OBJECT_CLASS_CAST_CACHE 4
>
> Total nitpick, but shouldn't this be
> OBJECT_CLASS_CAST_CACHE_SIZE ?

Ack, I need to respin anyway so I'll make the updates.

Thanks,

Anthony Liguori



>
> thanks
> -- PMM

Re: [Qemu-devel] [PATCH for-1.5 1/2] qom: aggressively optimize qom casting

[Anthony Liguori]

Applied.  Thanks.

Regards,

Anthony Liguori