Show HN: Glidesort, a new stable sort in Rust up to ~4x faster for random data

by orlp • 3 years ago

389 70 3 years ago

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• 3 years ago

Pretty 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?

orlp16• 3 years ago

Modern 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• 3 years ago

Would 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.

ww520• 3 years ago

Hope to see the video of the presentation at FOSDEM.

kzrdude7• 3 years ago

It's already up (haven't watched through yet)

https://fosdem.org/2023/schedule/event/rust_glidesort/

timerol4• 3 years ago

The ability to work with different memory sizes is pretty intriguing. How does the algorithm decide where and when to allocate?

orlp16• 3 years ago

The 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.

timerol4• 3 years ago

I 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).

mlochbaum7• 3 years ago

Any 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.

orlp16• 3 years ago

Not 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• 3 years ago

So how does this compare to PDQ, Crum, flux, etc? Do you have preliminary results?

orlp16• 3 years ago

I have some preliminary results I can share from the current draft paper:

https://i.imgur.com/AUOJ1w0.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• 3 years ago

Is ips4o parallelised here?

scandum10• 3 years ago

Those 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.

kzrdude7• 3 years ago

Note 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

10000truths• 3 years ago

I'm interested in seeing a comparison with blitsort. Like glidesort, it's stable, adaptive, and can be configured to use constant auxiliary memory.

orlp16• 3 years ago

I 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.

scandum10• 3 years ago

If 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.

orlp16• 3 years 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. 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.

mlochbaum7• 3 years ago

I 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/7664a046d294dcce2f6cdb1db6...

[1] https://github.com/mlochbaum/rhsort

[2] 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

orlp16• 3 years ago

Try 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"

mlochbaum7• 3 years ago

Updating my system, going to take a little while... Partner in crime dzaima has tested (nightly, unstable, lto) and found it is somewhat better. Eyeballing, still ~20% slower than fluxsort. We're on fairly old Intel x86-64 CPUs, i5-6200U for me and i3-4160 for him.

Does panic safety really cost 10-15% when sorting integers according to default comparison?

scandum10• 3 years ago

I recently upgraded fluxsort, you might want to give v1.1.5.4 a spin. I also updated the benchmark to use actual natural runs and be less favorable to rhsort, sorry. ;-)

I'm not surprised fluxsort is slightly faster, it's heavily optimized for gcc -O3.

Since the primary techniques that give glidesort it's speed were copied from fluxsort and quadsort I'm expecting very similar performance, and possibly significantly worse performance on strings due to accessing 4 memory regions.

Have you gotten it working with the wolfsort benchmark?

mlochbaum7• 3 years ago

I did actually test out 1.1.5.4 in advance of this. I just used saved results instead of the new version for comparison because performance appears very similar on random inputs. I do see a lot of improvement in quadsort and most of the special-case benchmarks.

I was planning to update my repository to grab the appropriate files from the fluxsort repository but if you'd update the wolfsort repo I wouldn't have to. Although maybe I should switch over to cloning fluxsort instead.

nerdfaktor42• 3 years ago

Looking forward to your talk tomorrow :)

nathell2• 3 years ago

This 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• 3 years 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.

nathell2• 3 years ago

It 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• 3 years ago

Sounds like the sort of thing dtrace or bpftrace might be able to do.

anacrolix• 3 years ago

sorting 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.

CyberDildonics• 3 years ago

This is not true. Power and transistor wise most of what a CPU does isn't even about running instructions, it is instruction reordering, cache, speculation, prefetching, write queueing and other techniques to minimize the effects of memory latency.

Instruction wise this is not true either. Sorting is a O(N log n) problem and log n is never going to be above 64. A cpu spending lots of time sorting implies that it is constantly throwing away the sorted results.

adgjlsfhk1• 3 years ago

Pretty sure something like 80% of CPU time and power is spent pointer chasing in bad OO code.

saagarjha• 3 years ago

Not at all. Try running perf against your computer and you’ll see differently.

olliej2• 3 years ago

Seriously 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• 3 years ago

On 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.

olliej2• 3 years ago

Oh 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• 3 years ago

Anyone have a C++/C port yet? :)

Would love to try this out, though the source looks... difficult for me to do a naive port.

kzrdude7• 3 years ago

I 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.

Show HN: Glidesort, a new stable sort in Rust up to ~4x faster for random data

Related Stories