Sorting algorithms & related tools for C++14
It's spooky month in Pokémon Go, and as a result I've found myself listening to several remixes of the Lavender Town theme - an all-time favourite of mine - while preparing this release. Consider it project culture now that bugfix releases are named after songs since I can't wait for something specific to happen to me to name those (which is something I tend to do with other releases).
The release itself is mostly a number of bug fixes, documentation fixes and tiny improvements. Most of those were the result on working on several smaller sorting-related projects that share some code with cpp-sort.
minRunLength()
function in the tim_sorter
implementation so that it matches the one in CPython (issue #172, thanks @weeyizhi).iterator_category
of quick_merge_sorter
.quick_sorter
and quick_merge_sorter
for forward iterators in the documentation.quick_sorter
and quick_merge_sorter
. A bug in the elements being swapped meant that a value further away from the median was picked sometimes. It is unknown whether this was sufficient to change the complexity of the algorithm, but no significant difference in speed was noticed after the change.verge_sorter
now returns early if the collection is already sorted.poplar_sorter
was tweaked to ensure that it only ever performs a single memory allocation to track the poplars.master
tag was use so far for the download, and it was recently removed from the repository.conanfile.py
now raises a ConanInvalidConfiguration
error when the target compiler does not support C++14.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.
I have started cooking a bit more during the confinement, and I've recently made a bunch of mochis, which were some of the delicacies I missed the most from the trip in Japan. I've also cooked some Japanese curry and increasingly improved instant noodles, but mochis were more of a symbol. My taste buds are satisfied, it's time for a new cpp-sort release.
This release brings no new feature, but improves the existing ones a lot, and deprecates a few. Special care was given to the algorithms that support forward and bidirectional iterators, many of whom were a bit neglected or suffered from excessive pessimization. The other big things in this release are the improvements in tooling. You can read more about it below, but here is the gist of it:
The following features are now deprecated and will fire deprecation warnings if used. They will be removed in cpp-sort 2.0.0 (see the linked issues for the rationale for deprecation & removal):
cppsort::default_sorter
(#168): replace with pdq_sort
or a carefully chosen sorter.cppsort::sort
(#167): replace with pdq_sort
or a carefully chosen sorter.cppsort::stable_sort
(#167): replace with merge_sort
, or wrap a sorter in stable_adapter
.cppsort::make_integer_range
: this utility hasn't been used since 2015 and does not help with any of the library's components.Deprecation warnings can be disabled by defining the preprocessor macro CPPSORT_DISABLE_DEPRECATION_WARNINGS
.
out_of_place_adapter
that sometimes triggered compile time errors.iterator_category
of out_of_place_adapter
is now always std::forward_iterator_tag
, in line with what the documentation claimed.sorter_facade
was used to add projections support to an algorithm that only handles comparisons. This might fix issues with std_sorter
.probe::exc
, probe::ham
and probe::max
.stable_adapter
<
std_sorter
>
from an instance of std_sorter
. It mainly makes it more usable with C++17 implicit deduction guides.indirect_adapter
now also works with forward and bidirectional iterators (#166). The algorithm underlying these new capabilities is Matthew Bentley's indiesort. The resulting sorter can sort any iterator category regardless of the iterator category of the adapted sorter.merge_sort
is now globally faster than it used to (see the story here if you want fun trivia):
probe::dis
is now O(n²) instead of accidentally being O(n³), leading to ridiculously huge improvements:
The algorithm was further improved with a heuristic allowing it to short-circuit non-negligible parts of the computation when it doesn't hit one of the worst cases:
In the graph above probe::dis-dev
corresponds to probe::dis
in the previous graph - the color was kept for consistency. It is also worth nothing that the collection used is 10 times the size of the one used for the previous graph.cppsort::sort
led to the change of the few parts of the library that relied on it. These lead to simpler error messages in those places.verge_adapter
had static assertions to ensure that the algorithm only handled forward iterators instead of bidirectional ones. This wasn't buggy per se but led to useless static assertions, and less clear error messages.Benchmarks:
patterns
and small-array
benchmarks now ensure that every sorter will be given the same input for random distributions, making the generated graphs more relevant.patterns
now takes the root of the results directory as a command-line parameter instead of forcing it to profiles
.patterns
and errorbar-plot
have an --alternative-palette
option to switch to an infinite colour palette instead of the new default colourblind-friendly palette.small-array
was enhanced with the experience gathered from the other benchmarks.size_t
into any type in a custom way.Documentation:
Test suite:
Miscellaneous:
rename-library.py
which renames all references to cpp-sort in the library, mainly used to test different versions of the library's algorithms side-by-side in benchmarks.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.
I spent a great deal of time during the recent confinement identifying flowers and other plants in my garden, and I also learnt to cook some of them. I was left with a a few hundred plant pictures on my phone and decided to start a tiny glitch art side project with some of the flower photos. With all those flowery endeavours behind me, it was time to come back with a fresh cpp-sort release.
Chainable projections through operator|
have been implemented (issue #82), allowing to apply several transformations in a row when projecting a collection's element:
struct wrapper { int value; };
std::vector<wrapper> vec = { /* ... */ };
auto&& negate = cppsort::utility::as_projection(std::negate<>{});
// Applies &wrapper::value to the elements of vec, then negate
cppsort::split_sort(vec, &wrapper::value | negate);
The new operator|
only considers classes inheriting from cppsort::utility::projection_base
during overload resolutions. In order to make your own projections work with you can either make them inherit from projection_base
, or adapt them with cppsort::utility::as_projection
.
merge_insertion_sort
has been improved (it remains an extremely slow algorithm):
The old implementation used std::list
internally, with either std::allocator
or __gnu_cxx::bitmap_allocator
when available to improve the allocation speed. The new implementation uses a custom list data structure which performs a single allocation of all the nodes required by the algorithm.const
reference, it is the responsibility of the caller to make sure that such predicates don't modify their parameters in a way that would affect the consistency of the sort (issue #136). Following the resolution of standard issue LWG3031 it is also the responsibility of the caller to ensure that, should the predicate accept both const
and non-const
parameters, the results are consistent between overloads.as_comparison
and as_projection
can now adapt any Callable, and not just objects callable with the normal function call syntax.pdq_sort
(merged a fix from upstream).ska_sort
a bit.find_package
first, and only downloaded if no suitable version was found on the system. This notably allows to build the test suite while offline.bars.py
in the benchmarking tools.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.
I didn't have the opportunity to brunch properly since my trip to Scotland back in August where I could enjoy tasty local breakfasts at unreasonable hours - with today's excellent vegetarian brunch that cycle is complete and I can publish a new cpp-sort release.
A new spin_sorter
has been added to the library, based on the algorithm from Boost.Sort. Spinsort is a stable mergesort derivative which is often faster than the other available stable sorting algorithms. It is a stable comparison sorting algorithm that runs in O(n log n) and requires O(n) additional memory; unlike other algorithms in the library it doesn't have a fallback when there isn't enough extra memory available to merge runs.
As can be seen in the benchmark result above (sorting a std::vector<long double>
with 10^7 elements) it tends to be the fastest of the stable sorts for random data, and is otherwise adaptive when some presortedness exists in the data to sort.
tim_sorter
, which sometimes triggered Valgrind diagnostics when trying to sort an std::deque
(issue #89).hybrid_adapter
that triggered a compile-time issue with Clang 9 (issue #158).poplar_sorter
that triggered a diagnostic with the undefined behaviour sanitizer.static_assert
that wasn't strict enough in verge_adapter
.assert
anymore: you now need to define the preprocessor flag CPPSORT_ENABLE_ASSERTIONS
explicitly in order to enable assertions. This flag still honours the NDEBUG
macro.verge_sorter
is used to sort bidirectional iterators, it now falls back to quick_merge_sorter
instead of quick_sorter
to sort sections of the data to sort where runs aren't big enough. This lowers the complexity from O(n²) to O(n log n log log n) with a worst case of O(log n log n) space - the complexity's worst case shifts from the fallback to the vergesort layer itself. The vergesort layer still uses O(n) memory when it finds patterns to optimize.counting_sorter
is now able to sort collections of [un]signed __int128
, even when the standard library is not properly instrumented to support them.uninitialized_move
may be faster when sorting trivial types. Affected sorters: block_sorter
, merge_insertion_sorter
, merge_sorter
, spin_sorter
, tim_sorter
and verge_sorter
.There has been some overarching CMake and Conan cleanups for this release: cpp-sort is notably available on Conan Center now, and the built-in Conan support has been reduced and should only be used by people willing to package their own version of the library.
add_subdirectory
without triggering errors.BUILD_EXAMPLES
(OFF
by default).Debug
builds.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.
Tiny Little Pieces: it's both what was broken in the 1.5.0 release and the name of an excellent track by Hypnagog that I often listen to while programming.
hybrid_adapter
, which failed for a variety of use cases, and notably when using CTAD in C++17. It now works as expected.hybrid_adapter
taking sorters is now constexpr
.adapter_storage::get()
are now constexpr
.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.
I spent the last two weeks enjoying a roadtrip through Scotland, watching the beautiful landscape while two good friends enjoyed driving the van on single-track roads. This feels pretty consistent with the previous Tartan release, and once again it gave me a boost of motivation to publish a cpp-sort release, so here we are.
The highlight of this release is the ability for sorter adapters to accept stateful sorters: this is the first step required for supporting mutable sorters in the library (issue #104). This is useful to provide first-class support for sorters that are parametrized at construction time: for example imagine a counting_sorter
taking min and max parameters at construction time to avoid having to look them up, it would still be possible to adapt such a sorter as follows:
auto sort1 = counting_sorter(0, 100); // NOT the cpp-sort sorter
auto sort2 = cppsort::out_of_place_adapter(sort1);
sort2(collection);
Several part of the library have been modified in order to support this feature. Here is an incomplete list of things that changed as a result:
small_array_adapter
for which I was unable to come up with a satisfying design.get()
member function to retrieve a copy of the original sorter, except hybrid_adapter
for which a single get()
function wouldn't make sense since it adapts several sorters.sorter_facade
was updated to handle stateful sorters: it can now be constructed with parameters which are forwarded to the sorter implementation, and it now only provides operators to convert the sorter to different of function pointers when said sorter is empty and default-constructible.In order to work properly with sorter adapters, sorters are expected to be copy-constructible: adapters make a copy of the sorters they adapt. Additionally a sorter is expected to be empty and default-constructible for conversions to function pointers to work.
Under the hood, pretty much every single-sorter adapter inherits from the newly introduced utility::adapter_storage<Sorter>
to store and retrieve the sorter they adapt. This class template implements three operations:
const
and reference qualifications depend on that of the adapter_storage
instance.adapter_storage::operator()
forwards its parameters to the corresponding operator in the wrapped sorter (or to a default-constructed sorter) and returns the result of that operation.If you need to write a sorter adapter that properly handles stateful sorters, then inheriting from adapter_storage
is probably the simplest solution to correctly provide the full gamut of semantics described above.
grail_sorter
and tim_sorter
now support comparison and projection function objects that aren't default-constructible.quick_merge_sorter
(issue #151).Function objects from the comparators module have been improved in the following ways (issue #150):
is_transparent
member type which allows them to be used in the standard library's ordered associative containers to compare heterogeneous types.total_less_t
, total_greater_t
, natural_less_t
, etc. to make them more usable where type names are needed.natural_less
is now able to compare heterogeneous types as long as they provide begin
and end
functions returning iterators that share a common value_type
.Other library improvements:
block_sorter
, grail_sorter
, merge_sorter
, split_sorter
, verge_sorter
and verge_adapter
.move[_backward]
algorithms have been rewritten to fallback to their std::
counterparts in more situations, which might make a good number of the library's algorithms faster when the std::
algorithms are optimized for specific iterators: this should notably be the case for libc++ std::deque
iterators.grail_sorter
and tim_sorter
.operator delete
supports sized deallocation, then several allocating algorithms will take advantage of it.conanfile.py
recipe is better integrated with CMake, and notably uses the project's CMakeLists.txt
install rules to package the library.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.
It was Tartan Day a few days ago, the perfect occasion to wear your kilt or anything tartan. Combined with a surprise carbonade flamande with a friend over the weekend, I had all the energy required to finally fix a remaining bug and push a new cpp-sort release.
This release brings a single new feature, split_sorter
that we will describe later, and a bunch of bug fixes, tiny library improvements, and tooling improvements. The development was somewhat painful because benchmarking split_sort
lead me to an existing bug in drop_merge_sort
, so I analyzed it, fixed it, wrote a more general test and found bugs in other sorting algorithms, then in measures of presortedness, and even in tooling while I was doing further testing... The rabbit hole went ever deeper, but it eventually came to an end and I could finally produce that single-feature release.
A split_sorter
has been added to the library, implementing the "in-place" variant of the SplitSort algorithm described in Splitsort—an adaptive sorting algorithm by Levcopoulos and Petersson. split_sort
is a comparison-based unstable sorting algorithm that might require O(n) extra memory to speed up an internal merge step, but works fine with O(1) extra memory nonetheless.
The algorithm is close from drop-merge sort: it computes an approximation of a longest non-decreasing subsequence, excludes the elements that are not part of it, sorts them (currently with pdqsort), and merges the two sequences. The graph below shows how it performs compared to drop-merge sort when sorting a collection with an increasing number of elements not in their place:
While it shares many similarities with drop-merge sort, they still have a few differences:
split_sort
offers a tool similar to drop_merge_sort
, but with different tradeoffs.
exc
, ham
and max
now correctly handle duplicate values (#143).block_sort
and drop_merge_sort
.std::string
with the following algorithms (#142): block_sort
, drop_merge_sort
and grail_sort
.Nested hybrid_adapter
now automatically unwraps (thanks to @notfoundry for this!). To understand why this feature is interesting, consider the following sorter:
using sorter = cppsort::hybrid_adapter<
cppsort::hybrid_adapter<
forward_sorter,
random_access_sorter
>,
bidirectional_sorter
>;
When called on forward or bidirectional iterators, sorter
will use the appropriate sorter. However, without the unwrapping, sorter
can never call random_access_sorter
because the outer sorter considers the iterator category of the inner sorter, which in this case is std::forward_iterator_tag
. With the new unwrapping ability, the sorter
above should be equivalent to the following one:
using sorter = cppsort::hybrid_adapter<
forward_sorter,
random_access_sorter
bidirectional_sorter
>;
Therefore it will call random_access_sorter
as expected when passed random-access iterators.
Avoid Clang -Wc++1z-extensions
warnings when using [[fallthrough]]
while not in C++17.
Small optimizations in block_sort
, drop_merge_sort
, grail_sort
, schwartz_adapter
and tim_sort
.
schwartz_adapter
now simply calls the adapted sorter when passed identity
as a projection.
Some efforts were made to improve the build times, notably because of the increasingly high build times of the continuous integration:
mtime_cache
on the CI server to finally have proper incremental builds.Other tooling changes:
test_failing_sorter.cpp
- which I often use and tweak to investigate failing sorters.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. I still don't have a great version hygiene for those, but I promise that it will improve with the time.
I legit had the best cuddles in my life over the weekend (it's never too late to learn new things apparently), so I am now in a good mood to finish a cpp-sort release ^^ This new release doesn't offer new features on the library side, but the CMake scripts have been totally overhauled to take advantage of modern CMake features and provide a cleaner interface.
Overhaul of the CMake scripts:
Catch2::Catch2
CMake target. This uses the CMake script Crascit/DownloadProject.catch_discover_test
to have one CTest test per Catch2 test instead of one CTest test for the whole testsuite.fixed_buffer<0>
which miscompiled with Clang 6.probe::mono
didn't work when the comparison function was a special kind of callable (e.g. a pointer to member).out_of_place_adapter
sometimes didn't work because we accidentally let ADL find a function in an inner namespace instead of fully qualifying it (which was enough for the testsuite).schwartz_adapter
now returns the result of the adapted sorter if any when called (#134).indirect_adapter
and out_of_place_adapter
now return the result of their adapted sorter if any when called (C++17 only, depends on the feature test macro __cpp_lib_uncaught_exceptions
) (#134).indirect_adapter
now works with projection-only sorters too (e.g. ska_sorter
, spread_sorter
) (#138).lower_bound
and upper_bound
somewhat faster, helping to make many algorithms using them slightly faster.The tool to validate sorting networks has been parallelized and now runs a few times faster.
Use the CMake script cotire to hopefully improve the build times.
Use Catch2's new TEMPLATE_TEST_CASE
to significantly reduce the size of the code of the testsuite.
I've recently got my freckles-ridden skin checked for melanomas and I apparently don't have any, which is an excellent occasion to celebrate with a new cpp-sort release. This release brings new tools and several performance improvements to the library.
quick_merge_sort
. It is a specific flavour of the QuickMergeSort algorithm proposed by Stefan Edelkamp and Armin Weiß with a specific quirk: it starts by partitioning the collection with an equivalent of std::nth_element
at its two thirds, then uses an internal mergesort to sort the first two thirds, using the last part of the collection as a swap buffer, then proceeds to sort the last third with the same technique. This sorter runs in O(n log n) even with forward iterators, using at most O(log²n) stack memory due to recursion.out_of_place_adapter
. This adapter simply moves the elements of the collection to sort to a temporary buffer, sorts the buffer with the adapted sorter, then moves the sorted result back to the original collection. As long as enough memory is available, it is the easiest way to sort a collection providing forward or directional iterators fast enough, allowing to use random-access sorters to sort them in the temporary buffer.quick_sorter
is now guaranteed to run in O(n log n) instead of O(n²). In order to achieve this it uses the median-of-medians algorithm to select its pivot when the recursion exceeds 2log n. This brings the space complexity up to O(log²n) due to the stack space used by the mutual recursion of the median-of-medians algorithm.sorting_network_sorter
now needs 100 comparisons instead of 101 to sort 21 inputs thanks to the latest results of SorterHunter.inplace_merge
function used by several sorters now uses the Symmerge algorithm described by Pok-Son Kim and Arne Kutzner in Stable Minimum Storage Merging by Symmetric Comparisons instead of the old Dudziński and Dydek algorithm.tim_sorter
now reuses a same merge buffer — making it grow as needed — instead of reallocating and deallocating a new buffer whenever it needs to merge runs.ska_sorter
is now able to sort collections of [un]signed __int128
, even when the standard library is not properly instrumented to support them.stable_adapter<hybrid_adapter<Sorters...>>
is now equivalent to hybrid_adapter<stable_adapter<Sorters>...>
in order to better take advantage of sorters and adapters specialized for stable_adapter
.Make it easier to change the type of elements to sort in bench.cpp
.
The tool to validate sorting networks is a bit faster thanks to a new permutation algorithm based on Gray codes.
I will be away in Japan for a few weeks, which means that it is probably a good time for a bugfix release. No new exciting feature in this release, but several small improvements here and there.
counting_adapter
in C++17stable_adapter<self_sort_adapter>
to make implicit deduction guides work in C++17class
/struct
difference between declaration and definition of hybrid_adapter
Make the constructors of sorter adapters taking one or more sorters explicit
probe::rem
now performs a single pass over the sequence even when passed non-random-access iterators, which might make it slightly more performant in this case
Code using std::result_of
now uses std::invoke_result
when available, making it more robust against type system subtleties
More noexcept
here and there
Tiny attempts to improve the build times and produced binary size here and there, but it unfortunately shouldn't make any noticeable difference