[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