Skip to content

1.13.1 — Find Her
Compare
Choose a tag to compare
@Morwenn Morwenn released this 02 Oct 18:10
1.13.1
aeb535f
This commit was created on GitHub.com and signed with GitHub’s verified signature. The key has expired.
GPG key ID: 4AEE18F83AFDEB23
Expired
Learn about vigilant mode.

DOI

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 and iter_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 the cppsort::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 of std::identity in C++20 mode. Introduced in version 1.13.0, this bug could cause issues when passing std::identity to sorters relying on sorter_facade to provide projection support, such as std_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.
    Graph showing the difference of comparisons performed between the old an new versions of heap_sort
  • 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 that quick_merge_sort was not a stable sort anyway and could therefore switch to a better unstable fallback algorithm for very small collections.
    Benchmark the new quick_merge_sort over std::forward_list<double> against the old version
  • string_spread_sort was changed to perform fewer projections, sometimes halving the total number of performed projections.
    Graph showing the difference of projections performed between the old an new versions of string_spread_sort
  • 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 their index_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 fully constexpr when the sorters it wraps are themselves constexpr (#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 the tools directory was changed by a more complete generate_sorting_network.py tool which formally verifies that a given sorting network works, then generates the corresponding sorting_network_sorter.
  • dist::as_long_string in the benchmarking tools now inherits from utility::projection_base and its operator() is const.
  • 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.

Assets 2