Blitsort: A fast, in-place stable hybrid merge/quick sort
github.com
github.com
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.
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.
> 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.
> 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. 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.
I was able to prove (on paper) that the whole algorithm was actually O(n log n). The moves seems to have a bad recursion pattern, but assuming my proof was right, it is possible to have a well behaved implementation in practice. However, the recursion pattern didn't fit the master theorem, I remember having to do a taylor expansion of some formula giving an upper bound on the number of computation steps to prove the O(n log n) bound.
And runtime measurements graph were showing the expected O(n log n) curve, as in your cases. So maybe they are not O(n log n ^ 2) as you feared... I did not keep much information from that time :P.
But that's such an effort in futility that I refuse to do so. So it's theoretically and practically in-place, but not technically.
If you are interested, I can try to recover the proof that the rotation step can be done in O(n), thus allowing to apply the master theorem on the main recursion and getting the O(n log n) result.
>I have a similar conjecture for glidesort but I'll have to do some thinking to see if I can prove it.
It probably is technically O(n (log n)^2) moves, but I suspect that when the rotations are fast enough (trinity / bridge rotations) the cost saving from localization nullify the additional moves.
>I do cite you in the presentation in the section on ping-pong merges
Wikisort does have prior claim to ping-pong merges, and it likely goes further back than that. I did independently implement them in quadsort.
>I do also cite you for what you call parity merges (something I did not use at the time of the presentation
This feels like a tricky claim to me, since I assume your bidirectional merge was fully inspired by my parity merge. If so you weren't the first to implement one, I did so while working on the parity merge, but I figured it was self-evident the 2x gain would apply for a more traditional merge, and I did state the gain was from accessing two memory regions in the quadsort article.
I've since made a quadsort release that uses a galloping 'bidirectional merge', though it still takes advantage of the parity principle, so properly speaking it's a bidirectional galloping parity merge hybrid that sorts 2 blocks of 8 elements at a time, without boundary checks for the 16 merge operations.
>As you could notice, I didn't have a large time slot for my presentation
I did take that into account, I guess it's human nature to get butthurt over stuff like this and I couldn't help myself from whining a little. It is better than bottling it up and I apologize if I caused you unease in turn.
>Hopefully this does show my good intent
It does, and I appreciate it.
>That said, glidesort does not use a branchless binary search.
I assume that's one of the advantages of building upon powersort? The blocky nature of quadsort is both a blessing and a curse in that regard.
>I call my partitioning method bidirectional partitioning.
I meant "parity merge" / "partition". If you think about it quicksort is naturally bidirectional, which is why branchless partitioning works without further work, and undoubtedly why it wasn't self-evident to most. I did try to write a bidirectional partition early on, but it's either my hardware or I messed up somehow.
I agree it's possible to write a bidirectional merge without utilizing the parity principle. One of the trickiest things in programming is properly naming things.
As for instruction-level parallelism, I do think it's actually almost entirely memory-level parallelism. I could be wrong though.
A nitpick, but my name is Orson Peters, Peters is my last name :)
> I assume that's one of the advantages of building upon powersort? The blocky nature of quadsort is both a blessing and a curse in that regard.
I don't know, I only use a binary search when splitting up merges, and almost no time is spent in this routine. I use this for the low-memory case, as well as to create more parallelism to use for instruction-level parallelism.
> As for instruction-level parallelism, I do think it's actually almost entirely memory-level parallelism. I could be wrong though.
I didn't do specific research into which effect it is, when I say ILP I also mean the memory effects of that.
I actually knew that, not sure what went wrong in my brain.
>I don't know, I only use a binary search when splitting up merges, and almost no time is spent in this routine.
You'll still get a definite speed-up, worth benching the difference just in case. I guess there's no easy way to avoid a binary search.
>I didn't do specific research into which effect it is, when I say ILP I also mean the memory effects of that.
They're indeed related. I did some empirical testing and I'm quite sure it's cache related. Thinking about it, one issue I may have had was not benching sorting 100M elements, which might be where a bidirectional partition might benefit on my system.
1) Is there a theoretical minimum assymptotic speed for sorting?
2) Some of these newer sorts seem to have arbitrary parameters in them (e.g. do X if size of set is smaller than Y). Are we likely to see more and more complex rule sets like that lead to increased sorting speeds?
2) I think things like cache and machine word size have huge impact on real world speed, so it makes sense to have knobs to tweak to fit within those limits, even enough a theoretical analysis does away with constants like that
I think it's worth clarifying that this is the best worst case possible, i.e for every sorting algorithm you could create a certain input in a way that it won't be able to beat O(nlog(n)). In other words, O(nlog(n)) is a minimum hard limit for worst case speed, no algorithm can do better than O(nlog(n)) on all possible inputs (but it can do better on some inputs, o(n) being the hard limit there).
I don't really remember the theory behind this, but hopefully someone here can answer: is it theoretically possible for a sorting algorithm to achieve sub-O(nlog(n)) speeds on 99.99% (or some other %) of randomly selected inputs? Or even O(n)?
Otherwise you can for instance sort an input made of zeroes and ones in O(n) time and O(log(n)) space by counting the ones.
No, you can get better than nlog(n) for specific cases that may happen a lot in practice, but not in the general case of randomly selected continuous inputs.
The explanation comes from information theory, and it is the same idea as for why you can't compress random data.
In essence, a sorting algorithm has to pick the correct reordering of the sequence, there are n! possible reorderings, so the algorithm needs log(n!) bits of information about the sequence, each comparison yields one bit, and log(n!) is asymptotically equivalent to nlog(n), so you need at least nlog(n) comparisons to cover every case. In practice, some reorderings are more common than others, in particular the "already sorted" case, so it is worth making your algorithm check these cases first, but on randomly selected inputs, these special cases represent a negligible fraction of all the possible cases.
I guess what I'm asking is how "specific" do these cases have to be, or how "general" is the general case? Can specific cases be 0.0001%? How about 1%?
You could also consider things like sleep sort or spaghetti sort: googling them I'll leave to the reader. Oh, and sorting networks are a good read too.
If we are sorting by comparison, then each comparison will eliminate at most half of the possible cases. So we need at least log_2(n!) comparisons in the worst case.
2) Hybrid algorithms, i.e. those that change the underlying strategy based on some parameters, are already quite common in real-world implementaions. Examples include timsort (stable, mix of merge sort and insertion sort), used in Python, Java, and Rust, and pdqsort (unstable, mix of quicksort and heap sort), used in Rust and Go.
Occasionally one is discovered and solved, and it can lead to a brief domino effect, but I have no idea how many are left.
I hope computer scientists will come up with something better than GC.
Pause time is not the same as cycle time, but it’s what’s important for reactivity.
[0] https://www.microsoft.com/en-us/research/uploads/prod/2019/0...
FWIW, I'm thinking of devices that don't have an MMU - like the Sega 32X. It's a hobby of mine. Having any GC time at all is too much suffering, even 1ms.
skasort_cpy is pretty good on 32 bit integers if you give it n auxiliary memory.
rhsort is very good and likely the best for 31 bit integers, but a bit rough around the edges still, and doesn't work well on arrays above 1M elements. Avoid radix sorts for 64 bit integers, they're ideal for 16 bit.
glidesort is promising, though I haven't seen it benched against the latest fluxsort / blitsort.
Timsort's main problem is that it's slow on shuffled arrays.
pdqsort and other introsorts aren't good on semi-ordered data.
https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...
It is slower than it's unstable brother, aptly named crumsort. https://github.com/scandum/crumsort
Radix sort is O[n] . (or [n * number of bytes in Int] or whatever is being compared).
It's omitted from the comparisons, I see. Radix sort can also have predictable memory overhead.
And djb's vectorized sorting networks are pretty great: https://sorting.cr.yp.to/
Edit: I misremembered, memory access is actually O(sqrt(N)):
I’m glad other people are having this conversation now and not just me.
All the time.
IP addresses
permutation arrays (⍋⍋)
Sometimes I pretend characters are numbers; short fixed-length strings (like currencies or country codes or even stock tickers) can be numbers.
If I can get away with it, a radix sort is better than anything else.
More often than not. Sorting by morton code, sorting by index, etc.
Stop faffing about with college text book solutions to problems like you’re filling in a bingo card and use a real database. Otherwise known as Architecture.
I haven’t touched a radix sort for almost twenty years. In that time, hardware has sprouted an entire other layer of caching. I bet you’ll find that on real hardware, with complex objects, a production-ready Timsort is competitive with your hand written radix sort.
> and use a real database.
I'm not going to use a database to store tens of billions of 3D vertices. And I'm not going to use a database to sort them, because it's multiple times, probably orders of magnitude faster to sort them yourself.
It's weird to impose completely out-of-place suggestions onto someone who does something completely different to what you're thinking of.
In high performance systems, constant time random access is just not constant.
Nothing theoretical about it: Sorting a list of all IP addresses can absolutely and trivially be done in O(N)
> in reality you can't do better than O(log N)
You can't traverse the list once in <N so the complexity of any sort must be ≥N.
> but memory access is logarithmic
No it's not, but it's also irrelevant: A radix sort doesn't need any reads if the values are unique and dense (such as the case IP addresses, permutation arrays, and so on).
> Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench
It's not that either.
The author ran out of memory; They ran a program that needs 10GB of ram on a machine with only 8GB of ram in it. If you give that program enough memory (I have around 105gb free) it produces a silly graph that looks nothing like O(√N): https://imgur.com/QjegDVI
The latency of accessing memory is not a function of N.
This is not generally relevant for PCs because the distance between cells in the DIMM does not affect timing; ie. the memory is timed based on worst-case delay.
No, you can clearly see the O(sqrt(N)) trend at every level of the memory hierarchy.
Lines goes up, then goes down. Very much unlike sqrt.
How could it not be, given that any physical medium has finite information density, and information cannot propagate faster than the speed of light?
And on a practical computer the size of N will determine if you can do all your lookups from registers, L1-L3, or main RAM (plus SSD, unless you disable paging).
You could have a tape of infinite length, and if you only ever request "the next one" then clearly the latency is constant.
> And on a practical computer the size of N ...
Don't be silly. N is the size of the input set, not the size of the universe.
In this way, radix sort is usually faster than an "omniscient sort" that simply scans over the input writing each element to its final location in the output array.
EDIT: Retracted -- did a search like for "license", but apparently the search results omits variants like "sublicense" which would have caught the MIT license at the beginning of the source file: https://github.com/scandum/blitsort/search?q=license vs. https://github.com/scandum/blitsort/search?q=sublicense