Hacker News Reader

Comment by gavinray | Hacker News Reader

If you look at the history of the author's own sorting implementation (ipnsort), it started as an attempt to port fluxsort to Rust:

https://github.com/Voultapher/Presentations/blob/master/rust...

https://www.youtube.com/watch?v=3JZAQ4Gsl-g

It starts there, eventually the author abandons the linked PR because of a better approach found with ipnsort:

https://github.com/rust-lang/rust/pull/100856#issuecomment-1...

View on HN

You are right the initial kick-off point was an attempt to port fluxsort for a stable sort in Rust, but that quickly turned out to be unfeasible because Rust implementations have way higher requirements in terms of safety. The user can modify values during a comparison operation, leave the logic at any comparison point via an panic (exception) and the comparison function may not be a total order. Together these effects make most of the code in fluxsort useless for Rust. I had been working on ipn_stable and ipn_unstable to completely different implementations. ipnsort, previously ipn_unstable started off with the pdqsort port that is the current Rust `slice::sort_unstable` and from there on I iterated and tried out different ideas.

Well, I know what you mean but "completely different" is potentially misleading here. The current ipnsort is using bidirectional merges developed for quadsort (the merging part of fluxsort) and the fulcrum partition from crumsort, also by Scandum (all credited in comments; check the source if you want to see more influences!). To balance things out, the strategy for using the namesake sorting networks is new to me: pick a few fixed sizes and handle the rest by rounding down then a few steps of insertion sorting.

I should clarify, I meant that ipn_stable and ipn_unstable were separate projects, albeit with some cross-over ideas.

I can't rule out that someone else had that idea for limiting the use of sorting-networks, all I can say is that I came up with that myself. At the same time a lot of the good ideas in ipnsort are ideas from other people, and I try my best to accredit them. As I commented before, my goal is not peak perf for integers at any cost. Here is a commit https://github.com/Voultapher/sort-research-rs/commit/d908fe... that improves perf by 7% across sizes for the random pattern. But that comes with a non negligible binary size and compile time impact even for integers. And while I use heuristics to only use sorting-networks where sensible, they can guess wrong. This is a generic sort implementation with the goal of being a good all-round implementation fit for a standard library and those various uses.

"pick a few fixed sizes and handle the rest by rounding down then a few steps of insertion sorting."

I'm late to the party, but this sounds a lot like quadsort's small array handling:

Sort 4, 8, or 16 elements using unrolled parity merges, and handle the rest with insertion sorting.

An unrolled parity merge can be viewed as a stable sorting network. I never added unstable sorting networks to crumsort due to wanting to keep the code size low, and perhaps the mistaken idea that it would reduce adaptivity, as crumsort is likely to scramble partially sorted input.

I'm not talking about ipnsort, which I think is great. It makes good use of existing work and doesn't use AVX at all. So extending it with AVX-512 partition code would also be a good project!

Reply on news.ycombinator.com