So now we have Orson, he's going to be talking about GlideSort, very beautiful opening slides,
so yeah, take it away.
Thank you.
Can everyone hear me?
All right.
Good.
Thanks for coming.
So my name is Orson, and I'm here to present GlideSort.
I did this research at the CBI Database Architecture Group, GlideSort.
What is it?
It's a general purpose, stable comparison sort here.
Does everyone here understand what that means?
No.
Oh, okay.
Well, good luck.
So stable means that it does not reorder equal elements.
They stay in the original order, so essentially it makes sorting deterministic.
GlideSort is a hybrid.
It's a hybrid of merge sort, quicksort, and block insertion sort, which is a variant of
insertion sort, and it is robustly adaptive to pre-sorted and low cardinality inputs.
Don't worry, I'll talk about what that means.
I made a reference implementation in partially unsaved rust, and you can think of it if you're
programming a rust as a drop-in for the slice stable sort algorithm.
So you might wonder, stable quicksort.
The answer is yes.
A guy named Igor von Den Hoven made a very, I don't know, he did very good work on flux
sort, where he showed that indeed you can do stable quicksort efficiently.
Wikipedia will tell you that quicksort is in place, that it is done using element exchanges,
and that it will literally tell you efficient implementations of quicksort are not a stable
sort.
Wikipedia tells you, no, you cannot do it.
Standard stable sort uses extra memory to do its sorting, and if you tell people, hey,
you can do the same with stable quicksort, they completely lose their minds.
No quicksort is in place, you cannot do that.
That's not true.
You can, and you probably should.
So earlier I mentioned adaptive sorting.
What do I mean by that?
To adapt is to change your behavior to deal with new information or a new situation.
And there are two ways that you can be adaptive, in my opinion, major ways you can be adaptive
in sorting.
And they correspond to two schools of sorting.
There is the bottom-up school of sorting.
Those are your merge sorts, or your mergers variance, like dimsort and powersort.
And they are bottom-up.
They construct larger and larger sorted sequences from smaller sort of sequences.
They are often presented in a schoolbook way top-down, but really fundamentally they are
bottom-up.
And that way they can be adaptive to pre-sorted runs.
If there's already pre-sorted running your input, you can just take that as is and continue
merging up.
There's also the partition school of sorts.
Those are your quicksort, your sample sorts, your radix sorts.
They partition out or distribute data.
They are fundamentally top-down.
You start at the higher, and you partition to smaller, smaller, smaller.
Subpartitions, and that way they can be adaptive to low cardinality inputs.
So what are low cardinality inputs?
Essentially you have a lot of data, and you're sorting it by a subset of the data.
So you're sorting your customers, but you're sorting them by which city they live in.
Or you're sorting your cars, but you're sorting by the brand of the car.
And even though you might have hundreds of thousands of cars, you might only have 100
brands.
So essentially duplicates, at least from the perspective of a comparison operator.
So how does adaptive quicksort deal with that?
The idea is that during partitioning, we can detect buckets of elements that are all equal
to each other.
And there's a challenge with doing that.
You don't want to do extra unnecessary comparisons.
And we actually want to avoid three-way comparisons.
That's a bit funny, because Rust's basic ORT trait uses three-way comparisons.
But that's a lie.
Under the hood, we turn that back into a two-way comparison, because computers aren't very
good at turner logic.
They really love binary logic.
They love ifs and else.
So we still turn that back into two-way comparisons.
And there's been a long history on adaptive quicksorts in this way, with Dijkstra and
Hauer, I still don't know how to pronounce that, working on it.
And already, time flies, eight years ago, I showed that in pattern defeating quicksort
that you can detect this and handle this very efficiently.
So how does that work?
I have an entire earlier talk on PDQ sort that you can watch if you're interested in
this.
But essentially, we have two different partition strategies.
A partition left and a partition right.
The partition left puts elements equal to the pivot on the left.
And the partition right puts equal elements on the right.
And what you do is, when you select a pivot, you check if that pivot is equal to a pivot
we used previously.
And you can do this efficiently using a single extra comparison during partitioning, or at
least pivot selection.
And the default is that you put the equal elements on the right.
But if you detect, hey, this pivot is equal to a previous pivot, you put equal elements
on the left.
And this way, you implicitly do a three-way partition using two-way comparisons.
And you can prove that, on average, this means that your sort is o n log k, where k is the
number of distinct values.
If every value is distinct, that becomes o n log n, we're used to that.
But if you have a lot of duplicate values, o n log k goes a lot faster than n log n.
There's also adaptive merge sort.
As I said earlier, these merge pre-existing runs in the input.
The problem with solving this is that you want to minimize the amount of unbalanced mergers
that you do.
So you don't want to merge a very large array with a very small array, because that's quite
inefficient.
And you also want to somehow store, during your algorithm, where the runs are in memory.
And if you do this in an illogical way, you have to potentially store a lot of data about
where all the runs are.
And Van Neumann invented merge sort very early, and Knuth described also quite early a natural
merge sort that takes advantage of pre-existing runs in the input.
And then, in particular, Tim Peters popularized Tim sort, which became the default sorting
algorithm in Python, that really showed the first sort of clever way to keep track of
your run information and minimizing unbalanced mergers.
The recent work is PowerSort, which extends on Tim sort essentially, or has the same logic,
but more clever logic, and actually has mathematical proofs that it creates balanced merge sequences.
And in fact, Python, I believe, now uses PowerSort's logic as well.
So I'm not going to go into detail on how PowerSort works.
I don't have enough time for that.
But essentially, the core loop of it is that you create a run, and that can either be
by finding the run in the input or doing a small sorting algorithm to create a small run.
You compute the power of a run.
That's the heuristics I'm not going to get into.
And then you keep a stack of runs, and then use this power heuristic that we computed
to decide when to merge two runs.
And you can prove that the stack then becomes logarithmic in size, and that your merge sequences
are going to be very good.
But yeah, the idea is that create a run can take advantage of existing runs in the input.
So a problem merges.
We want to be adaptive to low cardinality inputs, and we want to be adaptive to preexisting
run in input.
But one is fundamentally bottom up, and the other one is fundamentally top down.
And that's why I call this GlideSort.
We glide.
What do I mean by that?
Well, the idea is that a soaring bird only flaps its wings when necessary.
GlideSort only sorts when necessary.
So during this create run process, I'm sorry, before that, I changed the concept of a run
to a logical run.
And a logical run can be one of three things.
It can be just as before.
It can just be a sorted range of elements in your array, and can also be an unsorted
range of elements in your array, or two sorted ranges that are right next to each other in
your array.
We change the create run function.
We do, in fact, if there's a run in the input, detect that and return that as a sorted run.
But if we don't detect a sorted run, we just return an unsorted run.
We don't eagerly sort anything, and how you do that is very simple.
You just scan through the array, and if you find a run that we consider big enough, we
return it, and otherwise, we just skip some elements and return an unsorted run.
And then you add quite a bit of code for merging two runs, but it's actually relatively
simple.
As long as two unsorted runs concatenate it fit in our scratch base, which is essentially
this extra memory that blows people's minds, as long as it fits in that, we just concatenate
our unsorted runs.
And otherwise, we actively physically sort the elements using quick sort, and then create
one of these two sorted concatenated run cases.
If we have two sorted runs, we concatenate them.
If we have an unsorted run and something else, we actually sort this unsorted run and then
recurs.
And finally, we have our actual physical mergers.
So when we can no longer be lazy, we can no longer glide, we have to actually merge elements.
So that is essentially the main loop of glide sort.
So it's an extension of power sort, but you can apply the same logic to any natural stable
merge sort.
We don't eagerly sort small runs.
We keep them as unsorted runs as long as possible.
And this way, we transform the sorting problem into a sequence of quick sort calls and triple
slash quad merges.
And doing this, we are adaptive to pre-sorted runs and low cardinality inputs at the same
time.
So why triple and quad merges?
And there are three main reasons.
There's ping-pong merging, bidirectional merging, oh, sorry, before I want to quite clearly
mention something, Glider is not the first algorithm that is adaptive to both of these
categories at the same time, but to my knowledge, at least it is the first algorithm that is
robustly adaptive.
So it does not hard code anything, it does not use heuristics to decide when to switch
to which algorithm it detects this completely naturally based on the input.
So why triple slash quad merges?
There are three main reasons.
Ping-pong merging, bidirectional merging, and parallel merging.
Ping-pong merging is not my idea, it's found in two early projects, once again by Igor
van der Hove and an earlier paper, Pages is Virtue.
And the idea is that in a traditional merge, you copy out part of the data someplace else
and then merge back into the original array, that's an extra memcap.
With a triple slash quad or a quad merge, you can merge both into your scratch space
and on the way back, because essentially when you do an out of place merge, you get a mem
copy for free because you're moving to some other place.
So I think that's best described visually, if you have four, so in this case a quad merge,
you have four mer sorted runs, you merge two into your scratch space, you merge two
more into your scratch space, and you merge two back.
And now we eliminated three mem copies, so don't have to do that, that's one advantage
of being lazy with merging.
We can also do bidirectional merging, this, to my knowledge, was first done again by Igor
van der Hove in Quadsford, where he described a parity merge, where he showed a very clever
technique to merge two equal length arrays without any branch checks.
But then I thought by merging from both ends at the same time.
But then I thought, looked really into why that was fast and how can we extend that
and use that further.
So the idea behind a bidirectional merge is that if your destination and your source
arrays are disjoint, you can merge from both ends at the same time.
And then the pointer that's going from right to left does not interfere with the pointer
going from left to right.
These two logics are independent, essentially.
And it essentially looks like that.
Why?
Why do we want to do that?
Well, modern processors are quite different than what maybe your traditional processor
with your mental image are.
They are superscaler, that means they don't execute one instruction per cycle, no, they
can execute many instructions per cycle.
They are out of order, the processor will internally reorder your instructions based
on your assembly based on the data paths and when memory is available.
And they are deeply pipelined.
That means that they don't like it when the next instruction depends immediately on the
result of the previous instruction because it has to go through the entire pipeline of
the processor.
So to study that in a bit more detail, we look at a branchless merge, which was first
described in branch mispredictions don't affect merge source.
This is not the code that they used in this paper.
This is roughly translated from GlideSort.
You don't have to get into it, how it works.
The main important part is that you analyze where is the result used in the next slide.
Well, you find that generally all the data that's computed is needed immediately.
And the worst part of it all is that the next iteration cannot start really until the
previous iteration is finished.
You don't know if you're merging two arrays, you need to know, am I continuing with the
left array or am I continuing with the right array?
There's a lot of data dependencies.
So that is my main takeaway from GlideSort and my main low level design principle is
to interleave independent branchless loops.
So branchless is important, so the processor isn't jumping around and constantly canceling
your pipeline.
And by interleaving, we can hide some of these data dependencies.
The processor can execute multiple instructions at once and it can essentially reduce the
impact of having to constantly wait for the previous result.
You can also consider parallel merging.
So in this case, we had one merge where we did it in parallel from the left and parallel
from the right.
But we also noticed that the first step in our quad merge has two independent merges.
These are essentially parallel, but we're not using threads, but we can interleave
their loops.
So once I discovered that, I thought, let's create more parallelism.
By doing a binary search, you can identify a split point where you can turn one merge
into two smaller merges by swapping the right blocks in the middle.
I won't go into the exact logic of proof about that, but you can.
And in fact, if you are doing an out-of-place merge, you can do this swap implicitly by
just reassigning pointers.
So there's no actual physical mem copy going on.
However, if you're doing an in-place merge, you can actually do the physical swap.
And now you have for free a fallback for low memory merging.
So even if you don't have a large buffer available to merge with, you can use this algorithm
to do it in a low amount of memory.
Then I also optimized the quicksort portion of it with the same principle.
I came up with what I call bi-directional stable partitioning.
Again, I don't have time to get into it, but the idea is that we do, again, partition
like in quicksort.
So one set of elements that are less than the pivot goes somewhere else.
Go go here.
And some that are greater or equal go somewhere else.
But we do it from both the left-hand side to the right, and from the right-hand side
to the left.
And these two loops are independent from each other, so we can interleave them.
Same principle.
When you recurse, it gets a bit more involved, because now your data is in multiple different
locations.
I can tell you this is not fun to program, but I did it, and here it is.
So I do have some experiments to show you very briefly, an experiment of the setup.
So this is a lot of text that basically says a 2021 Apple MacBook.
And these are the numbers you would get on an Apple 2021 MacBook.
So at the top, I have two variants of GlideSort.
One is the default variant that you would get if you were to download it.
GlideSort 1024 is a variant that uses a fixed amount of memory, so 1024 elements of memory.
Then we have the Rust stable sort, the C++ standard stable sort, an implementation of
Tim sort, a PDQ sort, an older algorithm of mine, which is also the stable Rust sorting
algorithm, and the whatever shipped as the standard sort in C++.
You can read the slides yourself.
GlideSort is quite a bit faster than the Rust stable sort right now.
What isn't shown on this page are some more competitive algorithms, like Fluxort and Quadsort.
So they trade blows for blows on different data sets, but those are written in C, and
they don't have to deal with some of the problems that we deal with that I'll get to later in
my talk on sorting in Rust.
If you actually change your comparison operator, so we're only sorting by the last byte of
the integer, fun fact, if you do this, stability becomes even observable for integers.
GlideSort, again, speeds up even more compared to the Rust stable sorting algorithm.
So now we're over an order of magnitude faster for these data sets.
If you want to use it, good news, it's released.
It took me a while, but it's finally out.
You can just cargo add GlideSort, and you can replace your sort, call to Slidesort with
GlideSort.
If there are any standards library people in the audience come talk to me after the talk,
I would love to see it integrated, so you don't have to call GlideSort, and it would
just be done by default.
But this is a Rust dev room, so some of you at least probably are interested in Rust,
so I will also talk about some Rust specifics, so what it takes to implement a sorting algorithm
in Rust.
And first I'm just going to rant, unwinding panics, I think a Rust billion-dollar mistake.
They are complete nightmare.
If you are writing unsafe code and you've ever had to deal with panic, some people in
the audience are laughing, they're horrible, because essentially, since you can catch them
and we have to be sound and safe during a panic, they're essentially the same as C++
functions.
In C++, all these functions say if you throw an exception, tough shit, like your vector
is invalid now, too bad, it doesn't matter, you can't use it, you don't have the choice
in Rust, you have to always be safe and sound in Rust, ensuring that is a nightmare, especially
when you're dealing with generic code in unsafe code.
So if you're calling foreign code, anything you do, any call, can panic, which causes
an unwind.
So whenever you call a foreign function, you have to make sure that you are in a sound
and safe state.
The problem is every single trait is foreign code.
That clone call, that's foreign code.
This comparison operator, that's foreign code.
Lightning Glider was a complete nightmare, every time I compare two elements, that could
cause a panic, that could cause an unwind, and you saw all this stuff that I'm doing
with arrays all over the place, all of that has to be restored to the original location
because it's a mudslice, and you cannot leave a mudslice in an unsound or you can't leave
holes in it, everything has to be returned to the original array.
Yeah, it's a nightmare, I really wish we would just, instead of panicking, we would just write
out a stack trace and abort and be done with it.
I hate it, that's my rant.
Oh yeah, well, and in fact, GlideSort has an actual real performance penalty because
panics are a thing.
I can't just write a, like if you're writing an insertion sort, for example, in C++ or
in Python, you would just have a loop with a loop variable and you would put the items
in the correct place.
If you're implementing a thing like this in Rust and you're leaving gaps, so you're
moving the element out during the insertion sort, you have to have a drop handler that
puts this element back during a panic because this ORD implementation, this foreign code,
can cause a panic and cause an unwind.
So even when I'm sorting something like integers, which cannot panic, if I don't want to duplicate
my entire code base, I still have to pay this penalty for dealing with the potential for
panics by storing all my data, instructs, and all this algorithm state.
So yeah, that's a problem.
But I also want to praise Rust, where it is pleasurable.
I love that moves are mem copies.
There's no move constructor.
If you want to move a type somewhere else, you essentially just copy it and you ignore
whatever, wherever it came from.
This also makes optimizations possible that aren't possible in C++ because of move constructors,
at least not if you don't want to use like templates metaprogramming.
For example, instead of copying an element, this is an example actually from GlideSort,
not written like this, but where you place an element in one of two places, and if it's
going to the wrong place, it doesn't matter because it will just be ignored or overwritten
in the next iteration.
If it's a small type, just place it in both, don't do a branch.
So essentially, this is the opposite of unwinding panics.
There are no surprises.
A mem copy is always what you get.
This is not necessarily, it's part praise, part complaining.
Split at mutt, so splitting a slice into or more.
It's a one-way street.
You cannot go back.
Once it's split, it's split.
Unless you go back to the original object, but that's not always an option.
In GlideSort, when I concatenate these arrays, slices, I need actual concatenation.
My options were raw pointers, but that was the option.
You are storing an array with indices, but now you're storing an extra pointer everywhere
and passing an extra pointer everywhere, and that's overhead that I didn't want to pay.
So I came up with a thing I call branded slices.
You could hold an entire talk on this, but it's essentially applying the idea of a ghost
cell.
Some of you might have heard from this, where you essentially brand a type with a unique
lifetime that you cannot create.
You can only create this lifetime once, and it's not interchangeable with any other lifetime.
And with that, you can make safe concatenation.
So you could just check, is the end pointer equal to the begin pointer of the other array
if yes, we can concatenate?
And that will work, except that could also just be happening by chance because of the
local array layout on the stack, and you could create unsound behavior.
But if you know that they came from the same allocation, then it's safe to concatenate
them after checking and equals begin.
So that's what I did with what I call mudslice, which in GlideSword, every single slice is
a mudslice type, which has a brand, so you can do the safe concatenation, and it has
a state, which is one of five things.
It's weak on in it, maybe in it, in it, always in it.
Always in it, essentially, a mutable slice, so you always have to return it to initialization
state.
And maybe on in it, in it are a bit more specialized than just maybe on in it, where the type doesn't
really encode what it actually contains, and weak is essentially a pair of pointers.
And then the code becomes a lot more readable and a lot more verifiable by explicitly encoding
your assumptions about your slice type using the type, and then calling functions like
upgrades to say, hey, this now becomes an exclusive mutably slice.
I'm only going to access this here, or hey, I'm now going to temporarily invalidate this
initialization state of this slice.
That was essentially my talk.
I'm leaving academia, so if you have an interesting, potentially rust job, my contact details
are on the slides or come talk to me after the talk.
I'm not interested in cryptocurrency, Web3 or similar endeavors.
I love cryptography, but I don't know, some of this stuff gets rather sketchy, no offense.
That was essentially my talk.
I'm going to leave this on this slide.
Are there any questions?
I have a question.
Did you test Glidesort on, let's say, less modern CPUs, like embedded CPUs that don't
have auto-fordering execution, et cetera?
Yes.
Can you repeat the question, please?
The question was, did you test the algorithm on any older CPUs that might not have as much
instruction-level parallelism and that kind of stuff?
The answer is yes, and yes, it is slower than other state-of-the-art that don't do these
tricks.
This is really aimed towards essentially the future of modern processors.
From older CPUs, it is slower than, for example, flux sort, which doesn't do this aggressive
interleaving.
But if you compare it to the current Rust stable sort that's currently in the standard
library, it's still completely dumps us all over that.
Can you hear me?
Barely.
Can you speak loudly?
When you take two sort of sequences and you take the bottom half of one and the top half
of another and create a third sorted sequence out of that, I thought that was an interesting
observation, but what do you use it for?
So it's not the top half and the bottom half.
That's just the simplification.
You're talking about the splitting up merges into smaller merges, right?
Yes.
So it is not the top half and the bottom half.
It involves a binary search to find the unique split point that allows you to do this swap.
It could be bottom half, top half, but that's not necessarily the case.
What do I use this for?
It creates two independent merges.
After doing the swap, this merge no longer depends on this merge at all.
And by doing that, I can have two independent loops that merge these and then interleave
the bodies of these loops.
So it executes one instruction from this merge, one instruction from this merge, one instruction
from this merge, one instruction from this merge, et cetera.
And that way these instructions don't depend on each other and you can hide these data
dependencies and such.
On top of that, I use it as a fallback for the low memory case where you don't need,
so GlideSword can use less auxiliary memory.
We have a last question.
Thanks for the talk.
I would like to know if you have a bench.
I'm sorry, I cannot hear.
Can you speak a bit louder, please?
Did you bench when the array is already sorted?
Did I bench when the array is already sorted?
Yes.
Yes, it's on the slides.
Is it on the slides?
Yes, it's the ascending column on the slides and on this slide as well.
It's the one person.
Sorry?
It's the one person column.
No, ascending.
Ascent.
Okay.
Okay, that means sorted in this case and descending means reverse of sorted.
Okay, okay.
Thank you.
All right.
Thanks very much.
Thank you very much.