Bug 14308 - Can we replace Linear search with pattern search?
Summary: Can we replace Linear search with pattern search?
Status: NEW
Alias: None
Product: Samba 4.1 and newer
Classification: Unclassified
Component: File services (show other bugs)
Version: unspecified
Hardware: All All
: P5 normal (vote)
Target Milestone: ---
Assignee: Samba QA Contact
QA Contact: Samba QA Contact
Depends on:
Reported: 2020-03-03 06:14 UTC by Amit Kumar
Modified: 2020-03-04 22:27 UTC (History)
0 users

See Also:


Note You need to log in before you can comment on or make changes to this bug.
Description Amit Kumar 2020-03-03 06:14:41 UTC
This code block does linear search, which can take O(n) time can we replace with pattern search considering domain sid strings would be similar, just few bytes would differ?

This may make few microsec difference but summation of microseconds can be significant in bigger enviornment.


fstring dom_sid;
#define FSTRING_LEN 256
typedef char fstring[FSTRING_LEN];


int dom_sid_compare(const struct dom_sid *sid1, const struct dom_sid *sid2)
        for (i = sid1->num_auths-1; i >= 0; --i)
                if (sid1->sub_auths[i] != sid2->sub_auths[i])
                        return sid1->sub_auths[i] - sid2->sub_auths[i];
Comment 1 Ralph Böhme 2020-03-03 08:00:36 UTC
Amit, thanks for looking into improving Samba.

To me this doesn't look to be a bug, but instead a possible performance improvement which you may want to discuss on the samba-technical mailing list.

I don't think Samba bugzilla is the right place to discuss this.

If you agree, please close the bugs and start a discussion on the mailing list. Thanks!
Comment 2 Andrew Bartlett 2020-03-04 22:27:24 UTC
Please also take care that as a _compare function, the ordering of the result may be depended on by callers, so any change here would need an extensive testsuite.