4 ms·

I'd like to emphasize that ipnsort is primarily designed as the new Rust std library unstable sort, which means it optimizes for all these factors simultaneousl

I'd like to emphasize that ipnsort is primarily designed as the new Rust std library unstable sort, which means it optimizes for all these factors simultaneously: - input type (including stuff that is not an integer or float) - input size - input pattern - prediction state - binary size - compile times - varying ISAs and Hardware Especially binary size and compile times mean I'm not chasing the performance crown for integers in some HPC setting. I can trivially pull out another 7% perf by ignoring binary size, compile times and effects on types that are not integers https://github.com/Voultapher/sort-research-rs/commit/d908feb0070717510ddc20b632c1568ce6949b0a https://github.com/Voultapher/sort-research-rs/commit/d908fe....

mlochbaum 3y ago
This is a point that I'm kind of fuzzy on: is there a specific requirement to not change the algorithm too much based on type/comparison? Like if the user calls it on a 1-byte type with default comparison, the best way to do this in a vacuum is a counting sort. Smaller generated code and everything. Both C/C++ and Rust developers seem unwilling to do this, but not having asked I don't know why exactly. On the other hand Julia just switched to radix sort much of the time in their latest version, so other languages can have different approaches.
- xoranth 3y ago
  As a datapoint, numpy also chooses between radix and timsort based on data type. From the docs [^0]: > ‘stable’ automatically chooses the best stable sorting algorithm for the data type being sorted. It, along with ‘mergesort’ is currently mapped to timsort or radix sort depending on the data type. API forward compatibility currently limits the ability to select the implementation and it is hardwired for the different data types. [^0]: https://numpy.org/doc/stable/reference/generated/numpy.sort.html https://numpy.org/doc/stable/reference/generated/numpy.sort....

mlochbaum 3y ago

This is a point that I'm kind of fuzzy on: is there a specific requirement to not change the algorithm too much based on type/comparison? Like if the user calls it on a 1-byte type with default comparison, the best way to do this in a vacuum is a counting sort. Smaller generated code and everything. Both C/C++ and Rust developers seem unwilling to do this, but not having asked I don't know why exactly. On the other hand Julia just switched to radix sort much of the time in their latest version, so other languages can have different approaches.

xoranth 3y ago
As a datapoint, numpy also chooses between radix and timsort based on data type. From the docs [^0]: > ‘stable’ automatically chooses the best stable sorting algorithm for the data type being sorted. It, along with ‘mergesort’ is currently mapped to timsort or radix sort depending on the data type. API forward compatibility currently limits the ability to select the implementation and it is hardwired for the different data types. [^0]: https://numpy.org/doc/stable/reference/generated/numpy.sort.html https://numpy.org/doc/stable/reference/generated/numpy.sort....