[SSSD] [PATCHES] Some optimizations of memeberof plugin
Jan Zelený
jzeleny at redhat.com
Wed Jun 29 14:11:41 UTC 2011
This is the first part of some optimization I'd like to propose in memberof
plugin.
035 - mbof_dn_array optimization
This change can bring better performance in certain cases of deep and/or
circular membership structure. It reduces the complexity of some places in
code from N^3 to N^2. It has similar use case in later patches (even in those
I've not completed yet) as well.
036 - duplicate checking
This can improve performance when adding a group with many direct members,
reducing the complexity of adding a member from N^2 to N.
037 - unnecessary reallocation
I just don't like those cases when we realloc many times, each time growing
the array by 1 element. This patch removes one such case where it was
completely unnecessary.
038 - redundant duplicate checking
This one is little tricky to figure out and to be honest I'm still only 99%
sure about it. When analyzed how addop appending works, this check is totally
useless, since it will never find anything - all duplicates should be already
found by addop appending. Of course I was only considering one process modyfing
the database at a time thanks to transactions. If anyone needs a deeper
analysis, let me know, I'll explain you my train of thoughts.
Right now I'm working on the membership counter patch. It seemed to be quite
easy at first, but right now it seems that it'll take some time to make
everything work.
I'll be happy to answer any questions regarding these patches, feel free to
ping me.
Jan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: jzeleny-035-mbof_dn_array-structure-optimized.patch
Type: text/x-patch
Size: 20312 bytes
Desc: not available
URL: <https://lists.fedorahosted.org/pipermail/sssd-devel/attachments/20110629/a6563854/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: jzeleny-036-duplicate-checking.patch
Type: text/x-patch
Size: 4168 bytes
Desc: not available
URL: <https://lists.fedorahosted.org/pipermail/sssd-devel/attachments/20110629/a6563854/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: jzeleny-037-memberof-unnecessary-realocation-removed.patch
Type: text/x-patch
Size: 2937 bytes
Desc: not available
URL: <https://lists.fedorahosted.org/pipermail/sssd-devel/attachments/20110629/a6563854/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: jzeleny-038-memberof-removed-redundant-duplicate-checking.patch
Type: text/x-patch
Size: 3382 bytes
Desc: not available
URL: <https://lists.fedorahosted.org/pipermail/sssd-devel/attachments/20110629/a6563854/attachment-0003.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part.
URL: <https://lists.fedorahosted.org/pipermail/sssd-devel/attachments/20110629/a6563854/attachment.sig>
More information about the sssd-devel
mailing list