30 ms·
Branchless Quicksort faster than std:sort and pdqsort with C and C++ API
- davidkwast 5mo agoIt is so simple that I had to look very slowly to understand. Nicely done.
- NuclearPM 5mo agoIf it wasn’t simple you could look fast and understand?
- hyperhello 5mo agoIf 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 5mo agokind 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 5mo agoYes. 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.
- mgaunard 5mo agoAren't there several bitonic sort network implementations that are vectorized, Intel's in particular? Why not compare against that?
- orlp 5mo agoSince 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: 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) 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: driftsort 0.29s (stable) ipnsort 0.81s std::sort 1.15s std::stable_sort 1.63s (stable) blqs 1.89s
- vintagedave 5mo agoThis is very impressive work. 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 5mo agoIt's called driftsort because it's derived from another sort I made, glidesort: https://github.com/orlp/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 5mo agoThis comment didn't explain the name or how it works.
- deleted 5mo ago[deleted]
- kvuj 5mo 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?
- 4k0hz 5mo agoThere'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 5mo agoIsn’t there an implicit check to exit the loop?
- Tiddles-the2nd 5mo agoThe 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 5mo agoThere 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).
- quuxplusone 5mo agoIt'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 5mo 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.
- NooneAtAll3 5mo agowhy such love for copies tho? why look for trivial copy and not trivial move?
- chrka 5mo agoAuthor here. No, it's also called from the non_trivially_copyable branch (as a fallback). I'll fix that.
- dekdrop 5mo agoIf it's branch predicting, why would if statement run slow? How come unnecessary memory write is fine?
- tancop 5mo ago[dead]
- gblargg 5mo agoModern 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.
- teo_zero 5mo agoIn 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 5mo 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.
- deleted 5mo ago[deleted]
- deleted 5mo ago[deleted]
- kleiba2 5mo agofor (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]?
- gblargg 5mo agoIt only increments if the number was less than 500, effectively just saving the ones less than 500.
- defrost 5mo agonumbers[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.
- deleted 5mo ago[deleted]
- addaon 5mo 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 5mo agoI think the small_numbers array would differ after the end of the loop if, for instance, numbers contained only numbers >= 500. Am I wrong?
- teo_zero 5mo agoNitpicking the C variant: > #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.
- bagxrvxpepzn 5mo 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://mazzo.li/posts/value-speculation.html, https://yarchive.net/comp/linux/cmov.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.
- deleted 5mo ago[deleted]
- globular-toast 5mo agoI 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 5mo agoBranch 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.
- chrka 5mo agoBranchful 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.
- Tomte 5mo agoI‘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.
- globular-toast 5mo agoAnyone interested in branch-free code might like the book Hacker's Delight. Lots of examples of stuff like this in there.
- coldstartops 5mo agoHighly 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.
- Aardwolf 5mo agoOn 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
- benj111 5mo agoOff 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/ https://tiki.li/blog/ errors out. https://tiki.li https://tiki.li doesn't seem to have a link to the blog.
- deleted 5mo ago[deleted]
- chrka 5mo agoYou 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.