Releases: Morwenn/cpp-sort
1.15.0 — An Mil
Last weekend I spent a whole day on a reconstituted village from year 1000 (An Mil in French) where a small documentary was shot. It was awesome and gave me enough motivation to finish this release 1.15.0 that spent waaaay too much time in the making.
One of the reasons it took so much time was that I wanted to implement metrics (issue #214) before releasing it and lost all motivation to work on the library whenever I tried to work on metrics. It prevented me from working on algorithm improvements because metrics were supposed to help me better assess said improvements. In the end this release only ships a very basic version of metrics and very few algorithmic improvements - in the future I will most likely only work on them again when I feel like it instead of needlessly blocking releases like I did this time. At the end of the day, it is a hobby project and I can only gather so much motivation.
Deprecations
The following sorters are now deprecated as more generic features have been introduced to replace them:
drop_merge_sorter
: usedrop_merge_adapter
<
pdq_sorter
>
instead.split_sorter
: usesplit_adapter
<
pdq_sorter
>
instead.- [
verge_sorter
][verge-sorter]: use [verge_adapter
][verge-adapter]<
pdq_sorter
>
instead for random-access iterators, orverge_adapter<
quick_merge_sorter
>
for bidirectional iterators. The following composite sorter can be used as a drop-in replacement for the deprecated one:using verge_sorter = cppsort::verge_adapter< cppsort::hybrid_adapter< cppsort::pdq_sorter, cppsort::quick_merge_sorter > >
Deprecated components will be removed in cpp-sort 2.0.0.
Deprecation warnings can be disabled by defining the preprocessor macro CPPSORT_DISABLE_DEPRECATION_WARNINGS
.
New features
Metrics (issue #214)
Metrics are a special kind of sorter adapters that allow to retrieve information about the sorting process such as the number of comparisons performed when a collection is being sorted. This release ships the three following metrics:
cppsort::metrics::comparisons
: number of comparisons performed while sorting.cppsort::metrics::projections
: number of projections performed while sorting.cppsort::metrics::running_time
: time it took to sort the collection.
These adapters return an object of type [cppsort::utility::metric
][utility-metric-tools], which is some kind of tagged value type. metrics::comparisons
supersedes cppsort::counting_adapter
, which will likely be deprecated in a future release.
New sorter: splay_sort
implements splaysort, an adaptive O(n log n) comparison sort based on a splay tree data structure, a special kind of binary tree originally described by D. Sleator and E. Tarjan in Self-Adjusting Binary Search Trees.
The current implementation does not perform exceptionally well according to the benchmarks, though it might be improved in the future.
Support for libassert (experimental)
When the CPPSORT_USE_LIBASSERT
macro is defined - and NDEBUG
is not -, the library's internal assertions and audits use @jeremy-rifkin's libassert instead of the standard library assert
to report failures, allowing better diagnostics in case of failure thanks notably to stack traces, expression decomposition and coloured console diagnostics. The CPPSORT_USE_LIBASSERT
flag can also be passed to CMake.
That support is still experimental and might still contain undiagnosed issues.
Bug fixes
- Fixed construction of
stable_adapter
<
hybrid_adapter<A, B, C>
>
with parameters. Because of an oversight, it could basically only be default-constructed. - Additionally fixed
stable_t
<
hybrid_adapter<A, B, C>
>
:stable_adapter<hybrid_adapter<A, B, C>>::type
existed but could not be constructed from an instance ofhybrid_adapter<A, B, C>
. The::type
shortcut was therefore removed.
Improvements
Algorithmic & speed improvements:
sorting_network_sorter
now handles networks for 33 to 64 inputs. Many thanks @bertdobbelaere for the continued work on sorting networks on which most of this sorter is built.sorting_network_sorter
: sorting 27 inputs now requires 147 compare-exchanges instead of 148 thanks to a new network found by SorterHunter.
Other improvements:
- [
verge_adapter
][verge-adapter] now works on bidirectional iterators. Prior to this release it only accepted random-access iterators. - Defining
CPPSORT_ENABLE_AUDITS
now also automatically definesCPPSORT_ENABLE_ASSERTIONS
. - Fixed a warning that occurred when
CPPSORT_ENABLE_AUDITS
was defined butCPPSORT_ENABLE_ASSERTIONS
wasn't. - Fixed
-Wpessimizing-move
warnings inflip
andnot_fn
with GCC 13. noexcept
was added to several small functions in the library's internal code, occasionally leading to a better codegen.
Tooling
Benchmarks:
- Fixed a mistake that caused a compilation error in small-array benchmark since version 1.14.0.
- The inversions benchmark now uses
heap_sort
,drop_merge_adapter
(heap_sort)
andsplit_adapter
(heap_sort)
, which are more interesting defaults for that benchmark than the previous ones. - Replaced now deprecated [
verge_sort
][verge-sorter] withspin_sort
in patterns benchmark.
Test suite:
- Fixed a bug with some old GCC versions in
constexpr
tests. - Enabled more assertions when building the test suite:
_GLIBCXX_ASSERTIONS
with libstdc++ and_LIBCPP_ENABLE_ASSERTIONS
with libc++. - Bumped downloaded Catch2 version to v3.4.0.
- Do not compile with
-Winline
: the warning was extremely noisy on some platforms yet not really helpful. The library never explicitly tries to inline anything anyway, so the soundness of enabling that warning for the test suite was of debatable soundness.
Miscellaneous:
- Added two new CMake options:
CPPSORT_ENABLE_ASSERTIONS
andCPPSORT_ENABLE_AUDITS
which control whether the macros of the same name are defined. - Added the CMake option
CPPSORT_USE_LIBASSERT
to make assertions and audits use libassert instead of the standard library'sassert
. - Upgraded CI from Ubuntu 18.04 to Ubuntu 20.04. This means that GCC versions older than 7 are not tested anymore.
generate_sorting_network.py
now directly consumes the JSON files from SorterHunter to generate networks.- The whole Conan support was thoroughly updated: the embedded recipe now requires Conan 2.0 to work.
Known bugs
I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.
[uti...
1.14.0 — Tantanmen
I am writing those lines shortly after coming back from the local ramen restaurant, where I had the pleasure to enjoy edamame and tantanmen for the first time in a while. After eight months and and two patch releases, the long-awaited cpp-sort 1.14.0 is finally out. One of the reasons already mentioned in previous release notes is the work on version 2.0.0, which is far from being ready, but already had a positive effect on the overall quality of the library.
Worry not, for this long time spent in the making was not in vain: this version brings more new features to the table than usual with a clear focus on orthogonality, allowing to make the most of existing features. Another highlight of this release is a focus on documentation: I tried to make it more amenable with new power words, a lots of small changes and also a new quickstart page.
New features
New adapters: split_adapter
and drop_merge_adapter
(#148)
[split_adapter
][split-adapter]: the library has shipped [split_sorter
][split-sorter] since version 1.4.0, a sorter base don an algorithm that works by isolating an approximation of a [longest non-decreasing subsequence][longest-increasing-subsequence] in a O(n) pass in the left part of the collection to sort, and the out-of-place elements in the right part of the collection. The right part is then sorted with [pdq_sort
][pdq-sorter], and both parts are merged together to yield a sorted collection.
split_adapter
is basically the same, except that it accepts any bidirectional sorter to replace pdq_sort
in the algorithm. As such it acts as a pre-sorting algorithm that can be plugged on top of any compatible sorter to make it [Rem-adaptive][probe-rem].
[drop_merge_adapter
][drop-merge-adapter]: this is the adapter version of [drop_merge_sorter
][drop-merge-sorter], allowing to pass in any sorter instead of relying on [pdq_sort
][pdq-sorter]. Much like SplitSort, [drop-merge sort][drop-merge-sort] works by isolating out-of-place elements, sorting them with another sorting algorithm, and merging them back together. Unlike SplitSort it places the out-of-place elements in a contiguous memory buffer, allowing to use any sorter to sort them.
While philosophically close from each other, the two algorithms use different heuristics to isolate out-of-place elements, leading to a different behaviour at runtime: for the same fallback algorithm, drop_merge_adapter
is faster than split_sorter
when there are few out-of-place elements in the collection to sort, but becomes slower when the number of out-of-place elements grows.
As can be seen in the benchmarks above, split_adapter
and drop_merge
adapter offer different advantages: split_adapter
takes a bit less advantage of existing presortedness than drop_merge_adapter
, but its cost it very small even when there are lots of inversions. This can be attributed to drop_merge_adapter
allocating memory for the out-of-place elements while split_adapter
does everything in-place.
When sorting a std::list
however, drop_merge_adapter
becomes much more interesting because the allocated memory allows to perform the adapted sort into a contiguous memory buffer, which tends to be faster.
New utilities: sorted_indices
and apply_permutation
(#200)
[utility::sorted_indices
][sorted-indices] is a function object that takes a sorter and returns a new function object. This new function object accepts a collection and returns an std::vector
containing indices of elements of the passed collection. These indices are ordered in such a way that the index at position N in the returned vector corresponds to the index where to find in the original collection the element that would be at position N in the sorted collection. It is quite similar to [numpy.argsort
][numpy-argsort].
std::vector<int> vec = { 6, 4, 2, 1, 8, 7, 0, 9, 5, 3 };
auto get_sorted_indices_for = cppsort::utility::sorted_indices<cppsort::smooth_sorter>{};
auto indices = get_sorted_indices_for(vec);
// Displays 6 3 2 9 1 8 0 5 4 7
for (auto idx: indices) {
std::cout << *it << ' ';
}
[utility::apply_permutation
][apply-permutation] accepts a collection, and permutes it according to a collection of indices in linear time. It can be used together with sorted_indices
to bring a collection in sorted order in two steps. It can even be used to apply the same permutation to several collections, allowing to deal with structure-of-array patterns where the information is split in several collections.
// Names & ages of persons, where the identity of the person is the
// same index in both collections
std::vector<std::string> names = { /* ... */ };
std::vector<int> ages = { /* ... */ };
auto get_sorted_indices_for = cppsort::utility::sorted_indices<cppsort::poplar_sorter>{};
auto indices = get_sorted_indices_for(names); // Get sorted indices to sort by name
// Bring persons in sorted order
cppsort::utility::apply_permutation(names, auto(indices));
cppsort::utility::apply_permutation(ages, indices);
Note the use of C++23 auto()
copy above: apply_permutation
mutates both of the collections it accepts, so the indices have to be copied in order to be reused.
New utilities: sorted_iterators
and indirect
(#42, #200)
[utility::sorted_iterators
][sorted-iterators] is a function object that takes a sorter and returns a new function object. This new function object accepts a collection and returns an std::vector
containing iterators to the passed collection in a sorted order. It can be thought of as a kind of sorted view of the passed collection - as long as said collection does not change. It can be useful when the order of the original collection must be preserved, but operations have to be performed on the sorted collection.
std::list<int> li = { 6, 4, 2, 1, 8, 7, 0, 9, 5, 3 };
auto get_sorted_iterators_for = cppsort::utility::sorted_iterators<cppsort::heap_sorter>{};
const auto iterators = get_sorted_iterators_for(li);
// Displays 0 1 2 3 4 5 6 7 8 9
for (auto it: iterators) {
std::cout << *it << ' ';
}
The new projection [indirect
][utility-functional] dereferences its parameter and returns the result. It can be used together with standard range algorithms to perform operations on the vector of iterators returned by sorted_iterators
.
std::forward_list<int> fli = /* ... */;
auto get_sorted_iterators_for = cppsort::utility::sorted_iterators<cppsort::poplar_sorter>{};
const auto iterators = get_sorted_iterators_for(fli);
auto equal_bounds = std::ranges::equal_range(iterators, 42, {}, cppsort::utility::indirect{});
New sorter: d_ary_heap_sorter
[d_ary_heap_sorter
][d-ary-heap-sorter] implements a heapsort variant based on a [d-ary heap][d-ary-heap], a heap where each node has D children - instead of 2 for a binary heap. This number of children nodes can be passed as an integer template parameter to the sorter and its associated sort function. Storing more nodes makes the algorithm a bit more complicated but improves the locality of reference, which can affect execution speed.
std::vector<int> vec = { /* ... */ };
cppsort::d_ary_heap_sort<4>(vec); // d=4
The complexity is the same as that of the library's [heap_sorter
][heap-sorter]. It is however worth nothing that unlike its binary counterpart, d_ary_heap_sorter
does not implement a bottom-up node searching strategy.
The benchmark above shows how the value picked for D might influence the speed of the algorithm. It also shows that [d_ary_heap_sort
][d-ary-heap-sorter] is currently much slower than [heap_sort
][heap-sorter], though the former is not really optimized and has room for improvements.
Bug fixes
- Fixed [
slab_sort
][slab-sorter] when sorting collections where several elements compare equivalent to the median element (#211). - Fixed a potential use-after-move bug in [
quick_merge_sort
][quick-merge-sorter].
Improvements
Algorithmic & speed improvements:
- [
slab_sort
][slab-sorter] now falls back to using insertion sort on small enough collections in its melsort pass. This change leads to speed improvements when sorting shuffled data that does not exhibit obvious patterns.
- [
low_moves_sorter<n>
][low-moves-sorter]: removed O(n) comparisons in the generic case.
Other improvements:
- Add more [audit assertions][assertions-audits] around some internal merge operations. Audits are expensive assertions which can be enabled by defining the preprocessor macro
CPPSORT_ENABLE_AUDITS
. - When
CPPSORT_ENABLE_AUDITS
is defined, the library's internal assumptions (e.g.__builtin_assume
) are now turned into assertions, providing additional checks to diagnose errors. - `schwarz_adapter<schwarz_adapter...
1.13.2 — Sword Search
This release is named after the eponymous song in the OST of The Legend of Zelda: Link's Awakening. This theme, following you for a short time at the very beginning of the game, never fails to haunt me and put me in a nostalgic mood, be it the original, the Switch remake or fan remakes. It's like the mood, the feels, the adventure are all still there deep down somewhere and forever.
This is the first cpp-sort version benefiting of a second patch release for a simple reason: I just made the library compatible with clang-cl. For those who don't know, clang-cl is a Clang fronted on MSVC, which also has the particularity of using the Microsoft STL instead of libc++. I only tested clang-cl recently, but I believe it worked in version 1.13.0 and I introduced a small change that broke it in version 1.13.0, hence a new patch version to fix that and introduce official support for this target.
Changes
No new features or algorithmic changes, this release is all about tooling:
- Make the test suite pass with clang-cl (#208). There are still lots of warnings, but they are mostly noise.
- Add clang-cl to continuous integration. Currently only the Debug mode is tested with clang-cl in the CI: the Release mode crashes due to what I think is an out-of-memory error in the VM, but I did compile & run it locally and it worked correctly.
- Improve
std::identity
detection with Clang and clang-cl in C++20 mode. - Add a Python script to the
tools
folder to make it easier to change the version number where needed before a release. - Make
conanfile.py
more compatible with Conan 2.0. It now requires at least Conan 1.50.0 to work.
Known bugs
I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.
1.13.1 — Find Her
This release is named after Easily Embarrassed's critically underrated Find Her, a great mix of bounce, crispy synths and glitchy sounds. It seems that I can't ever get bored of it.
I haven't taken the time to work a lot on cpp-sort lately, which called for at least a small release with the available bug fixes and quality of life changes. While remaining mostly a quality-of-life release, it eventually turned out to be bigger than expected, mostly due to the ongoing work the future version 2.0.0 of the library and the resulting refactors and backports.
The most notable changes are the algorithmic improvements mentioned in the corresponding section of this note, and the addition of a page explaining how to write a sorter adapter to the documentation.
Bug fixes
- Fix
iter_move
anditer_swap
when the library is compiled with C++20. The standard perimeter changed a bit in this area, and caused some ambiguous overload errors when the compiler couldn't decide which overload to pick between the standard library ones and thecppsort::utility::
ones. The standard library ones are now preferred for standard types when they exist. <cpp-sort/sorters/spreadsort/string_spread_sorter.h>
could not be included alone due to a missing include. This is now fixed.- Fix a bug where
make_projection_compare
failed to compile when passed an instance ofstd::identity
in C++20 mode. Introduced in version 1.13.0, this bug could cause issues when passingstd::identity
to sorters relying onsorter_facade
to provide projection support, such asstd_sorter
.// Error in 1.13.0, works in 1.13.1 cppsort::std_sort(collection, std::greater{}, std::identity{});
Improvements
Algorithmic & speed improvements:
- Update
heap_sort
from upstream (we use the libc++ implementation): the new implementations turns it into a bottom-up heapsort. It performs fewer comparisons than the previous implementation, which doesn't make a noticeable difference from a speed point of view when comparisons are cheap, but can be much more noticeable when comparisons are expensive. This new implementation can be slower in the expensive moves/cheap comparisons scenario.
- The fallback of
quick_merge_sort
for forward iterators when sorting just a few elements was changed from bubble sort to selection sort after I was reminded of the fact thatquick_merge_sort
was not a stable sort anyway and could therefore switch to a better unstable fallback algorithm for very small collections.
string_spread_sort
was changed to perform fewer projections, sometimes halving the total number of performed projections.
- The library's internal adaptive quickselect implementation was tweaked to perform fewer projections. As a result the following sorters perform up to 1% fewer projections when operating on random-access iterators:
- MSVC STL SIMD algorithms are now used when possible, which might marginally impact the following components for random-access iterators:
Improvements to sorting networks:
- All sorting networks used by
sorting_network_sorter
are now formally verified. - Regenerate all
sorting_network_sorter
specializations with the smallest networks from this list. The main resulting change is that sorting 25 inputs is now done with 130 compare-exchanges instead of 131. - All specializations of
sorting_network_sorter
now have theirindex_pairs()
function marked as[[nodiscard]]
when possible.
Other improvements:
- Total, weak and partial order comparators now support
__int128_t
and__uint128_t
. hybrid_adapter
is now fullyconstexpr
when the sorters it wraps are themselvesconstexpr
(#58).
Tooling
- Add a tutorial to the documentation explaining how to write a sorter adapter with a simple example (issue #154).
- Various smaller changes to improve the overall quality of the documentation.
- The required and downloaded Catch2 version is now v3.1.0.
- The
generate.py
from thetools
directory was changed by a more completegenerate_sorting_network.py
tool which formally verifies that a given sorting network works, then generates the correspondingsorting_network_sorter
. dist::as_long_string
in the benchmarking tools now inherits fromutility::projection_base
and itsoperator()
isconst
.- Continuous integration: update scripts to use actions/checkout v3.
- The configurations tested by the CI change depending on which tools are available in the CI environments.
Known bugs
I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.
1.13.0 — Swimming Pool
A few days ago I went to the swimming pool for the first time since 2015, which might also be the first time since the very first cpp-sort commits. The library is getting old, and while it might be too late to give it a cute name, it is still time to give it a cute logo.
This release focuses on improving the state of function objects in the library in a somewhat holistic way, notably with the addition of flip
and not_fn
, but also with smaller changes:
- Many more function objects are now transparent or conditionally transparent.
- Several function objects that except a single parameter now inherit from
projection_base
, which makes them more easily chainable. - Some comparator adapters were updated to automatically unwrap upon recognizing specific function objects, allowing to reduce template nesting and instantiations.
- The documentation about function objects and related concepts was improved.
New features
New comparator adapters not_fn
and flip
. The former is equivalent to the C++17 std::not_fn
: it takes a comparator and returns a function object of type not_fn_t<F>
whose call operator calls the adapted comparator and returns the negation of its result. The latter is named after the flip
function from Haskell's Prelude module: it takes a comparator and returns a function object of type flip_t<F>
whose call opearator calls the adapted comparator with its arguments flipped. Here is an example of them being used to reimplement std::upper_bound
in terms of std::lower_bound
:
template<typename ForwardIt, typename T, typename Compare>
auto upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
-> ForwardIt
{
return std::lower_bound(
first, last, value,
cppsort::not_fn(cppsort::flip(comp))
);
}
The function templates flip
and not_fn
recognize and unwrap some combinations of flip_t
, not_fn_t
and other "vocabulary types" in function objects. For example flip(flip(std::less{}))
returns an instance of std::less<>
instead of flip_t<flip_t<std::less<>>>
. The goal is to reduce the nesting of templates as well as the number of templates instantiated by the library — which is especially interesting considering that many of the library's internal functions rely on flip
and not_fn
.
New sorter: adaptive_shivers_sort
, a k-aware natural mergesort described by Vincent Jugé in Adaptive Shivers Sort: An Alternative Sorting Algorithm. It is very similar to tim_sort
and actually shares most of its code. Adaptive ShiversSort worst case notably performs 33% fewer comparisons that timsort's worse case.
Bug fixes
- When wrapping a non-comparison sorter that accepts projections (such as
spread_sorter
),indirect_adapter
failed to compile if passed a projection but no comparison (issue #204, thanks to @marc1uk for reporting).
Improvements
sorting_network_sorter
now uses one fewer compare-exchange than previously for 21, 22, 23, 25, 27 and 29 inputs thanks to the latest results of SorterHunter.- The following function objects from
<cpp-sort/utility/functional.h>
are now unconditionally transparent and inherit fromprojection_base
:utility::half
utility::log
utility::sqrt
- The objects returned by
as_comparison
andas_projection
as well as the result of chained projections are now transparent when their parameters are also transparent. - The objects returned by
make_projection_compare
,as_comparison
andas_projection
are now default-constructible when the adapted function objects are default-constructible. make_projection_compare
now returns the passed comparison directly when the passed projection isstd::identity
orutility::identity
. This change can help to reduce the number of template instantiations in generic code. This is potentially a minor breaking change.- Silence a
-Wunused-but-set-variable
false positive inpdq_sorter
which fired with some versions of MinGW-w64.
Tooling
Documentation:
- The documentation now uses relative links when linking to its own pages instead of absolute links to the online wiki. This makes the documentation more easily browsable in the GitHub repository interface at any point in time.
- It is also now browsable offline with Gollum (issue #198). A new section of the documentation explains how to do it.
- Update the documentation about comparators, create a dedicated page comparator adapters.
- Add a section explaining what transparent function objects are.
Test suite:
- Rename the test suite directory from
testsuite
totests
, in accordance with the Pitchfork project layout. - Upgrade Catch2 to v3-preview4.
- New CMake option
CPPSORT_STATIC_TESTS
: whenON
some tests are turned intostatic_assert
and are reported as success if the program compiles. The option defaults toOFF
. - New wiki section to document the concept of transparent function objects.
- Give the
[comparison]
tag to more tests, unify similar tags. - Move
every_sorter_*
tests from the root of the test suite to thesorters
subdirectory.
Miscellaneous:
- The project layout is now fully compatible with the Pitchfork project layout.
- Bump codecov-action to v3.
- The action to deploy the documentation to the wiki was updated to stop relying on the unmaintained SwiftDocOrg/github-wiki-publish-action.
Known bugs
I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.
1.12.1 — Till It's Over
This release is named after Tristam's timeless glitch hop classic Till It's Over, which is always a favourite of mine when I want to be pumped up while programming — or doing anything else, really.
This end-of-the year release mostly fixes bugs and warnings, but also delivers a few small improvements to the library and its tooling that were ready and unlikely to cause issues. Notably sorters and adapters should now be able to handle some iterators even when they define a difference_type
smaller than int
.
Bug fixes
counting_sorter
::iterator_category
andcounting_sorter::is_always_stable
were accidentally unavailable since version 1.9.0 unless__cpp_lib_ranges
was defined. They are now unconditionally available again.- Due to a missing
using
declaration,slab_sort
only compiled for iterators with an ADL-founditer_swap
. - Fix compile time error in
quick_sort
when the passed iterators have adifference_type
smaller thanint
.
Improvements
slab_sort
now works with bidirectional iterators.drop_merge_sort
does not need to compute the size of the collection anymore, which saves a full pass over the collection to sort when with bidirectional iterators.- Reduce the number of memory allocations performed by
spin_sort
. utility::size
now also works with collections that only provide non-const
begin()
andend()
functions.- Fix warnings in the following sorters due to integer promotion issues when the passed iterators have a
difference_type
smaller thanint
:
Tooling
- Rollback changes to the patterns benchmark accidentally committed in version 1.12.0.
- Rewrite large parts of the bubble sort tutorial.
- Test sorters and adapters with an iterator type for which
difference_type = std::int8_t
.
Known bugs
I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.
1.12.0 — Fitness
To my utmost surprise, my life has recently taken a weird turn where I'm doing more fitness-related activities than I thought I would ever do: muscle-strengthening and stretching on a regular basis, and I even started to play badminton again after a 12-year hiatus. My self from three years ago would probably call me a liar while reading those lines. Life can be weird, eh... Anyway, it's still leaving me enough time to work on cpp-sort and to release new versions.
One of the main highlights of this release is the improved support for [measures of presortedness][mops]: one was added, one was deprecated, and several were improved. As a result, all of the library's measures of presortedness run in O(n log n) or better — save for a deprecated O(n²) that will be removed in the future.
Much effort went into improving the overall library quality: bug fixes, consistency fixes, binary size improvements, better tooling and documentation, etc. One of the biggest items was the switch from [GCOV][gcov] to [LCOV][lcov] as a code coverage engine: it actually reports a correct line coverage while I never managed to get GCOV to show all the lines that were actually covered by the test suite. As a result the library's line coverage is now over 90% and it will now be easier to cover the missing parts.
One of the smaller features that got some library-wide attention is the handling of stable sorting: several bugs were fixed, and a few parts of the library were changed to ensure that stable_t
would do a better job at "unwrapping" stable_adapter
. These changes caused a few minor breaking changes, which should however not be issues when the library features are used correctly. [The documentation][stable-adapter] was also updated to better explain the logic behind stable_t
and stable_adapter
(with graphs) and to clarify the expectations around the related type traits.
Deprecations
[probe::par
][probe-par]
Right invariant metrics and measures of presortedness by V. Estivill-Castro, H. Mannila and D. Wood mentions that:
In fact, Par(X) = Dis(X), for all X.
After checking, it appeared that [probe::dis
][probe-dis] and [probe::par
][probe-par] indeed both returned the same result for the same input. The authors of Par stopped using Par in their subsequent publications and preferred using Dis instead, so we follow suit and deprecate probe::par
accordingly since it is redundant with probe::dis
. It will be removed in version 2.0.0.
[probe::osc
][probe-osc] O(n²) fallback
The measure of presortedness [probe::osc
][probe-osc] was improved to run in O(n log n) time and O(n) space instead of O(n²) time and O(1). The old algorithm is still used as a fallback when there isn't enough memory available - to avoid breaking backward compatibility -, but that fallback is deprecated and will be removed in version 2.0.0.
The rationale is that we don't want to keep quadratic algorithms around without a good reason. Measures of presortedness are first and foremost (expensive) diagnostic tools, and as such they aren't expected to run on resource-constrained environments. It makes sense to expect extra memory to be available when suing such tools.
Deprecation warnings can be disabled by defining the preprocessor macro [CPPSORT_DISABLE_DEPRECATION_WARNINGS
][deprecation-warnings].
New features
New measure of presortedness: [probe::block
][probe-block]: it implements Block(X) — described by S. Carlsson, C. Levcopoulos and O. Petersson in Sublinear Merging and Natural Mergesort —, slightly modified so that to handle equivalent elements correctly and in a way that makes it a correct measure of presortedness according to the formal definition given by Mannila. Block(X) corresponds to the number of elements in X sequence that aren't followed by the same element in the sorted permutation of X. Its worst case returns |X| - 1 when X is sorted in reverse order.
Bug fixes
- Not all comparisons in [
probe::osc
][probe-osc] were performed with the provided comparator, which could lead to compile-time or runtime errors. - Fixed an issue where [
merge_insertion_sort
][merge-insertion-sorter] and [slab_sort
][slab-sorter] produced a memory error (caught by Valgrind and address sanitizer) when called on an empty collection (issue #194). - [
stable_adapter<T>
][stable-adapter] did not support construction fromT
whenT
was one of the following types (which was not consistent with the other specializations):default_sorter
- [
stable_adapter
][stable-adapter]
- [
stable_adapter
][stable-adapter]<
default_sorter
>::type
now aliasesstable_adapter<default_sorter>
instead of [merge_sorter
][merge-sorter]. This is technically a minor breaking change, butstable_adapter<T>::type
is supposed to be constructible fromT
so the new behavior is correct. - Since their last rewrite in version 1.9.0, [
verge_sorter
][verge-sorter] and [verge_adapter
][verge-adapter] always used their stable algorithm, even when they weren't wrapped in [stable_adapter
][stable-adapter]. That was an accident, and they now use the unstable algorithm by default, as they should have done.
Improvements
- [
probe::dis
][probe-dis] now runs in O(n log n) time and O(1) space. When sorting bidirectional iterators, if enough heap memory is available, it uses an O(n) time O(n) space algorithm described by T. Altman and Y. Igarashi in Roughly Sorting: Sequential and Parallel Approach. - [
probe::par
][probe-par] is now a deprecated alias for [probe::dis
][probe-dis] and thus benefits from the same improvements. - [
probe::osc
][probe-osc] now runs in O(n log n) time and O(n) space. The old algorithm that ran in O(n²) time and O(1) is still used as a fallback when not enough memory is available, but it is deprecated and will be removed in a future breaking version. Thanks a lot to @Control55 from @The-Studio-Discord for coming up with the algorithm. - [
stable_t<Sorter>
][stable-adapter] now usesSorter::type
when it exists andSorter
is astable_adapter
specialization. - [
stable_adapter<Sorter>::type
][stable-adapter] now does a better unwrapping job whenSorter
is itself astable_adapter
specialization. - [
sorter_traits
][sorter-traits] now has a partial specialization for [stable_adapter
][stable-adapter] whereis_always_stable
always aliasesstd::true_type
. It was introduced to defensively enforce this contract on user specializations ofstable_adapter
. - Some work was done to reduce the size of the binary bloat in various places, with additional small gains in C++17. It is mostly noticeable when the same components are instantiated for different types of collections.
- Reduce recursion in the implementation of [
quick_merge_sort
][quick-merge-sorter] for forward and bidirectional iterators.
Tooling
Documentation:
- The documentation about measures of presortedness was reworked and improved a bit. A new section describes some measures of presortedness that appear in the literature but don't explicitly appear in the library.
- Improve the documentation for [
stable_adapter
][stable-adapter] and related feature. Add graphs to visually explain the logic behind them. - Rewrite parts of the documentation about [
sorter_traits
][sorter-traits] and related features. Make some usage expectations clearer. - Fix broken links and Markdown errors.
Test suite:
- WARNING: several changes affect random number generation in the test suite. As a result, errors encountered when running the test suite with specific seeds prior to this release might not be reproduced with new versions of the test suite.
- Bump downloaded Catch2 version to v2.13.7.
- Fix segfaults that occurred when running the memory exhaustion tests with some versions of MinGW-w64.
- Fix some
-Winline
warnings with GCC and MinGW-w64. - Fix
/W2
conversion warnings with MSVC. - Test more documented relations between measures of presortedness.
- Add more tests to improve coverage.
- The parts of the test suite that used random numbers have been updated to use less memory at runtime.
- Greatly reduce the number of
thread_local
pseudo-random engines instantiated by the test suite.
Code coverage:
- Use [LCOV][lcov] instead of [gcov][gcov] in the coverage GitHub Action, which seems to better represent what was really executed, and brings the coverage to more than 90%.
- Bump
codecov/codecov-action
tov2
. - Update the embedded CMake-codecov scripts, which notably makes code coverage work with MinGW-w64.
- Move
codecov.yml
to.github/.codecov.yml
to reduce the number of files at the root of the project. - More small tweaks and fixes to the coverage handling in the test suite's
CMakeLists.txt
and in the GitHub Action.
Miscellaneous:
- GitHub Actions: bump the Ubuntu version from 16.04 to 18.04.
- GitHub Actions: fix the Ubuntu job so that it actually shows the Valgrind logs when a Valgrind jobs fails.
- GitHub Actions: run CTest with
--no-tests=error
because no tests run by the test suite is always an error. - Fix includes in benchmarks to work out-of-the-box.
- Simplify the example in the README a bit, and add it to the
examples
directory.
Known bugs
I didn't manage to fix every bug I could find since the previous release, so you might want to check the [list of known bugs][known-bugs].
1.11.0 — Heatwave
I am writing those release notes in the middle of a heatwave — 32°C, you might laugh but I live in a region where that's unusually high enough for AC and fans to be uncommon around here —, which means that my brain is too confused to think of a better name or of anything else for what it's worth.
The biggest features in this release are the addition of several tools to create and manipulate sorting networks, including two new fixed-size sorters implementing specific sorting network algorithms. The rest is mostly the usual smaller improvements, bug fixes and all those things that are needed to improve the overall quality of the project.
Deprecations
block_sort
is now deprecated and will fire a deprecation warning if used. It will be removed in cpp-sort 2.0.0. [wiki_sort
][wiki-sorter] was added to the library to replace it.
Block sort is not a single sorting algorithm, but a whole family of sorting algorithms that shift blocks to sort a collection. Those algorithms are often in-place stable comparison sorts. cpp-sort provides two such algorithms: [WikiSort][wikisort] and grail_sort
. However WikiSort used the general name block_sort
, which seemed more and more unclear and unfair as years went on, especially when considering that new block sorts have been implemented in the recent years, and more are being worked on.
Deprecation warnings can be disabled by defining the preprocessor macro CPPSORT_DISABLE_DEPRECATION_WARNINGS
.
New features
This release adds several new features related to [sorting networks][sorting-network]. The goals are to start completing the library's collection of fixed-size sorters based on sorting networks, and to provide new user-facing tools that make manipulating and creating sorting networks easier.
New header [<cpp-sort/utility/sorting_network.h>
][utility-sorting-network]
This new utility header will contain all generic tools related to sorting networks specifically. It contains the following vocabulary type:
template<typename IndexType>
struct index_pair
{
IndexType first, second;
};
Sorting networks work by performing a fixed sequence of compare-exchange operations on pairs of elements in the collection to sort. index_pair
represents the pair of indices used to access the elements on which a compare-exchange operation will be performed. There is an implicit assumption that first < second
, but it is never checked by the library. Currently the vocabulary type to represent a sequence of compare-exchange operations is [std::array
][std-array]<index_pair<IndexType>, N>
.
This new header also contains the function templates swap_index_pairs
and swap_index_pairs_force_unroll
, which accept an iterator to the beginning of a random-access collection and an std::array<index_pair<IndexType>, N>
. Both functions use the index pairs to perform compare-exchange operations on the collection - effectively applying operations like a comparator network. The former simply loops over the index pairs while the second is a best effort function that tries its best to unroll the loop.
[sorting_network_sorter
][sorting-network-sorter]::index_pairs()
All sorting_network_sorter
specializations got a new index_pairs() static
member function with the following signature:
template<typename DifferenceType=std::ptrdiff_t>
static constexpr auto index_pairs()
-> std::array<index_pair<DifferenceType>, /* Number of CEs in the network */>;
It returns the sequence of compare-exchange operations used by a network to sort its inputs. It builds upon the features introduced in the previous section.
merge_exchange_network_sorter
and [odd_even_merge_network_sorter
][odd-even-merge-network-sorter]
Those new fixed-size sorters are sorting networks that implement two variations of [Batcher odd-even mergesort][odd-even-mergesort], an algorithm that halves the collection to sort, sorts both halves recursively then merges them. The former halves the input by considering that the first half is on the even lanes of the network and the second half on the odd lanes. The latter consider that the first half is on the first N/2 lanes of the network, and the second half is on the last N/2 lanes. Both are pretty similar and interchangeable in most scenarios.
Both provide a static index_pairs()
method similar to the one described in the previous section.
Bug fixes
- If
container_aware_adapter
<
insertion_sorter
>
worked at all when sorting an [std::forward_list
][std-forward-list], it was purely accidental prior to this release: that's how bugged it was. Now it should be fixed, and way faster than it used to be when it accidentally worked. - Fix a potential bug in
cartesian_tree_sorter
: when an exception was thrown during the construction of the Cartesian tree, the algorithm would try to destroy elements that had not been constructed yet. - Fix potential use-after-move issues in [
stable_adapter
][stable-adapter].
Improvements
- The [conversion to function pointer operators][sorter-facade-fptr-conversion] of
sorter_facade
were improved to allow sorters to be converted to function pointers returningvoid
regardless of the type they're supposed to return. In such a case, any value returned by the sorter is ignored/discarded. This allows to pass some sorters to functions expecting avoid
-returning function, or to more easily store sorters into arrays as function pointers no matter their return type:Those conversions still don't work with MSVC (see issue #185).using sort_t = void(*)(std::vector<int>&); sort_t available_sorters[] = { cppsort::merge_sort, cppsort::quick_sort, cppsort::counting_adapter(cppsort::poplar_sort) }
container_aware_adapter
<
insertion_sorter
>
is now around 50% faster in benchmarks when sorting an [std::list
][std-list].
- [
probe::enc
][probe-enc] is now up to 40% faster for small types when the comparison and projection are considered likely branchless. This improvement is thanks to a variation on binary search proposed by @scandum called monobound binary search.
cartesian_tree_sort
now also works with forward and bidirectional iterators.- Fix a warning about
[[nodiscard]]
when usingmel_sort
. - Fix a warning about a unused
typedef
which fired when compilingcontainer_aware_adapter
<
mel_sorter
>
with Clang. - Reduce a bit the memory use of
mel_sort
(up tosizeof(T) * n/2
less memory is allocated).
Tooling
Benchmarks:
- Add
dist::as_long_string
function object to turn along long int
into a [std::string
][std-string] of 50 characters whose last characters are the digits of thelong long int
; this allows to use all the existing distributions to create strings. The big sequence of equal characters at the beginning of the strings make the comparisons expensive, which is a benchmarking category that was often overlooked up to now. - The visualization part of the patterns benchmark now accepts an
--errorbars
option to display the standard deviation. - Add "lower is better" indications on the relevant axis of the benchmark plots to make them more easily understandable (the graphs in these release notes predate that change, sorry about that).
Documentation:
- Give a formula to compute the number of compare-exchanges performed by a hypothetical merging network based on repeated half-cleaner networks.
Test suite:
- Bump downloaded Catch2 version to v2.13.6.
Miscellaneous:
- Conan integration: fix test when cross-building in
test_package
.
Known bugs
I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.
...
1.10.0 — Dreams
Here comes a new release after merely two months, making it the minor version of the library with the shortest development cycle so far. I haven't done anything super interesting recently so that release name is dedicated to all the dreams I've written down since the beginning of the pandemic, mostly adventures, improbably situations and lots of fun — it's nice being able to live adventures in my dreams when every day life is slow. Speaking of fun: it was pretty much the leading force behind this release, which was reified as one new measure of presortedness and three new sorters, mostly implemented after research papers from the 80s and 90s.
One of the most important (but not fun) changes is that cpp-sort now works with MSVC 2019 (only with /permissive-
): the compiler front-end evolved sufficiently to compile most of the library, so I decided to change the library where needed to fully support it — which also allowed to fix small bugs in several parts of the library, improving its overall quality. The only big feature that still doesn't work is the ability to convert a sorter to a variety of function pointers (issue #185).
New features
New sorters: one of the goals of this release was to be fun, and what's more fun than implementing unknown algorithms from old research papers without having to care about them being the fastest in the land? This release adds several new sorting algorithms, mostly found in the literature about adaptive sorting from the 80s and 90s. On average those new algorithms are adaptive, but slow and impractical for most real world use. However their inclusion in the library means that they now have an open-source implementation, which is always something valuable.
cartesian_tree_sorter
: it implements a Cartesian tree sort, an Osc-adaptive comparison sort introduced by C. Levcopoulos and O. Petersson in Heapsort - Adapted for Presorted Files under the name maxtree-sort. The algorithm uses a Cartesian tree and a heap to sort a collection.mel_sorter
: it implements melsort, an Enc-adaptive comparison sort described by S. Skiena in Encroaching lists as a measure of presortedness. It works by creating encroaching lists with the elements of the collection to sort then merging them. When used together withcontainer_aware_adapter
,mel_sorter
provides specific algorithms for [std::list
][std-list] and [std::forward_list
][std-forward-list] than run in O(sqrt n) extra memory instead of O(n).slab_sorter
: it implements slabsort, an SMS-adaptive comparison sort described by C. Levcopoulos and O. Petersson in Sorting Shuffled Monotone Sequences. The algorithm builds upon the adaptiveness of melsort to take advantage of even more existing presortedness in sequences to sort.
Measures of presortedness (MOPs): the literature about adaptive sorting is also about MOPs, so those were given some love for the first time in a while:
- New MOP
probe::sus
which implements SUS(X) as described by Levcopoulos and Petersson in Sorting Shuffled Monotone Sequences. It computes the minimum number of non-decreasing subsequences (of possibly not adjacent elements) into which X can be partitioned. It happens to correspond to the size of the longest decreasing subsequence of X. Its worst case returns n - 1 when X is sorted in reverse order. - MOPs now all have a static
max_for_size
function which takes a size and returns the maximum value that the MOP can return for the given size. This helps to give a better scale for how much presortedness represents the value returned by a specific MOP.
More constexpr
: this release also brings very basic constexpr
support to some of the library's building blocks: sorter_facade
, iter_move
and iter_swap
. None of the library's sorters or sorter adapters have been updated to work in a constexpr
context (this would require C++17/C++20 library features, or reinventing the wheel again), but these changes mean that it is possible for a user to write a constexpr
-friendly sorter implementation, wrap it with sorter_facade
, and get a - mostly - constexpr
sorter ("mostly" because the ranges overload require C++17 features to work in a constexpr
context). More comprehensive constexpr
support is planned for a future 2.0.0 release (see issue #58).
Bug fixes
- Fix out-of-bounds iterator issue in
merge_insertion_sorter
(issue #182). - Fix out-of-bounds iterator issues in
grail_sort
(issue #183). - Fix incorrect destruction of some elements in
merge_insertion_sorter
(issue #184). - Fix integer overflows in the branchless partitioning algorithm of
pdq_sort
(see upstream issue orlp/pdqsort#13), potentialy affecting all of the library components that rely on it. - Fix a rather obscure issue potentially affecting
projection_compare
, [stable_adapter
][stable-adapter] and [std_sorter
][std-sorter], as well ascontainer_aware_adapter
<
merge_sorter
>
when used for [std::list
][std-list] or [std::forward_list
][std-forward-list] (issue #139, huge thanks to @sehe for debugging that one). - Fix the check for [
std::identity
][std-identity] with libstdc++. - The check for [
std::identity
][std-identity] now works on non-Clang non-GCC compilers. - Calls to [
std::min
][std-min] and [std::max
][std-max] are now consistently wrapped in parenthesis to avoid clashes with popularmin()
andmax()
macros.
Improvements
- The [conversion][sorter-facade-fptr-conversion] from a sorter to a function pointer is now unconditionally
constexpr
(it used to only beconstexpr
in C++17 mode and later). - Change
grail_sort
to usedifference_type
instead ofint
wherever it matters in its implementation. It solves some conversion warnings, and might even solve potential overflow issues with big collections. - Silence several conversion warnings.
probe::enc
now performs up to 40% fewer comparisons.- Reduce the number of allocations performed by
merge_insertion_sorter
. This doesn't affect its speed nor its memory complexity.
Tooling
Benchmarks:
- The distributions are now constructed with a
long long int
instead of asize_t
. - Change the default patterns in the patterns benchmark.
Documentation:
- Complete the introduction about MOPs, add a graph showing the partial ordering for MOPs.
- Remove mentions of Bintray.
Test suite:
- Test that all sorters handle projections returning an rvalue.
- Add minimal to check that sorters behave correctly when a move operation throws.
- Test that all MOPs return 0 when given a collection of equivalent values.
- Test more relations between MOPs described in the literature.
- Remove
alternating_16_values
tests, they never gave results significantly different fromshuffled_16_values
. - The distributions are now constructed with a
long long int
instead of asize_t
. - The whole test suite was successfully compiled and executed with
-no-rtti
.
Miscellaneous:
- Add MSVC 2019 builds to the continuous integration.
- The minimal supported Conan version is now 1.32.0.
- The configuration checks in
conanfile.py
were moved fromconfigure()
tovalidate()
. - No more
@morwenn/stable
packages on Bintray: JFrog is sunsetting Bintray. Only the Conan Center packages will be updated from now on. - Tweak
tools/test_failing_sorter.cpp
to make it more useful.
Known bugs
I didn't manage to fix every bug I could find since the previous release, so you might want to check the list of known bugs.
1.9.0 — Windbelt
I kind of managed to turn the current pandemic, lockdowns and even general stay-at-home endeavours without an explicit lockdown into opportunities to work on several side projects — this is already the third cpp-sort release whose name is directly inspired by those side projects, which somehow means a lot. A windbelt is a small device used to harvest wind energy and turn it into electricity, generally a rather cheap DIY project since the required components can often be found around the house. I just finished mine, and even though I still need to test it it's as good as anything for a release name.
This release continues to pave the road to the future breaking 2.0.0 version of the library, even though it always seems to draw further away — there will definitely be more 1.x.y versions. As a result this release brings a few deprecations, polishing of existing features, and initial support for some C++20 features. One of the big items was also the move of the whole continuous integration from Travis CI to GitHub Actions.
Deprecations
All of the following CMake configuration variables and options are deprecated:
BUILD_EXAMPLES
ENABLE_COVERAGE
SANITIZE
USE_VALGRIND
Equivalent options prefixed with CPPSORT_
have been added to replace them. For backwards compatibility reasons, the new options default to the values of the equivalent deprecated variables.
New features
Some limited C++20 support was added to the library:
- When available, [
std::identity
][std-identity] can be used wherever [utility::identity
][utility-identity] can be used, including in the places where the latter is used as a "joker". In the future 2.0.0 version of the library,std::identity
will entirely replaceutility::identity
(issue #130). - When available, [
std::ranges::less
][std-ranges-less] and [std::ranges::greater
][std-ranges-greater] can be used wherever [std::less<>
][std-less-void] and [std::greater<>
][std-greater-void] can be used, including in the places where the latter is used as a "joker". In the future 2.0.0 version of the library,std::less<>
andstd::greater<>
will remain the main vocabulary types because they are less constrained that their new counterparts (issue #130).
Other new features:
- [
stable_adapter
][stable-adapter] and its specializations might define a member type namedtype
: this type should be an alias to the "least nested" sorter with the same behaviour as thestable_adapter
specialization which is guaranteed to always be stable - it can be thestable_adapter
specialization itself. - A new [
stable_t
][stable-adapter] alias template is available when including<cpp-sort/adapters/stable_adapter.h>
. This alias takes a sorter template parameter and aliases a possibly adapted sorter which is always stable. It is meant to replacestable_adapter
when the goal is to take any sorter and to get a stable sorter (stable_adapter
remains the customization point). One of the goals is to reduce template nesting when possible, with the hope that it leads to better diagnostics and smaller template stack traces. For a given sorterSorter
,stable_t<Sorter>
will follow these rules:- If [
cppsort::is_always_stable_v<Sorter>
][is-always-stable] istrue
, thenstable_t
aliasesSorter
. - Otherwise if
stable_adapter<Sorter>::type
exists, thenstable_t
aliases it. - Otherwise
stable_t
aliasesstable_adapter<Sorter>
.
- If [
- A new comparator [
projection_compare
][projection-compare] can be used to embed both a comparison and a projection into a single comparison object, allowing to easily use projections with algorithms that don't support them explicitly:// Sort a family from older to younger member std::vector<Person> family = { /* ... */ }; std::sort(family.begin(), family.end(), cppsort::make_projection_compare(std::greater<>{}, &Person::age));
- A new [
CPPSORT_ENABLE_AUDITS
][assertions-audits] macro can be defined to enable library audits. These audits are assertions too expensive to enable withCPPSORT_ENABLE_ASSERTS
: some of them might even change the complexity of the algorithms performing the checks.
Bug fixes
- Fix [
ska_sorter
][ska-sorter] for signed 128-bit integers when both positive and negative values are present in the collection to sort. - The random-access version of [
quick_merge_sorter
][quick-merge-sorter] was O(n²) because it relied on libc++'s implementation of [std::nth_element
][std-nth-element] which is itself O(n²). It was replaced with [miniselect][miniselect]'s implementation of Andrei Alexandrescu's [QuickselectAdaptive][quickselect-adaptive] algorithm, ensuring thatquick_merge_sort
is O(n log n) as documented (issue #179).
- Fix a potential move-after-free bug in [
pdq_sorter
][pdq-sorter], affecting all components that rely on it.
Improvements
- The bidirectional overload of [
verge_sorter
][verge-sorter] was significantly reworked in order to make the optimized path faster, while keeping its previous speed for the path where the vergesort layer doesn't find big enough runs. The improvements are especially noticeable for the Ascending sawtooth and Descending sawtooth in the patterns benchmark. Here is a brief summary of the main improvements:- It now uses the same k-way merge algorithm as the random-access overload. Among other things this means that the bidirectional overload should now have the complexity described in the documentation. I am still unsure whether it was the case before or not.
- It is now smarter about which element should belong to which run, and as a result generates fewer 1-element runs, which leads to fewer merges overall.
- It now spends less time computing
std::distance
prior to merges.
- [
stable_adapter
][stable-adapter] now has dedicated specializations for [verge_sorter
][verge-sorter] and [verge_adapter
][verge-adapter] instead of relying onmake_stable
. The stable algorithm is a bit different from the unstable one: it detects strictly descending runs in the collection to sort instead of non-ascending ones, and wraps the fallback sorter instable_t
. This addresses issue Morwenn/vergesort#11 in the standalone project, and gives a partial answer for issue Morwenn/vergesort#7.
The benchmarks above clearly show the difference for the fast vergesort path for random-access iterators. The significant decrease in speed in the bidirectional benchmarks is due to the fact thatstable_adapter<verge_sorter>
usedmake_stable
in 1.8.1, which actually creates a buffer of N elements and performs a random-access sort there. As a result the new version uses less memory but is slower. It is still possible to get the 1.8.1 behaviour usingmake_stable<verge_sorter>
. - Nested [
stable_adapter
][stable-adapter] now unwraps. It is a scenario that could happened from time to time, and should produce clearer error messages thanks to the reduced nesting. - [
utility::is_probably_branchless_comparisons
andutility::is_probably_branchless_projection
][branchless-traits] now have specializations for more comparisons and projections (#177), both for internal and standard library types. These changes mean that [pdq_sorter
][pdq-sorter] uses its branchless partitioning algorithm in more scenari (which tends to be faster on average, but slower for some patterns). Since many components rely on pdqsort, the changes should be noticeable throughout the library. The changes affect the following features:- The type returned by [
std::mem_fn
][std-mem-fn] in libc++ and libstdc++ is now considered likely to be branchless when it wraps a pointer to data member. [utility::as_function
][as-function] usesstd::mem_fn
to make pointer to members callable, so this change might have repercussions in most of the library. - The C++20 function object [
std::identity
][std-identity] is always considered branchless. - The C++20 function objects [
std::ranges::less
][std-ranges-less] and [std::ranges::greater
][std-ranges-greater] follow the same rules as [std::less<>
][std-less-void] and [std::greater<>
][std-greater-void] when determining whether they are considered branchless. - [
ska_sorter
][ska-sorter] and [schwartz_adapter
][schwartz-adapter] have been enhanced to more often pass comparison of projection functions considered likely branchless to their underlying algorithms. - The comparison adapter used by [
counting_adapter
][counting-adapter] is now considered likely branchless when the adapted comparison is likely branchless itself, and when the type used for counting is a built-in arithmetic type.
- The type returned by [
Tooling
Benchmarks:
- Fix a
MatplotlibDeprecationWarning
in the errorbar-plot benchmark.
Documentation:
- Change the documentation here and there to make it more forward-compatible with the changes coming in 2.0.0.
- Change HTTP links to HTTPS when possible.
- Fix some incorrect uses of [
cppsort::sort
][cppsort-sort] that still used the pre-1.0.0 parameters order. - More small fixes to improve the overall quality of the documentation.
Test suite:
- Some files testing [
cppsort::sort
][cppsort-sort] and [cppsort::stable_sort
][cppsort-stable-sort] were in the sources but never run as par...