> Hi guys, > here is the second part of nice talloc features. > > talloc_*_append(dest, src) works in O(n^2) complexity as it needs to do > strlen(dest) and strlen(src). Talloc also provides an alternative > talloc_*_append_buffer(dest, src) which uses size of the dest context > to determine the length of the string. Its complexity is O(n) as it > runs only strlen(src).
I wonder why original talloc_*_append functions are not using the same
approach. After all they both work on the same data.
> Let me show it on an example. One part of the sysdb filter creation for
> sudo contains:
> for (i=0; groupnames[i] != NULL; i++) {
> filter = talloc_asprintf_append(filter, "(%s=%%%s)",
> SYSDB_SUDO_CACHE_AT_USER,
> groupnames[i]);
> NULL_CHECK(specific_filter, ret, done);
> }
> groupnames contains all groups that a user is member of.
>
> Let's say he's a member of 100 groups where each group name consist of
> 10 characters. We will run strlen(filter) 100 times with total of
> sum[i=1..100](10*i) = 50 500 iterations but we can simply make it 0 if
> we replace talloc_*_append with talloc_*_append_buffer.
There are quite a few places in the code where we construct filters in a
similar way. I'm all for optimizing them all.
I wonder. Have you run any performance tests on at least dome parts of the
code. Before we start doing these optimization on every place in the code, it
might be nice to have an image what kind of performance boost can we expect. I
would like to avoid another memberof plugin fiasco (even though the scale of
work would be considerably different here) ;-)
Thanks
Jan
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ sssd-devel mailing list [email protected] https://fedorahosted.org/mailman/listinfo/sssd-devel
