14 ms·
Show HN: Glidesort, a new stable sort in Rust up to ~4x faster for random data
Hi all, I've talked about glidesort a few times on HN already, but it's finally ready for release. If you have any questions, feel free to ask. An academic paper on glidesort that goes into a lot more detail than the readme is upcoming, but is not ready yet.
I will be giving a talk on glidesort tomorrow at FOSDEM 2023 in the Rust Devroom at 16:10, you can seek me out there as well. In other news, I am leaving academia soon, so if you have interesting (Rust) jobs the coming months feel free to approach me.
- cdiamand 4y agoPretty neat! So it looks like you have a few things happening in parallel. What is instruction level paralellism and how does it speed the sort up?
- deleted 4y ago[deleted]
- orlp 4y agoModern processors execute out-of-order (reordering instructions) and are superscalar (they execute more than one instruction per cycle). By providing multiple independent data paths in the tight merging/partitioning loops we can keep the CPU busier than a traditional merge/partition loop and have higher throughput. Note that this all happens on a single thread, this is in addition to thread-level parallel sorting (which glidesort does not (yet) have). Also note that this is different than SIMD, which processes more data in a single instruction. This can give you incredible speed-ups, but the code is very dependent on the data (e.g. code for sorting integers looks very different than sorting strings with SIMD). Glidesort is written using scalar code with fully generic comparison functions, no SIMD-specific speedups.
- repsilat 4y agoWould a simple example of this be something like, > In a traditional "merge" algorithm, the second comparison depends on the output of the first, so it can't be done at the same time. So it might make sense to merge "from the left" and merge "from the right" at the same time because those things can be done in parallel when both arrays have length > 1. ?
- orlp 4y agoThat is exactly right.
- timerol 4y agoThe ability to work with different memory sizes is pretty intriguing. How does the algorithm decide where and when to allocate?
- orlp 4y agoThe allocation always happens once, at the start of the algorithm. The default allocation size is hard to describe in plain English, whereas the code is quite readable: const FULL_ALLOC_MAX_BYTES: usize = 1024 * 1024; const HALF_ALLOC_MAX_BYTES: usize = 1024 * 1024 * 1024; fn glidesort_alloc_size<T>(n: usize) -> usize { let tlen = core::mem::size_of::<T>(); let full_allowed = n.min(FULL_ALLOC_MAX_BYTES / tlen); let half_allowed = (n / 2).min(HALF_ALLOC_MAX_BYTES / tlen); let eighth_allowed = n / 8; full_allowed.max(half_allowed).max(eighth_allowed) } Essentially the default allocation size is a linear graph M(n) = n until 1 MiB, where it will plateau until overtaken by M(n) = n / 2 until 1 GiB, where it will once again plateau until overtaken by M(n) = n / 8. Note that this is only the default, you can pass glidesort a buffer with a size/location of your choice and it will use that instead.
- timerol 4y agoI used the word "allocate" imprecisely. (The plain English description in the README did a good job of explaining the up-front allocation needs.) What I meant to ask: How does the algorithm stay bounded in memory usage? Is glidesort written in such a way to never use more memory than that? Is the some sort of back-pressure mechanism, when most of the allocated memory is in use, and another operation is ongoing? Basically: when sorting a 1 GiB array of data, how does the algorithm keep from using more than 128 MiB of additional memory? Nothing in the "Technique Overview" section mentions bounded memory use (under n bytes, at least).
- orlp 4y ago> How does the algorithm stay bounded in memory usage? Is glidesort written in such a way to never use more memory than that? It does not ever allocate more than what it allocated at the start. > Is the some sort of back-pressure mechanism, when most of the allocated memory is in use, and another operation is ongoing? Yes and no. I did write some code that will make glidesort back off and use less memory if the allocation request fails: https://github.com/orlp/glidesort/blob/master/src/lib.rs#L206 https://github.com/orlp/glidesort/blob/master/src/lib.rs#L20... The sad part is that this will probably never work in reality due to overcommit. > Basically: when sorting a 1 GiB array of data, how does the algorithm keep from using more than 128 MiB of additional memory? By allocating 128 MiB at the start, and never allocating more than that. Maybe what you really want to know is: how can it do merges in space (much) smaller than the input? The answer is by (recursively) splitting merges into two separate smaller merges using an in-place block swap. You can see this in action at the 10 to 12 second mark here: https://user-images.githubusercontent.com/202547/216675278-e4c8f15c-e42d-4224-b8c7-fdc67fdc2bde.mp4 https://user-images.githubusercontent.com/202547/216675278-e... Because I use block swaps and not rotations, this block swap can often be done implicitly (just not in the case of low-memory fallbacks) by re-assigning buffer names rather than physically moving elements.
- ww520 4y agoHope to see the video of the presentation at FOSDEM.
- deleted 4y ago[deleted]
- kzrdude 4y agoIt's already up (haven't watched through yet) https://fosdem.org/2023/schedule/event/rust_glidesort/ https://fosdem.org/2023/schedule/event/rust_glidesort/
- mlochbaum 4y agoAny source available for your benchmarks here? I'd like to benchmark against pdqsort, fluxsort, etc. but the existing benchmarks use C so I either have to call glidesort from C or write my own Rust benchmark to get any numbers at all.
- orlp 4y agoNot yet. I do aim to have open code for a benchmark including pdqsort, fluxsort, etc, accompanying my upcoming paper on glidesort. This would be in a separate repository. That code is very much... 'academic' right now, and needs polishing before release. To compare across languages I simply implemented the exact same benchmark twice, once in Rust and once in C++.
- nwmcsween 4y agoSo how does this compare to PDQ, Crum, flux, etc? Do you have preliminary results?
- deleted 4y ago[deleted]
- kzrdude 4y agoNote that the author also is the author of PDQ. And there was some prior discussion on HN here: https://news.ycombinator.com/item?id=33827843 https://news.ycombinator.com/item?id=33827843
- orlp 4y agoI have some preliminary results I can share from the current draft paper: https://i.imgur.com/AUOJ1w0.png https://i.imgur.com/AUOJ1w0.png https://i.imgur.com/AP6DnIS.png https://i.imgur.com/AP6DnIS.png Note that the four bottom sorts (RustSort, StdSort, Pdqsort, IPS4o) are not stable. GlidesortN is glidesort using n elements of memory, Glidesort is the default memory setting and Glidesort1024 uses a fixed 1024 element buffer. Arm is a 2021 Apple M1, Amd is a 2018 Threadripper 2950x.
- moonchild 4y agoIs ips4o parallelised here?
- orlp 4y agoNo, it is running serially. IPS4o is inherently more cache efficient due to having a very wide partition operator, making it better on machines with smaller caches, and better in general for strings (where no matter how cache-local your algorithm is, the string pointer indirection mostly destroys it).
- scandum 4y agoThose are some awfully large array sizes. Not something I ever had the patience for to sit out, or optimize for, as it didn't seem like the most common real-world scenario. One thing glidesort appears to do extremely well is to branchless merge till the very end, this gets quite tricky when memory constrained. It does not seem worth it intuitively, but judging from the performance of rotate mergesort, it probably is.
- 10000truths 4y agoI'm interested in seeing a comparison with blitsort. Like glidesort, it's stable, adaptive, and can be configured to use constant auxiliary memory.
- orlp 4y agoI haven't done a comparison yet (because I haven't gotten to really benchmarking the low-memory performance), but I will include it in the paper. The fact that glidesort can use small amounts of memory is honestly a happy coincidence of the merge-splitting technique I do that I only realized during development, and was not a primary goal.
- scandum 4y agoIf the last presentation's benchmark still goes, blitsort is significantly faster. Keep in mind that glidesort is partly derived from fluxsort and many of its techniques were directly inspired by fluxsort/quadsort, while several others are implemented in a similar or near-identical manner. This is in my opinion not adequately explained in the presentation on youtube. The main difference is that glidesort uses timsort's approach to adaptive sorting rather than quadsort's, though it uses quadsort's novel method for cost-effective branchless merging. Glidesort tries to access 4 memory regions instead of 2, primarily with the bidirectional partition, an approach I implemented in 2021, but rejected because it was causing degraded performance for expensive comparisons. This does however result in a very different visualization which can give the impression it is unrelated. The general approach to stable partitioning is likely nearly identical to fluxsort. As for why blitsort is fast, it's likely due to trinity rotations and monobound binary searches. Possibly also a more optimal overall partitioning strategy. I haven't spend too much time on blitsort however, so there are likely further improvements to be made.
- orlp 4y ago> Keep in mind that glidesort is partly derived from fluxsort and many of its techniques were directly inspired by fluxsort/quadsort, while several others are implemented in a similar or near-identical manner. This is in my opinion not adequately explained in the presentation on youtube. We've had an extensive email discussion on this, and I still have to publicly provide counterweight. Yes, I did look at fluxsort/quadsort (mostly the README descriptions) while developing glidesort, I did get inspired by fluxsort's stable quicksort performance. And I did take quadsorts 'parity merge' idea for small sorts, as I described here 9 months ago: https://news.ycombinator.com/item?id=31101498 https://news.ycombinator.com/item?id=31101498. I'm open about this. But you're not the first to do branchless merging, I was already aware of that in "Branch Mispredictions Don't Affect Mergesort". Ping-pong merges turns out were already described in "Patience is a Virtue: Revisiting Merge and Sort on Modern Processors". The observation that the reason the 'parity merge' was so fast being instruction-level and memory-level parallelism is my own (you added this to the README after I publicly described this in the above linked comment). That we can then use it more generally as a bidirectional merge is my own. Using merge splitting and lazy merging to then apply this to more merges is my own. Interleaving multiple independent merge loops is my own. Extending the quicksort to then also use bidirectional partitioning is also my own idea (I don't have a crystal ball about you implementing and rejecting the idea in 2021). My pivot selection is my own. The whole extension of powersort to use lazy merging and more merge splitting for ping-pong merge opportunities is my own. The novel robustly adaptive combination of merge and quicksort is my own. I've spent months and months optimizing glidesort. Glidesort tackles problems fluxsort/quadsort don't even have to worry about in being unable to copy values, only move them, and dealing with panics from user-provided comparator functions, and comes out with minimal losses. You do great work Igor, but I would appreciate it if you would stop try to claim mine as (mostly) yours.
- mlochbaum 4y agoI was able to get glidesort running as part of the Robin Hood sort benchmark[1]. See [0]; it's a lot slower than fluxsort on random data. Wondering if I did something wrong. Is cargo build --release with rustc 1.64.0 enough? Tried lto = "thin" in .cargo/config as well, which is ever so slightly faster. Also tried passing in a buffer one, then two, times the input length which didn't change things. Was this tested on x86? Commands to run to replicate my results are below. Clone rhsort and run them in that directory. The res/*.txt results are human-readable but you have to install my programming language[2] to generate the plot. Hey, you made me program in Rust. [0] https://gist.github.com/mlochbaum/7664a046d294dcce2f6cdb1db6ab4600 https://gist.github.com/mlochbaum/7664a046d294dcce2f6cdb1db6... [1] https://github.com/mlochbaum/rhsort https://github.com/mlochbaum/rhsort [2] https://github.com/mlochbaum/BQN https://github.com/mlochbaum/BQN ./wolfbench.sh mkdir res gcc -O3 -D NOTEST bench.c && ./a.out l > res/r_rh.txt gcc -O3 -D FLUXSORT -D NOTEST bench.c && ./a.out l > res/r_flux.txt gcc -O3 -D WOLFSORT -D NOTEST bench.c && ./a.out l > res/r_wolf.txt g++ -w -fpermissive -O3 -D SKACOPY -D NOTEST bench.c && ./a.out l > res/r_ska_.txt cd glide && cargo build --release && cd .. gcc -O3 -D GLIDESORT -D NOTEST bench.c -Lglide/target/release -lglide LD_LIBRARY_PATH=glide/target/release ./a.out l > res/r_glide.txt images/line.bqn res/r_{flux,wolf,ska_,glide,rh}.txt > images/rand_glide.svg
- orlp 4y agoTry running with the latest nightly Rust (`rustup update nightly`) and with `cargo +nightly build --release`. EDIT: I'm sorry, you need to specify this in your Cargo.toml, my earlier command was incorrect: glidesort = { version = "0.1.1", features = ["unstable"] } To get the best performance I use specialization for Copy types (such as integers) to compete with the assumptions that fluxsort and such can make, which is not available on stable Rust (unless glidesort were to be merged into the standard library). Without that I have to be more conservative with bounds checks. And even then there's a variety of places where I sacrifice performance compared to fluxsort and such in the name of safety, and the limitations that Rust gives me (in particular panic safety has cost me 10-15% performance). Also when you say x86, I assume you mean x86-64? I have not tested raw x86. What is your actual processor? EDIT 2: I believe this should also go in the Cargo.toml of glide in your repository, not in a .cargo/config [profile.release] lto = "thin"
- nerdfaktor42 4y agoLooking forward to your talk tomorrow :)
- nathell 4y agoThis got me thinking about sorting. I wonder how many times per day (or, indeed, per second) my computer does sorting of any kind. I just checked a largish codebase I'm working on, and about 0.12% SLOCs invoke the standard library's sort. But that's just a random codebase. What about the kernel, the browser, the VMs, the graphical subsystem of the OS? Could I capture all these sorts' inputs to generate My Real-Life Sorting Corpus of One Day's Worth of Data? And then compare the performance of different sorting algorithms on that corpus? I'm pretty sure this kind of research has been done before. Can someone point me towards relevant literature?
- rightbyte 4y ago> Could I capture all these sorts' inputs to generate My Real-Life Sorting Corpus of One Day's Worth of Data? You could wrap the lib containing the sort function and write the input to some file. It is easy of it is C at least.
- nathell 4y agoIt is easy enough to wrap libc's qsort() with LD_PRELOAD, sure. The problem is heterogeneity: qsort() is by far not the only sort implementation the machine is running. Even identifying them all might be a daunting task, not to mention figuring out how to wrap them.
- mtlmtlmtlmtl 4y agoSounds like the sort of thing dtrace or bpftrace might be able to do.
- anacrolix 4y agosorting and searching are like 50% of what the CPU ever does. the benefits of ground breaking improvements there are huge. makes me think of proebsting's law, I don't know if this applies here.
- saagarjha 4y agoNot at all. Try running perf against your computer and you’ll see differently.
- olliej 4y agoSeriously working on the default/built in sorting implementation must suck. You can make the theoretically optimal choice, but get utterly hosed because in practice you get the “wrong” distribution of input data. I recognize that in practice vs in theory is often an issue and have had to deal with it myself in the past, but seriously sorting seems specifically awful to deal with.
- vba616 4y agoOn the rare occasion I need to roll my own sort, I go for Heapsort, even though it isn't stable, because it's the simplest n log n worst case option I know.
- olliej 4y agoOh yeah, there are occasions it might be necessary - a more feeling bad for the people writing the generic system/platform ones that have to be magically "the best" for everyone all at the same time, and feeling glad that's not my problem :D
- loxias 4y agoAnyone have a C++/C port yet? :) Would love to try this out, though the source looks... difficult for me to do a naive port.
- kzrdude 4y agoI think it's fair to say "quicksort is not stable" if you want. You need some definition of what the parameters of the algorithm is, when you describe it. What should be mentioned is that there's a variant (requiring memory XYZ) that is stable. It would be fair to call it a variant of the quicksort algorithm.