[SERVER-66764] Polyfill C++20 constexpr isSorted Created: 25/May/22  Updated: 16/Sep/22  Resolved: 21/Jul/22

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Daniel Morilha (Inactive) Assignee: Alex Li
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
is depended on by SERVER-66829 Refactor extractHedgeOptions Closed
Operating System: ALL
Sprint: Service Arch 2022-06-27, Service Arch 2022-07-11, Service Arch 2022-07-25
Participants:

 Description   

One can make the case a flat data structure should be declared with all elements already sorted so run-time checks for elements being contained within the list can be optimized. C++20 has isSorted as a constexpr which therefore can be used with static_asserts possibly failing compilation. This is a betterment to writing a comment above the data structure and hoping for the best as non-sorted lists with silently degrade performance or require extra run-time checks or complicated constructs. Here is a proposal for a possible polyfill:

template <typename It>
constexpr bool constexprIsSorted(It b, It e) {
#if __cpp_lib_constexpr_algorithms >= 201806L
    return std::is_sorted(b, e);
#else
    if (b == e)
        return true;
    auto p = b++;
    while (b != e) {
        if (!(*p < *b))
            return false;
        p = b++;
    }
    return true;
#endif
} 

And here's an example on how to use it:

 // Keep this sorted.
constexpr std::array roCmds{
    "collStats"_sd,
    "count"_sd,
    "dataSize"_sd,
    "dbStats"_sd,
    "distinct"_sd,
    "filemd5"_sd,
    "find"_sd,
    "listCollections"_sd,
    "listIndexes"_sd,
    "planCacheListFilters"_sd,
};
 
static_assert(constexprIsSorted(roCmds.begin(), roCmds.end()));
 
bool isReadOnlyCommand(StringData cmd) {
    return std::binary_search(roCmds.begin(), roCmds.end(), cmd);



 Comments   
Comment by Githook User [ 21/Jul/22 ]

Author:

{'name': 'Alex Li', 'email': 'alex.li@mongodb.com', 'username': 'lia394126'}

Message: SERVER-66764 Polyfill C++20 constexpr isSorted
Branch: master
https://github.com/mongodb/mongo/commit/f2fdac7de514b76a1e951bb7c9c12924fe50ac46

Generated at Thu Feb 08 06:06:22 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.