sdap: eliminate O(N^2) loop in sdap_add_incomplete_groups()#8454
Conversation
![gemini-code-assist[bot]](https://avatars.githubusercontent.com/in/956858?s=60&v=4){kind=small}
There was a problem hiding this comment.
Code Review
This pull request correctly refactors sdap_add_incomplete_groups() to eliminate an O(N^2) loop, replacing it with a more efficient O(N) implementation. This is a great performance improvement. The changes are clean and remove now-unused code and parameters.
I've found one critical issue where loop variables are not being reset, which could lead to data corruption in the cache. Please see my detailed comment.
2fa1aa8 to
fdd3d17
Compare
fdd3d17 to
1c5c5ff
Compare
|
Note: Covscan is green. |
justin-stephenson
left a comment
justin-stephenson
left a comment
There was a problem hiding this comment.
Changes LGTM, commit message of behavior change is well documented. Thank you.
sumit-bose
left a comment
sumit-bose
left a comment
There was a problem hiding this comment.
Hi,
thank you for the improvement. I was first a bit irritated testing the patch because I started with 2000 groups and basically didn't seen any improvement. But when I switched to 5000 groups there was a considerable speedup, I didn't reach a factor of 2 but it was near. Code-wise I'm fine, ACK.
Btw, to create a test environment I used a shell script to create an LDIF file with the LDAP content and called dsctl localhost ldif2db userroot /tmp/my.ldif to load it into the LDAP server. While the bash script runs about 20s to create the LDIF, dsctl only took 3s to load 5000 users and 5000 groups. So at least in the pure LDAP case we might not need pre-populated container images but it might be possible to create larger environments on the fly with some optimization to create the LDIF file.
bye,
Sumit
`sdap_add_incomplete_groups()` had two separate steps: first it iterated the group name list checking each against sysdb to build a 'missing' list, then for each missing group it scanned the entire 'ldap_groups' array calling to find matching LDAP attributes. This resulted in O(N^2) behavior when all groups were missing (i.e. empty cache). Replace this with a single O(N) loop that iterates 'ldap_groups' directly: check sysdb, and if missing create the incomplete entry immediately. The 'sysdb_groupnames' parameter is removed as it is not used anymore. This patch also has an interesting side effect: it also makes `sysdb_update_members()` executed in the `sdap_initgr_common_store()` after `sdap_add_incomplete_groups()` faster. Most probably this is because previosuly O(N^2) allocations of `groupname` (by `sdap_get_group_primary_name()`) trashed memory, purging ldb/tdb data from the cache. Implementation assisted-by: Claude Code (Opus 4.6) Reviewed-by: Justin Stephenson <[email protected]> Reviewed-by: Sumit Bose <[email protected]>
1c5c5ff to
2a5d288
Compare
4 participants
Those patch is based on a profiling of a following test case:
tu1is a member of 5k LDAP groups (RFC2307 case, no nested groups)time id [email protected] | tr ',' '\n' | wc -lis executedThis patch provides a x2 performance gain for described test case on a laptop. See commit message for details.