spinsort and flat_stable_sort don't compile with -fno-exceptions or -fno-operator-names GCC flags about sort HOT 12 OPEN

from sort.

Hey @fjtapia ,
are you willing to accept new contributors? I am interested into contributing to this repository so, if you could explain a bit more this feature request, it would be great.
Thanks

from sort.

I was doing some performance characterisation work recently. I had some difficulty building in gcc --no-exceptions mode due to boost::block_indirect_sort. The workaround for me was to simply comment out the offending try, catch and throws.

But I did also happen across BOOST_NO_EXCEPTIONS and Boost.ThrowException which does seem intended as a way of supporting both with and without exception handling.

There are only 20 or so places in boost::sort throwing exceptions, so seems quite doable to make a change to support BOOST_NO_EXCEPTIONS mode. The performance improvement in my testing amounted to about 2% overall, which isn't so compelling on the face of it. But it does seem like it might be more significant for a different code path and we might like to use --no-exceptions mode, and it would be nice for boost::sort to support that.

I don't think that boost::sort performance would be significantly improved with --no-exceptions directly. But if the rest of the codebase is in C, or not especially exception-happy C++, it could make sense. The other example I came across is spdlog SPDLOG_NO_EXCEPTIONS.

from sort.

from sort.

from sort.

Hi Francisco,

I am not a proponent or advocate of this flag myself. I had tried to use flat_stable_sort() to speed up opening a project in KDevelop, found the missing support a significant obstacle, and so logged this bug. Eventually I had found and switched to timsort(), because it turned out to be much faster than flat_stable_sort() for the KDevelop's use case (flat_stable_sort() had been a strong second-fast sorting algorithm for the use case).

I just searched and found the original proposal and discussion of -fno-operator-names in KDE: https://phabricator.kde.org/D3850. I think the discussion can be summarized like this:

• the flags contradict the C++ standard, so enabling them by default in KDE code is not universally agreed on;
• there is a practical portability benefit (not breaking a MSVC build) of using this flag by default to compile KDE code, because not all KDE projects are regularly compiled on Windows;
• the flag can be overridden for [sub]projects that depend on 3rd-party libraries/headers, which do not compile with it.

from sort.

from sort.

In the KDevelop use case, the elements are relatively expensive to compare and move, and indeed are mostly sorted from the start. So flat_stable_sort() handily outperforms std::stable_sort(), std::sort(), boost::sort::spinsort() and every other sorting algorithm I have tried except for timsort(), which is even more fine-tuned for this specific task.

Thanks for making flat_stable_sort() compile with -fno-exceptions and -fno-operator-names. Now KDE projects can use it without hindrance.

EDIT: reopening the issue because boost::sort::spinsort() does not seem to compile with these flags yet.

from sort.

I think there is fairly strong argument to avoid operator names.

At our organisation they are strongly discouraged. The compiler flags are set accordingly.
Having to manage that for dependencies with other opinions is simply work that needs doing, of no functional or practical value.

Ease of integration with other code bases is a positive, even if it isn't as we'd personally prefer it to be.
Minimise the friction.

from sort.

from sort.

If you could provide me with some information about the type of data to
sort, the size of the data, the number of elements to sort, and approximate
times, I would appreciate it

First of all, timsort() works fast enough that further optimization is not very important to me. So I am not asking you to optimize for my use case :)

I have already described general characteristics of the sorting task. More specifically, the element is a struct that contains: 1) two copy-on-write QVector<QString>s with a custom optimized comparison; 2) an expensive to move/copy but cheap to compare custom KDevelop type. The initial order consists of usually long runs of already sorted elements: paths obtained from a file system API, then inserted into a file-system tree, then appended to a QVector (a Qt class similar to std::vector) via depth-first-search of the tree.

If you need more details, here is the optimizing commit: https://commits.kde.org/kdevelop/09426bcff8060b1b6f1bb450c2ce6595861f3c0f. There are automated KDevelop benchmarks that are affected by the choice of sorting algorithm. But the main criterion of my sorting algorithm selection was manual benchmarking: opening large projects in KDevelop and comparing intrusive QElapsedTimer measurements of the sorting call.

from sort.

from sort.