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
