Hello everyone, I apologize that this question is not exactly about libc++, but it is closely related to it.
At work we have to use STL that is used on every OS (MSVC’s STL on Win, libstdc++ on Linux, libc++ on MacOS) for API/ABI compatibility. But we have a problem because some functions like std::sort, std::nth_element are giving slightly different results when used on different platforms, which results in significantly different results of our software. I am totally aware that it is problem of code that is too sensitive to such minor variations, and I am also aware of std::stable_sort existence, but the issue still remains because stable_nth_element does not exists, and for average developer it is not always clear if std::stable_sort should be used in some place where we currently use std::sort.
So my current idea is to “stabilize” implementation across platforms by using libc++ version of algorithms on all STLs, that means that I want to try to extract std::nth_element from libc++, and use it on all platforms and other 2 remaining STL’s instead of the standard versions.
Now the question: Do you think such approach make sense? Maybe you can see some pitfalls? Has anyone done it before and already extracted useful algorithms of libc++ into a separate lib?
You’ve pointed out yourself that you could use std::stable_sort instead of std::sort to fix some of your issues. I would recommend simply using the correct algorithm. I’m not sure what stability you expect from std::nth_element. Maybe std::partial_sort would be the right algorithm? In libc++ we actually reserve the right to change the underlying algorithm, so you definitely shouldn’t rely on how exactly the elements are ordered. You can use _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY to catch such bugs.
I kind of agree with you, but I just want to listen to other people opinions.
Using or not using stable_* algorithms in our case is a complex question. I totally agree that stable_sort must be used when stable order (in mathematical sense) is required, but what if I don’t care about stable ordering in mathematical sense, I only want the order to be the same on all platforms (and of course it has to be sorted, but not necessarily stable sort’ed). The same applies to iteration over std::unordered_set and std::unordered_map. I totally agree that it is a stupid idea to expect any particular order when iterating over these two, but I want the order to be the same on all platforms.
Regarding additional macro - I previously used it on our codebase and it helped me to find a lot of broken compare predicates, so thanks to whoever was involved in adding it.
This still counts as a requirement for a stable order. It’s a requirement across multiple instances of the program rather than one instance, but that’s still a requirement. You need to make your program fulfill that requirement.
I have noticed LLVM developers sometimes changing a container or algorithm in order to produce consistent results over time or across platforms, not because the operation inherently requires consistent results.
Basically you can update your program to use STL calls that guarantee the results you want, or you can update your program to abandon STL and roll your own algorithms/containers to guarantee the results you want.