[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance i
From: |
Pavel Fedin |
Subject: |
Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement |
Date: |
Mon, 27 Jul 2015 17:36:05 +0300 |
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
- [Qemu-devel] [PATCH v4 0/2] QOM: object_property_add() performance improvement, Pavel Fedin, 2015/07/14
- [Qemu-devel] [PATCH v4 1/2] QOM: Introduce object_property_add_single(), Pavel Fedin, 2015/07/14
- [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement, Pavel Fedin, 2015/07/14
- Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement, Daniel P. Berrange, 2015/07/27
- Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement,
Pavel Fedin <=
- Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement, Markus Armbruster, 2015/07/27
- Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement, Pavel Fedin, 2015/07/27
- Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement, Andreas Färber, 2015/07/27
- Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement, Paolo Bonzini, 2015/07/27
- Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement, Paolo Bonzini, 2015/07/27
- Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement, Pavel Fedin, 2015/07/27
- Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement, Paolo Bonzini, 2015/07/27
- Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement, Pavel Fedin, 2015/07/28