3 ms·

Ok so both the things you linked are not my ideas. The first one is AFAIK originally from the BlockQuicksort paper https://arxiv.org/pdf/1604.06697.pdf https://

Ok so both the things you linked are not my ideas. The first one is AFAIK originally from the BlockQuicksort paper https://arxiv.org/pdf/1604.06697.pdf https://arxiv.org/pdf/1604.06697.pdf section 3.2. Which Orson Peters used in his pdqsort, which I know base ipnsort on. The second one is from Igor van den Hoven in his work on quadsort as I mention in the function description. Really a lot of this stuff is building on top of other peoples work and refining it. Seemingly I'm the first to write neat little ASCII graphics for them in the code making them easier to approach. There are some novel ideas by me in there too though, for example https://github.com/Voultapher/sort-research-rs/blob/42bf339d0d31de61c0490dceffdfd7f55324cbc8/src/unstable/rust_ipnsort.rs#L1501 https://github.com/Voultapher/sort-research-rs/blob/42bf339d... the way I marry a limited number of sorting-networks, insertion sort and the bi-directional merge into one, very fast but binary size and compile time efficient package is novel. Or that with LLVM you can do 2 instead of 4 writes per loop iteration in the bi-directional merge, which Igor has now ported back to his stuff as well. Generally I'd say my work has been more about figuring out novel ways to combine existing ideas into one good cohesive package fit for a standard library sort implementation. As well as taking ideas that work in the C and C++ world and doing the legwork to adapt them for use in Rust, which requires a lot more considerations and a lot of code can't be ported straight up. I wrote a little more about that in another comment here.

gavinray 3y ago
Thanks for the reply! Do you feel like you have a sort of "intuition" for which things might work, and you experiment starting from that, or what is your general thought process like? Or maybe you start by drawing things out on paper? Really curious what the process of reasoning and thinking about something like this is.
- Voultapher 3y ago
  As with many things experience plays a large role. I've now spent more than a year a probably more than a thousand hours on and around the topic of sort implementations. The way I think about this now is very different to the start. I have a background of investigating and wanting to understand compilers and how they interact with modern hardware. My mental model of how hardware works is usually my start-off point to try out ideas. More often than not my ideas don't work out and my mental model is wrong. That's ok, modern hardware is a giant bunch of shared mutable state that interacts in really non-trivial ways. So I guess yes I've developed an intuition, but I always try to prove it wrong with experiments. Sometimes I sit down with pen and paper and scribble ideas down, sometimes I start coding an implementation directly, sometimes I start with an experiment setup, sometimes I search for what other people have done in that space, and I've even tried asking Chat-GPT about some stuff but that has been mostly useless. Specifically with high-performance sort implementations it helps to think of them as a bunch of components that each have their own role. Giving a simple example of a quicksort based implementation, you have partitioning, small-sort, fallback and some kind of pattern analysis. Each component exists to fulfill a certain role, partitioning is the algorithmic core and should perform well for sizes above your small-sort threshold up to really large sizes. The small-sort is maybe the most perf critical part, quicksort will spend most of the calls, not necessarily most of the time, in the small-sort, classically insertion sort e.g. https://user-images.githubusercontent.com/6864584/200373619-4fa69557-bab2-46e4-adb2-a0e3a8446f79.png https://user-images.githubusercontent.com/6864584/200373619-.... The fallback is there to make sure that you have a worst case Big O(N * log(N)). It should take over if a certain recursion limit is reached based on the input size, eg. `2 * (len | 1).ilog2()`. And the pattern analysis, for example a simple streak analysis usually sits at the start and makes sure that fully ascending and descending inputs can be sorted in O(N - 1). Hope this answers your question, and thanks for asking :)
scandum 3y ago
https://github.com/scandum/quadsort/blob/f171a0b26cf6bd6f6dc220ef49b0ea43fc85a578/src/quadsort.c https://github.com/scandum/quadsort/blob/f171a0b26cf6bd6f6dc... As you can see, quadsort 1.1.4.1 used 2 instead of 4 writes in the bi-directional parity merges. This was in June 2021, and would have compiled as branchless with clang, but as branched with gcc. When I added a compile time check to use ternary operations for clang I was not adapting your work. I was well aware that clang compiled ternary operations as branchless, but I wasn't aware that rust did as well. I added the compile time check to use ternary operations for a fair performance comparison against glidesort. https://raw.githubusercontent.com/scandum/fluxsort/main/images/fluxsort_vs_glidesort.png https://raw.githubusercontent.com/scandum/fluxsort/main/imag... As for ipnsort's small sort, it is very similar to quadsort's small sort, which uses stable sorting networks, instead of unstable sorting networks. From my perspective it's not exactly novel. I didn't go for unstable sorting networks in crumsort to increase code reuse, and to not reduce adaptivity.

gavinray 3y ago

Thanks for the reply! Do you feel like you have a sort of "intuition" for which things might work, and you experiment starting from that, or what is your general thought process like? Or maybe you start by drawing things out on paper? Really curious what the process of reasoning and thinking about something like this is.

Voultapher 3y ago
As with many things experience plays a large role. I've now spent more than a year a probably more than a thousand hours on and around the topic of sort implementations. The way I think about this now is very different to the start. I have a background of investigating and wanting to understand compilers and how they interact with modern hardware. My mental model of how hardware works is usually my start-off point to try out ideas. More often than not my ideas don't work out and my mental model is wrong. That's ok, modern hardware is a giant bunch of shared mutable state that interacts in really non-trivial ways. So I guess yes I've developed an intuition, but I always try to prove it wrong with experiments. Sometimes I sit down with pen and paper and scribble ideas down, sometimes I start coding an implementation directly, sometimes I start with an experiment setup, sometimes I search for what other people have done in that space, and I've even tried asking Chat-GPT about some stuff but that has been mostly useless. Specifically with high-performance sort implementations it helps to think of them as a bunch of components that each have their own role. Giving a simple example of a quicksort based implementation, you have partitioning, small-sort, fallback and some kind of pattern analysis. Each component exists to fulfill a certain role, partitioning is the algorithmic core and should perform well for sizes above your small-sort threshold up to really large sizes. The small-sort is maybe the most perf critical part, quicksort will spend most of the calls, not necessarily most of the time, in the small-sort, classically insertion sort e.g. https://user-images.githubusercontent.com/6864584/200373619-4fa69557-bab2-46e4-adb2-a0e3a8446f79.png https://user-images.githubusercontent.com/6864584/200373619-.... The fallback is there to make sure that you have a worst case Big O(N * log(N)). It should take over if a certain recursion limit is reached based on the input size, eg. `2 * (len | 1).ilog2()`. And the pattern analysis, for example a simple streak analysis usually sits at the start and makes sure that fully ascending and descending inputs can be sorted in O(N - 1). Hope this answers your question, and thanks for asking :)

scandum 3y ago

https://github.com/scandum/quadsort/blob/f171a0b26cf6bd6f6dc220ef49b0ea43fc85a578/src/quadsort.c https://github.com/scandum/quadsort/blob/f171a0b26cf6bd6f6dc... As you can see, quadsort 1.1.4.1 used 2 instead of 4 writes in the bi-directional parity merges. This was in June 2021, and would have compiled as branchless with clang, but as branched with gcc. When I added a compile time check to use ternary operations for clang I was not adapting your work. I was well aware that clang compiled ternary operations as branchless, but I wasn't aware that rust did as well. I added the compile time check to use ternary operations for a fair performance comparison against glidesort. https://raw.githubusercontent.com/scandum/fluxsort/main/images/fluxsort_vs_glidesort.png https://raw.githubusercontent.com/scandum/fluxsort/main/imag... As for ipnsort's small sort, it is very similar to quadsort's small sort, which uses stable sorting networks, instead of unstable sorting networks. From my perspective it's not exactly novel. I didn't go for unstable sorting networks in crumsort to increase code reuse, and to not reduce adaptivity.