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: use drop_merge_adapter<pdq_sorter> instead.
• split_sorter: use split_adapter<pdq_sorter> instead.
• verge_sorter: use verge_adapter<pdq_sorter> instead for random-access iterators, or verge_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, 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 of hybrid_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 now works on bidirectional iterators. Prior to this release it only accepted random-access iterators.
• Defining CPPSORT_ENABLE_AUDITS now also automatically defines CPPSORT_ENABLE_ASSERTIONS.
• Fixed a warning that occurred when CPPSORT_ENABLE_AUDITS was defined but CPPSORT_ENABLE_ASSERTIONS wasn't.
• Fixed -Wpessimizing-move warnings in flip and not_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) and split_adapter(heap_sort), which are more interesting defaults for that benchmark than the previous ones.
• Replaced now deprecated verge_sort with spin_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 and CPPSORT_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's assert.
• 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.