1.8.0 — Mochis

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 wiki pages are now in the main source repository, and a GitHub Action automatically updates the wiki when a new release is created.
• New benchmarks were added to display interesting properties of some algorithms.
• The Benchmarks page of the documentation was totally rewritten, and all benchmarks were regenerated to be up-to-date with the library.

Deprecations

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.

Bug fixes

• Add missing includes to out_of_place_adapter that sometimes triggered compile time errors.
• The declared iterator_category of out_of_place_adapter is now always std::forward_iterator_tag, in line with what the documentation claimed.
• Fix bug that sometimes occurred when sorter_facade was used to add projections support to an algorithm that only handles comparisons. This might fix issues with std_sorter.
• Fix bugs due to use of moved-from comparison and projection functions in probe::exc, probe::ham and probe::max.
• Fix construction of stable_adapter<std_sorter> from an instance of std_sorter. It mainly makes it more usable with C++17 implicit deduction guides.

Improvements

• 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.
• When given forward iterators and when no extra heap memory is available, merge_sort is now globally faster than it used to (see the story here if you want fun trivia):
  
• When given forward iterators or bidirectional iterators, 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.
• Other sorters, adapters, measures of presortedness and internal algorithms that handle forward and/or bidirectional iterators used to start by computing the size of the passed collection, which was often rather sub-optimal (#169). Those components were reviewed prior to this release, and changed as needed. They now perform O(n) fewer operations when passed a collection which provides its size in O(1), leading to speed improvements in the following user-facing function objects:
  • probe::dis
  • probe::exc
  • probe::ham
  • probe::inv
  • probe::max
  • probe::rem
  • schwartz_adapter
  • stable_adapter
  • verge_sorter
• The sorting network for 18 inputs uses fewer compare-exchange units than it used to thanks to the latest results of SorterHunter.
• The sorting networks for 21 and 22 inputs also use newer results from SorterHunter. These networks don't have a smaller size than before, but have a smaller depth.
• The removal of 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.

Tooling

Benchmarks:

• New benchmark to compare the evolution of the running times of different sorting algorithms when the size of the collection grows.
  
• New benchmark to visualize how the speed of some algorithms evolve with the number of inversions in the collection to sort.
  
• Some of the benchmarks now use a colorblind-friendly palette created by Thøger Rivera-Thorsen (unfortunately not the one above since it uses more colors than the new palette).
• The benchmarks directory was reorganized and now has one subdirectory per benchmark.
• 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.
• Benchmarks now log the seed they were initialized with for better reproducibility.
• The benchmark distributions can now be passed a projection function to transform the generated size_t into any type in a custom way.

Documentation:

• The documentation sources are now in the main GitHub repository (#157), and a GitHub Action updates the wiki whenever something is pushed to master. This change makes things better in several ways:
  • Code, tests and documentation can be committed at the same time, increasing the coupling and making it easier to track or revert related changes.
  • It makes it easier for non-maintainers to contribute to the documentation.
  • It is now possible to have a specific version of the library with a matching documentation.
  • The day we switch to version 2.0.0, it will be possible to cleanup the documentation and having the doc for version 1.x and 2.x live side by side in different branches.
  • The documentation is now easily browsable for a given release or branch.
• The Benchmarks page was completely regenerated, updated with new benchmarks and reorganized. I hope that I will be able to keep it updated in the future.

Test suite:

• Additional tests for adapters that can handle forward iterators and/or bidirectional iterators.
• Test some measures of presortedness when no heap memory is available.
• Additional tests to ensure that sorters and measures of presortedness don't use a moved-from comparison or projection.

Miscellaneous:

• New tool 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.
• All source files now use an UTF-8 encoding.
• The handling of licenses changed a bit: the way all the files are licensed now appears in a clearer way, there is NOTICE.txt file describing all the extra licenses, most files without an explicit license were changed to display one. Also source files now use a short form of the copyright notice in order to reduce the redundant per-file information.

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.