Since pdqsort (an older project of mine) was mentioned, I felt it wouldn't be entirely inappropriate to mention that I've since then collaborated with Lukas Bergdoll to provide two high-quality sort implementations for the Rust standard library, ipnsort (unstable) and driftsort (stable).
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:
I 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.
orlp 10 hours ago [-]
It's called driftsort because it's derived from another sort I made, glidesort: https://github.com/orlp/glidesort. Glidesort is a bit faster still for large inputs, however it was too large and complex for inclusion in the standard library, and suffered from code size penalties on small inputs. So driftsort is a slimmed down version more appropriate for general purpose.
CyberDildonics 3 hours ago [-]
This comment didn't explain the name or how it works.
orlp 3 hours ago [-]
It's just a play on words, something lightweight drifts in the wind rather than gliding on a wing. It's really not all that deep.
CyberDildonics 2 hours ago [-]
How does that relate to the mechanics of the algorithm?
conradludgate 39 minutes ago [-]
Does quicksort explain the mechanics of the algorithm?
tialaramex 11 hours ago [-]
Thanks for everything Orson! I know Clang struggled to ship improved sorts for their C++ implementation, so it's a good sign that Rust was able to ship ipnsort and driftsort without too much chaos.
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!)
quuxplusone 5 hours ago [-]
FWIW, I believe that's not a mistake, just a consistent use of (novel?) jargon. From context I infer that the paragraph is distinguishing between the _hard requirements_ of the traits (quote: "the language contract says they cannot become unsafe") and the behavior human programmers would naturally _expect_ of the traits ("the social contract").
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.
tialaramex 4 hours ago [-]
I take your point but I do still think it's a violation here, if I see a type which implements Hash and Eq this doesn't feel like a reasonable outcome to me.
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.
tambre 6 hours ago [-]
> I know Clang struggled to ship improved sorts for their C++ implementation
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++.
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.
kleiba2 13 hours ago [-]
for (int i = 0; i < 1000; i++) {
small_numbers[smlen] = numbers[i];
smlen += (numbers[i] < 500);
}
is much faster than the conventional version with a conditional branch:
for (int i = 0; i < 1000; i++) {
if (numbers[i] < 500) {
small_numbers[smlen] = numbers[i];
smlen += 1;
}
}
Been staring at this for a bit, but my brain is not working properly today: could someone please explain how these to loops compute the same value for small_numbers[smlen]?
edelind 11 hours ago [-]
Here is another perspective:
- 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
bhaak 11 hours ago [-]
They don't. After running, for the values in small_numbers from 0 to smlen-1 they are equivalent.
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].
addaon 13 hours ago [-]
> "these two loops compute the same value"
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.
kleiba2 7 hours ago [-]
I think the small_numbers array would differ after the end of the loop if, for instance, numbers contained only numbers >= 500. Am I wrong?
Ukv 7 hours ago [-]
smlen would be 0 for both if there are no small numbers, so end result of both is an empty array.
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.
davrosthedalek 7 hours ago [-]
The point is that you should look only at the first smlen entries, which would be 0 for this case.
teo_zero 12 hours ago [-]
Writing to array[n] and not incrementing n means that the value just written is outside the "useful" range (from 0 to n-1) and will not be considered (it will be overwritten the next iteration).
zelphirkalt 12 hours ago [-]
I am rather thinking, if one is so much faster, and they are truly equal, why is the compiler too stupid to convert one into the other?
br121 10 hours ago [-]
It doesn't convert bogosort into heapsort either, despite the second being much faster than the first. I'm guessing that it's not that easy going from one to the other because the only thing they have in common is the output (and only after you have checked the last value), so if the transformation is not hard-coded into the compiler, the odds of it randomly discovering the optimization is close to zero
zelphirkalt 10 hours ago [-]
Yeah, I would expect such transformations to be implemented as optimizations. Just like maybe (the admitedly simpler):
(+ ((lambda () 1)) ((lambda () 1))) -> (+ 1 1)
A syntactical transformation, where it is possible as an equivalent transformation.
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.
flohofwoe 11 hours ago [-]
The two code snippets do different things, apples and oranges... e.g. the array modification in the second example needs to move in front of the if for the two snippets to behave identically. I bet then the compiler output is the same with -O1 or higher.
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:
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).
11 hours ago [-]
gblargg 13 hours ago [-]
It only increments if the number was less than 500, effectively just saving the ones less than 500.
jcul 12 hours ago [-]
First version has a side effect of writing to small_numbers[0] always.
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.
9 hours ago [-]
defrost 13 hours ago [-]
numbers[i] < 500
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.
9 hours ago [-]
bagxrvxpepzn 12 hours ago [-]
> On modern CPUs, avoiding branch misprediction is a key technique to speed up programs.
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.
chrka 11 hours ago [-]
Branchful only wins via ILP when data becomes good predictable. But since Quicksort partitioning aims for a 50/50 split, it operates in the worst possible zone for a branch predictor. That's why branchless wins here, as proven by the benchmarks.
adrian_b 7 hours ago [-]
I do not agree to call "exceptions" the cases where branchless code is preferable, because they can be quite frequent in certain application domains, like sorting and searching.
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.
12 hours ago [-]
globular-toast 11 hours ago [-]
I was thinking that... When they say "modern CPUs", surely that includes any pipelined CPU? Maybe Pentium 4 era long pipelines in particular. But actual modern CPUs are much better at branch prediction.
But for something like sorting wouldn't the worst case be completely random data which would defeat any kind of branch prediction?
adrian_b 6 hours ago [-]
Branch prediction is indeed necessary for any pipelined CPU. It does not matter whether the CPU also has other more modern features, like being superscalar, having out-of-order execution, etc.
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.
quuxplusone 17 hours ago [-]
It's unfortunate that the C++ version of the code assumes the type T is default-constructible (and that the default constructor is cheap). It also assumes that the type T is copy-constructible; at a glance I can't tell if the algorithm depends on making a copy in every place that it does make a copy. E.g. in the `heap_sort` helper we have
T k; // default-construct
if (i > 0) k = left[--i]; // copy-assign
This fairly obviously could be replaced with "copy-construct." Could it be replaced with "move-construct"? I don't know.
Again, in `partition_small`, we have
T swbuf[SMALLPART];
which default-constructs a bunch of Ts. I think we're just going to overwrite that memory in a moment anyway, so constructing all those Ts is a waste of cycles; but I'm not sure.
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)".
quuxplusone 17 hours ago [-]
...Ah, `heap_sort` is used only for trivially copyable types. So my complaint about not distinguishing copy from move is essentially unimportant (matters only in pathological cases that we shouldn't worry about).
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.
chrka 12 hours ago [-]
Author here. No, it's also called from the non_trivially_copyable branch (as a fallback). I'll fix that.
NooneAtAll3 14 hours ago [-]
why such love for copies tho?
why look for trivial copy and not trivial move?
mgaunard 21 hours ago [-]
Aren't there several bitonic sort network implementations that are vectorized, Intel's in particular?
Why not compare against that?
jeffbee 20 hours ago [-]
Great question. It would also be fair to ask how this behaves with non-random inputs. The benchmarks in the repo only use random values.
20 hours ago [-]
mswphd 20 hours ago [-]
Funny: you can cf "sorting network", and see they use them within their own design even.
Tomte 11 hours ago [-]
I‘m always a bit envious when I see those branchless styles. In my day job I have the obligation to hit 100% modified condition/decision coverage, and I‘m daydreaming about having just one control flow through everything, in order to save module tests that only test the umpteenth condition combination.
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.
davidkwast 21 hours ago [-]
It is so simple that I had to look very slowly to understand. Nicely done.
NuclearPM 21 hours ago [-]
If it wasn’t simple you could look fast and understand?
hyperhello 20 hours ago [-]
If it wasn't simple, there would be more lines of code to implement the same idea. As it is, he might have had to spend an hour understanding one line to understand that idea (1 line/hr slow), as opposed to spending an hour reading a hundred lines of code (100 line/hr fast) for the same result.
pasquinelli 17 hours ago [-]
kind of the flip side of pascal's "I would have written a shorter letter, but I did not have the time." if someone does have the time to make the letter short, it'll take longer to read (where "read" means to grasp the subtleties of.)
Brian_K_White 14 hours ago [-]
Yes.
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.
kvuj 18 hours ago [-]
>On modern CPUs, avoiding branch misprediction is a key technique to speed up programs. This branchless approach:
>
>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?
josephg 17 hours ago [-]
Nah. (numbers[i] < 500) is an expression which evaluates to true (1) or false (0). Evaluating this doesn't require a branch. There are instructions on modern CPUs to turn this expression into a number without a conditional jump. (cmp (compare), setle (set if comparison was less than or equal), then add).
> 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:
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.
aw1621107 14 hours ago [-]
If you hoist small_numbers[smlen] = numbers[i] out of the if statement then the compiler will produce nearly the same branchless assembly for both cases (the only difference being compare against 499 followed by setle vs. compare against 500 followed by setl).
Taking a second look I want to say you need to hoist the assignment for the loops to be semantically identical anyways.
14 hours ago [-]
rotifer 16 hours ago [-]
At the bottom of the page there's a link, "When ‘if’ slows you down, avoid it" [1], that discusses these exact questions. It's basically what @josephg said, but it also shows the assembly language for each version.
There's no branch in that code either way. The comparison operator outputs a value (which is arithmetic, not a branch), and that value is added unconditionally.
achandlerwhite 17 hours ago [-]
Isn’t there an implicit check to exit the loop?
Tiddles-the2nd 17 hours ago [-]
The check isn't important; what's important is being predictable so the CPU can guess which way the check will go. I don't know exactly how it works, but after the first couple of loops, the predictor will assume it's always going to end up in the loop and make that the fast path. It may guess wrong the first couple of loops, and the last check wrong, but the other 997 will be correct.
grumbelbart2 13 hours ago [-]
There is a static branch predictor that is used if there is no statistic on a branching instruction yet, and it's really simple: Jumps backward are assumed to be taken (they usually are from a loop), jumps forward are assumed to be not taken.
So the jump that forms the loop will be predicted correctly for all executions but the very last (when the loop ends).
Panzer04 10 hours ago [-]
That's very cute.
I wonder how much more complicated and effective statistical predictors are.
hyperhello 10 hours ago [-]
They get much more complicated, but their effectiveness tops out where certain branches just can’t be predicted in advance.
cstrahan 17 hours ago [-]
“that code” refers to the body of the loop.
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).
13 hours ago [-]
Aardwolf 10 hours ago [-]
On what datatype though, e.g. for sorting arbitrary length strings? I think that is if the comparator is expensive, quicksort and variants do not win because they do a constant factor more comparisons
18 hours ago [-]
dekdrop 17 hours ago [-]
If it's branch predicting, why would if statement run slow? How come unnecessary memory write is fine?
teo_zero 13 hours ago [-]
In modern CPUs a mispredicted branch is much more expensive than a memory write.
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).
josefx 10 hours ago [-]
> In modern CPUs a mispredicted branch is much more expensive than a memory write.
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.
gblargg 13 hours ago [-]
Modern processors are pipelined, where they run a lot in advance of when the result is needed. A mispredicted branch requires throwing out all the advance calculations on the incorrectly followed path. The branch predictor can't predict branches like this based on data that tends to equally be distributed for taken and not taken. The memory write is fine because it's not conditional, so it can be pipelined along with everything else.
11 hours ago [-]
tancop 13 hours ago [-]
[dead]
globular-toast 11 hours ago [-]
Anyone interested in branch-free code might like the book Hacker's Delight. Lots of examples of stuff like this in there.
coldstartops 10 hours ago [-]
Highly recommend. The exampels are in c/c++ and the same concepts can be ported to other languages like golang.
My favorite part of it is Chapter 2 the bit manipulation tricks.
benj111 8 hours ago [-]
Off topic. But how are you supposed to explore that website? There seems to be no way to look at other blog posts, https://tiki.li/blog/ errors out. https://tiki.li doesn't seem to have a link to the blog.
chrka 7 hours ago [-]
You will now see the directory listing. This website was actually created for my primary side project:
a simplified programming language for beginners. I just added a blog folder there for other things as well.
7 hours ago [-]
Rendered at 18:52:10 GMT+0000 (Coordinated Universal Time) with Vercel.
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:
And now for a cool party trick, let's repeat the 50 million doubles experiment again, but have the first 90% already sorted, last 10% random:I 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.
- 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].
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.
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.
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).
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.
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.
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.
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.
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.
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?
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.
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.
>
>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?
> 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.
[1] https://tiki.li/blog/branchless
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).
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.
My favorite part of it is Chapter 2 the bit manipulation tricks.