[Top][All Lists]

[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


> 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.


> 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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]