Branchless Quicksort faster than std:sort and pdqsort with C and C++ API
tiki.li
tiki.li
So if you use Rust, you get these by simply calling [T]::sort(_unstable). Great performance out of the box :)
On my machine (Apple M2), using the benchmarks from the repository on Apple clang 17 and Rust 1.98 nightly:
Sorting 50 million doubles:
ipnsort 0.79s
blqs 0.90s
driftsort 1.13s (stable)
std::sort 1.22s
std::stable_sort 4.64s (stable)
Sorting 50 million (i32, i32) structs:
ipnsort 0.82s
blqs 0.89s
driftsort 1.07s (stable)
std::sort 3.09s
std::stable_sort 3.15s (stable)
driftsort 0.29s (stable)
ipnsort 0.81s
std::sort 1.15s
std::stable_sort 1.63s (stable)
blqs 1.89sI looked at your paper[0] and was curious why it was named "drift" sort. Even searching for 'drift' didn't show me. I mainly ask because this is noted as a stable sort and the word 'drift' implies movement; I did not expect it, from the name, to be a stable sort.
Also, Lukas looked over my `misfortunate` crate (which provides "perverse" implementations of safe Rust traits) and although misfortunate isn't intended for testing he has inspired me to improve the perverse implementations of Ord, not for testing per se but to further illustrate. It occurs to me I should point anybody reading misfortunate's documentation at your/ Lukas' work in case they actually need really nasty tests not just mild perversion.
but that's not a violation of the contract, it's just a hash collision. Hash collisions are expected to happen, so HashMap and HashSet won't "misbehave seriously", they'll just be slow (linear-time lookup) and unable to remove entries.
The contract of Hash is that if two values are equal, then they hash to the same value. Which would be violated by doing the opposite of Maxwell: all values equal each other, but their hash differs (you can even make it random so it changes across calls on the same value!)
And yes, looking at https://docs.rs/misfortunate/latest/misfortunate/index.html and Ctrl+F'ing for "social contract," I see that usage very consistently. The entire point of Misfortunate is that its types correctly implement the language contract, while violating the "social contract" in various surprising ways. For example, causing a hash collision on every operation is a perfectly cromulent implementation of Hash, but violates the "social contract" of Hash. For another example, look at LoadLetter — throwing an error on every operation is a valid implementation of Read, but still violates the "social contract" of what a human programmer would naturally expect from something readable.
Do you have a better way to describe how Maxwell<T> works here? Or, failing that, an idea for a type which you feel can be perverse in a more interesting way here?
By the way (though you should not design things where this happens) you can alway remove things from a HashMap (or HashSet) because such collections provide e.g. retain and extract_if which both take callables, your callable is given a reference to each thing in the collection and asked if you want it, they behave differently and have different intended purposes but either will let you fish out a NaN you mistakenly stored in an ordered collection for example.
Clang has no built-in sorting algorithms. I imagine you're referring to the LLVM project's libc++? Though all common distributions of LLVM default to GCC's libstdc++.
https://blog.rust-lang.org/2024/09/05/Rust-1.81.0/#new-sort-...
> #define BLQS_CMP(a, b) ((a) < (b))
A function that returns true when one operand is Less Than the other, should be called BLQS_LT. The CMP abbreviation is idiomatic for a function that returns -1,0, or 1.
for (int i = 0; i < 1000; i++) {
small_numbers[smlen] = numbers[i];
smlen += (numbers[i] < 500);
}
for (int i = 0; i < 1000; i++) {
if (numbers[i] < 500) {
small_numbers[smlen] = numbers[i];
smlen += 1;
}
}
is a conditional (true or false) that evaluates to 1 or 0 (in C)
Therefore smlen has either a 0 or a 1 added to it's value .. equivilent to only adding 1 if True.
At what sequence point? The branchless version writes to small_numbers[smlen], for any given value of smlen, potentially more than once; so there are observable points of time during the loop where the behavior is different. But after the loop, both contain the final write to small_numbers[i] for all 0 <= I < smlen; and the transient writes both don't change observed external behavior, and are apparently cheaper than fewer but conditional writes.
For the first version small_numbers[0] will contain an arbitrary value at the end, and for the second version it happens to contain the last number read, but that address is outside of the 0-length array being returned.
PS: e.g. note how bla() (first code snippet) and blob() (fixed second code snippet) have identical output (both are turned into the same 'branchless' code via a conditional 'setl' instruction), but the blub() function (original second code snippet) differs because that function has different behaviour:
https://www.godbolt.org/z/h9Kfbn5bc
TL;DR: most 'branchless advice' that only tinkers with language features (like "x = a ? b : c" instead of an if) is useless because to the optimizer passes both are the same thing (a condition).
When there's a difference in the generated code then it's usually a bug and the before-after code are not actually equivalent (like in the code examples above).
(+ ((lambda () 1)) ((lambda () 1))) -> (+ 1 1)
I may be overlooking special cases, but I thought the compiler is smart enough to infer that the array elements are integers and that `<` will result in a boolean, which is just `0` and `1` and will understand that having only the `if` without `else` branch is equivalent in this case. Guess I was wrong and the compiler is not sophisticated in this specific way.
The compiler probability can't optimize that in the second version.
If it wrote unconditionally and incremented only in the if then I'd guess they would compile to the same thing.
- the first one (branchless) use the condition to SAVE the correct value (< 500): it temporarily writes any current value to the same index i, always overwriting the previous value, effectively saving it (by moving forward to i+1) only when the value is right (small number). Downside of this simple function: the last value may be bigger than 500
- the second one use the condition to ADD the value, when it is 100% sure it is a correct small number
But if the last value of numbers[] is not smaller than 500, small_numbers[smlen] will contain that value for the first version whereas the second version does not write to small_numbers[smlen].
The former preliminarily adds all numbers to the array but only keeps the small ones.
As long as you don't look at the small_numbers[smlen] element after the loop, they behave identically.
This is true but it's misleading. The reality is that modern out-of-order superscalar CPUs are so good at branch prediction that it's nearly always better to branch in a tight loop (to allow more ILP) than introduce a data-dependency in a tight loop (which limits ILP). Cf. https://mazzo.li/posts/value-speculation.html, https://yarchive.net/comp/linux/cmov.html
Branchless code should generally be avoided because modern CPUs are not designed to optimize that use case. There are exceptions of course, but those are exceptions.
But for something like sorting wouldn't the worst case be completely random data which would defeat any kind of branch prediction?
That is why the simplest kind of branch prediction, i.e. static branch prediction, had already been implemented in an early pipelined computer, the IBM Stretch, which was designed around 1959/1960, so it is hardly a "modern" computer.
When the result of a comparison is random, which happens frequently in certain kinds of sorting or searching applications, as you say, that defeats any kind of branch prediction.
The difference between the cases when branches are worse and the cases when they are better, is whether the tested condition is random (i.e. unpredictable) or not.
Whenever you compare a random number with a threshold (or two random numbers between themselves) and use the result for conditional execution, that is an example where using branches is worse.
In most cases, when writing a program it is easy to estimate whether branches will be predictable or not, and in the latter case branchless methods should be used.
T k; // default-construct
if (i > 0) k = left[--i]; // copy-assign
T swbuf[SMALLPART];
All of my "I don't knows" and "I'm not sures" are due to my own lack of digging into the code; I'm sure one could find out if one really looked.
None of that matters if you're just sorting `int` or the benchmarked `struct entry`. But it matters a great deal if you're taking the README literally and trying to sort "types with higher copy costs [...] (such as strings)".
But it's perfectly possible for a type to be "trivially copyable" without being "default-constructible." An example of such a type from the STL: `std::reference_wrapper<int>`.
Anyway, looks like a quick fix for this would be to just extend the list of traits on which blqsort is gated (currently `is_trivially_copyable` and `sizeof(T) <= 16`) by adding `is_trivially_default_constructible<T>::value` also.
why look for trivial copy and not trivial move?
Why not compare against that?
>
>for (int i = 0; i < 1000; i++) {
> small_numbers[smlen] = numbers[i];
> smlen += (numbers[i] < 500);
>}
Excuse my terrible ignorance but isn't there still a branch? If numbers[i] < 500 then 1 else 0? I would think something like addition plus a bit comparison would avoid said branch. Unless compilers already optimize the code, but then wouldn't they also optimize the naive piece of code?
So the jump that forms the loop will be predicted correctly for all executions but the very last (when the loop ends).
I wonder how much more complicated and effective statistical predictors are.
Unless the loop is unrolled, yes, there is a branch to exit the loop. But then that doesn’t matter because the whole goal at the beginning was to avoid branch misprediction (which is not the same thing as avoiding branches entirely).
> then wouldn't they also optimize the naive piece of code?
Great question. They do sometimes!
In general, the problem for compilers is that its not obvious which method would be better in some given piece of code. Most branches are highly predictable. Like, imagine a for loop which counts to 1000. At the end of the loop body, the code branches to see whether we should stay in the loop, or exit the loop. The first 999 times through the loop we keep going - so 99.9% of the time, the branch ends up taking the same path. Its very predictable! CPU designers optimise heavily for this, via branch prediction logic. Highly predictable branches run fast. (This is also why array bounds checking doesn't really hurt performance at all.)
But the branch predictor really struggles when the condition is unpredictable - ie, when a conditional branch is taken about 50% of the time. As is the case in a sorting algorithm.
The compiler has no idea whether any condition in your code is predictable or not. There are hints you can use, but it often defaults to just doing whatever you ask it to do.
Here's what the compiler actually does with the code you quoted. You can see the extra branch + jump for the second version of the code:
https://c.godbolt.org/z/zv7Tcd49f
I clicked around - for some reason even using __builtin_expect_with_probability, none of the compilers I tried will convert from one version of this code into the other.
Taking a second look I want to say you need to hoist the assignment for the loops to be semantically identical anyways.
Having the compiler convert a conditional store to an unconditional store can have bad consequences if you have interrupts or task switches or SMP going on, so it's not a good idea to do it -- unless you can guarantee that the thread of execution the compiler can see is indeed the only one. Yeah, yeah, volatile and barriers etc... still, not a good idea.
But merely the word simple isn't the best. Replace simple with elegant.
It can be quite hard to fully and correctly understand a small perfect thing.
If it gets 20 different jobs done without 20 different if statements, it's small and elegant, and simple to impliment, but not simple to understand (maybe simple to think you understand it.)
20 if statements you understand immediately and with no effort.
Obviously, readable code wins, but at least once I had the computing time budget to be able to have a central function go straight through by calculating all five or so variations (it was about several kinds of encodings of the output values) and just pick the correct one in the end. That felt good.
My favorite part of it is Chapter 2 the bit manipulation tricks.
The unsaid assumption is that the array is filled with random values between 0 and 1000, so the "if" condition has a 50% of chances to be true. The branch is mispredicted 50% of times.
Of course this trick won't work when the statement protected by "if" is a more complex and costly action, or one that can't be undone (in the example, note that when the counter is not incremented, the value written to memory will be overwritten in the next cycle, so it's "undone" in a certain way).
Mostly because of caching. The writes either go to the same address as a previous one or move only a small increment, so most writes are likely going to hit L1 cache. If it wrote to a random memory location after every iteration the cost of a misprediction would probably disappear in the noise.
Branch prediction works when the CPU can detect some kind of pattern in the program behavior, like if the branch usually goes one way and rarely goes the other way. If it predicts correctly, the CPU pipeline keeps going without stalling. If it predicts incorrectly, the CPU wastes time doing work that it has to throw away. Therefore, being able to predict correctly is essential.
In quicksort, you partition an array into two halves based on whether each element is smaller or larger than the pivot value. The key to good quicksort performance is to choose a good pivot which divides the values in half about equally. This means (assuming you're sorting randomly-ordered data) that the branching behavior will be totally unpredictable, like flipping a coin. So branch prediction will be basically useless.
Copying small chunks of data is OK if it all fits in cache, especially if it all fits in L1 cache. It's not ideal to copy data unnecessarily, but if it allows you to keep the CPU pipeline running at full speed with no stalls, it can be a good trade-off.