4 ms·

Hello, author of glidesort (and for context, pdqsort) here. No it's not released yet but it's getting real close. The code is virtually done, with some minor c

by orlp 4y ago

Hello, author of glidesort (and for context, pdqsort) here. No it's not released yet but it's getting real close. The code is virtually done, with some minor cleanup required. Besides some personal stuff, a large source of my delay has been the headache that is panic safety in Rust. Non-trivial sorting code becomes extra difficult if a forced stack unwinding can occur every time you compare two elements, where you are then required to fully restore the input array to a valid state. Doubly so if you can't even assume the comparison operator is valid and obeys the strict order semantics. I am currently in the process of writing a paper I want to publish along glidesort which is also mostly done. Since the linked talk I've also had some more performance wins making it ~4.5 times faster than std::stable_sort for uniform random integers and much more than that for low cardinality data and input patterns. Glidesort can use arbitrary amounts of auxiliary memory if necessary, but is fastest when given a fraction of the original input array worth of memory - I'm currently planning on releasing it with n / 8 as the default. I haven't looked at blitsort in detail but I am skeptical of the O(n log n) claim, I believe it is O(n (log n)^2) like glidesort is when given a constant amount of memory, as blitsort's partition and merge functions are recursive. Not that this really matters in practice - ultimately the real runtime is what matters. But I wouldn't be surprised to see blitsort slow down more relative to the competition for larger inputs.

scandum 4y ago
It should be O(n log n) comparisons and technically O(n (log n)^2) moves. The moves are reduced by a relatively large constant however, and blitsort might qualify as O(n log n) moves when given sqrt(n) aux. In your Youtube presentation you do seem to skip mentioning that many of the performance innovations in glidesort were derived from quadsort and fluxsort. Some credit in your upcoming paper would be much appreciated. Feel free to email me if you have any questions, some things like my first publication of a "branchless" binary search in Aug 2014 may be hard to find, though there might be prior claim. ~4.5 times faster than std::stable_sort for uniform random integers is pretty impressive. Is this primarily from increasing the memory regions from 2 to 4 for parity merges / partitions? I'm benching on somewhat dated hardware and had mixed results (including slowdowns), so I never went further down that rabbit hole.
- orlp 4y ago
  Hi Igor, > It should be O(n log n) comparisons and technically O(n (log n)^2) moves. Yes, the same applies to glidesort. Looking at your repository again more carefully you do indeed only claim O(n log n) comparisons, I was not careful enough. > blitsort might qualify as O(n log n) moves when given sqrt(n) aux I have a similar conjecture for glidesort but I'll have to do some thinking to see if I can prove it. > In your Youtube presentation you do seem to skip mentioning that many of the performance innovations in glidesort were derived from quadsort and fluxsort. Some credit in your upcoming paper would be much appreciated. Good artists borrow, great artists steal. I do try to give credit where due though, so to clear my name... ...I do cite you in the presentation in the section on ping-pong merges (at 10 minutes in the presentation), and in the upcoming paper I do also cite you for what you call parity merges (something I did not use at the time of the presentation, but I do use now in the small sorting routine), where you don't have to do bounds checks when merging two equal-size arrays from both ends. As you could notice, I didn't have a large time slot for my presentation, so I could not go into more details regarding the branchless nature of merging and partitioning. I'll make sure to mention you in the paper for inspiring the out-of-place branchless partition as well. I do take full credit myself for making the bidirectional branchless out-of-place partition however: https://i.imgur.com/EiVi8Y2.png https://i.imgur.com/EiVi8Y2.png. > Feel free to email me if you have any questions, some things like my first publication of a "branchless" binary search in Aug 2014 may be hard to find, though there might be prior claim. I'll email you for sure, and I have a summary I posted on HN 7 months earlier as well: https://news.ycombinator.com/item?id=31101056 https://news.ycombinator.com/item?id=31101056. Hopefully this does show my good intent and that I have never tried to cover up the inspiration I took from your work. That said, glidesort does not use a branchless binary search. > Is this primarily from increasing the memory regions from 2 to 4 for parity merges / partitions? I'm benching on somewhat dated hardware and had mixed results (including slowdowns), so I never went further down that rabbit hole. I believe it is primarily from having multiple independent interleaved loops, which can use instruction-level parallelism. The speed-up is most significant on Apple M1, less so on my AMD Threadripper machine. I disagree with the term 'parity partition' entirely however, and when I say 'parity merge' I specifically refer to your trick where the optimization where bounds checks can be eliminated entirely when merging two equal-sized arrays. I call my partitioning method bidirectional partitioning. Similarly, how I see it is that every parity merge is a bidirectional merge, but not every bidirectional merge is a parity merge.

by orlp 4y ago

scandum 4y ago

It should be O(n log n) comparisons and technically O(n (log n)^2) moves. The moves are reduced by a relatively large constant however, and blitsort might qualify as O(n log n) moves when given sqrt(n) aux. In your Youtube presentation you do seem to skip mentioning that many of the performance innovations in glidesort were derived from quadsort and fluxsort. Some credit in your upcoming paper would be much appreciated. Feel free to email me if you have any questions, some things like my first publication of a "branchless" binary search in Aug 2014 may be hard to find, though there might be prior claim. ~4.5 times faster than std::stable_sort for uniform random integers is pretty impressive. Is this primarily from increasing the memory regions from 2 to 4 for parity merges / partitions? I'm benching on somewhat dated hardware and had mixed results (including slowdowns), so I never went further down that rabbit hole.

orlp 4y ago
Hi Igor, > It should be O(n log n) comparisons and technically O(n (log n)^2) moves. Yes, the same applies to glidesort. Looking at your repository again more carefully you do indeed only claim O(n log n) comparisons, I was not careful enough. > blitsort might qualify as O(n log n) moves when given sqrt(n) aux I have a similar conjecture for glidesort but I'll have to do some thinking to see if I can prove it. > In your Youtube presentation you do seem to skip mentioning that many of the performance innovations in glidesort were derived from quadsort and fluxsort. Some credit in your upcoming paper would be much appreciated. Good artists borrow, great artists steal. I do try to give credit where due though, so to clear my name... ...I do cite you in the presentation in the section on ping-pong merges (at 10 minutes in the presentation), and in the upcoming paper I do also cite you for what you call parity merges (something I did not use at the time of the presentation, but I do use now in the small sorting routine), where you don't have to do bounds checks when merging two equal-size arrays from both ends. As you could notice, I didn't have a large time slot for my presentation, so I could not go into more details regarding the branchless nature of merging and partitioning. I'll make sure to mention you in the paper for inspiring the out-of-place branchless partition as well. I do take full credit myself for making the bidirectional branchless out-of-place partition however: https://i.imgur.com/EiVi8Y2.png https://i.imgur.com/EiVi8Y2.png. > Feel free to email me if you have any questions, some things like my first publication of a "branchless" binary search in Aug 2014 may be hard to find, though there might be prior claim. I'll email you for sure, and I have a summary I posted on HN 7 months earlier as well: https://news.ycombinator.com/item?id=31101056 https://news.ycombinator.com/item?id=31101056. Hopefully this does show my good intent and that I have never tried to cover up the inspiration I took from your work. That said, glidesort does not use a branchless binary search. > Is this primarily from increasing the memory regions from 2 to 4 for parity merges / partitions? I'm benching on somewhat dated hardware and had mixed results (including slowdowns), so I never went further down that rabbit hole. I believe it is primarily from having multiple independent interleaved loops, which can use instruction-level parallelism. The speed-up is most significant on Apple M1, less so on my AMD Threadripper machine. I disagree with the term 'parity partition' entirely however, and when I say 'parity merge' I specifically refer to your trick where the optimization where bounds checks can be eliminated entirely when merging two equal-sized arrays. I call my partitioning method bidirectional partitioning. Similarly, how I see it is that every parity merge is a bidirectional merge, but not every bidirectional merge is a parity merge.