Re: [Qemu-devel] [PATCH v4 2/2] QOM: object_property_add() performance improvement

[Pavel Fedin]

 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