Isn't a hashtable a bit overhead especially if you have entries with few attributes.
Would an approach like in valuset work ? Instead of having a linked list of attrs use a sorted (directly or indirectly) array of attr structs and do a binary search for attrlist_find. It would reduce the comparisons, reduce allocs (in slapi_attr_new) and be more cpu cache friendly

Isn't a hashtable a bit overhead especially if you have entries with few attributes.

Correct. Especially if you have to rebuild the hashtable frequently too.

Would an approach like in valuset work ? Instead of having a linked list of attrs use a sorted (directly or indirectly) array of attr structs and do a binary search for attrlist_find. It would reduce the comparisons, reduce allocs (in slapi_attr_new) and be more cpu cache friendly

I think that a directly sorted version seems better here yes. Especially because attrs in a directory would tend to either single value in many cases OR a large number of values (ie memberof). So a BTreeSet would actually be perfect here as in the single value or low value case, it's effectively a sorted array. But given we don't have access to this easily in C, I think the sorted array + binary search is the best option.

@firstyear , @elkris, Thank you so much for your ideas and feedback. I agree that sorted array looks a better idea than hash table. A first step of the ticket is to do an evaluation of the expected benefit, will do that later today

389-ds-base is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in 389-ds-base's github repository.

This issue has been cloned to Github and is available here:
- https://github.com/389ds/389-ds-base/issues/4309

If you want to receive further updates on the issue, please navigate to the github issue
and click on subscribe button.

Thank you for understanding. We apologize for all inconvenience.