On Tue, 2012-08-07 at 15:40 +0200, Michal Zidek wrote:
On 08/06/2012 08:57 PM, Simo Sorce wrote:
> The major question I have is that this new code introduces O(N^2)
> behavior, if there are more then a handful of groups it will be quite
> costly. Can we find a way that is not so expensive ?
I think this is not a big problem. If I understand the code correctly,
the inner cycle only iterates through potential direct parent groups (we
add group member to them later) and it is unlikely to be a big number in
real scenarios (Or am I wrong? Is it common that a group has so many
direct parents that it would be expensive?).
On what data do you base your assertion about probability, not saying
you are wrong, but is it a gut feeling or do you have actual data ?
I corrected the nitpicks, new patch is attached.
Nitpick-wise looks ok.
You may want to add a talloc_free(add); before the continue; but you
could get even more gains if you instead of freeing the add array at
each loop always just realloc it if grp_count is > than the previous
grp_count.
Allocations tend to be expensive and here you can spare a lot of
allocation given you always leave the array in consistent state by
adding the terminating NULL.
Also given you have to count it may make sense to pass down the
interfaces the number of elements to avoid busy loops just for counting,
but I haven't looked at the interface, so if it is a lot of work, please
ignore this suggestion for now (feel free to file a ticket if you want).
Simo.
--
Simo Sorce * Red Hat, Inc * New York