13 ms·
Lomuto's Comeback
- zengid 6y agoI love this sort of "Historical Fiction" where interactions and conversations between The Great People of Science are imagined and portrayed. A great example of this is Louisa Gilder's wonderful book _The_Age_Of_Entanglement:_When_Quantum_Physics_was_Reborn https://www.amazon.com/Age-Entanglement-Quantum-Physics-Reborn/dp/1400095263 https://www.amazon.com/Age-Entanglement-Quantum-Physics-Rebo...
- mhh__ 6y agoAnthony Zee's Quantum Field Theory textbook takes a similar tone.
- mwcampbell 6y agoOh, I assumed that dialogue between Lomuto and Hoare was real -- at least the gist of it, if not the exact words.
- zengid 6y agoThe interaction was probably real, since there is a date and location, but the dialog (and certainly the narration) seems to be taking some artistic liberties perhaps? This is also what Louisa did in her book on the history of quantum mechanics; real interactions with imagined dialogs. My apologies if I gave the wrong impression.
- gumby 6y agoThanks for writing his because I hated it — I read that par thinking it would shed some light on the topic of the paper at large, but it was just noise to me. Which is not to imply that I am right and you wrong or vice versa! Simply to observe that people are different. As I liked the article but was annoyed by that beginning, it’s great for me that the first comment I saw was yours. So thanks for making it.
- turndown 6y agoIf you enjoy books like that, I recommend The Cambridge Quintet[0]; it's a wonderful book. 0. https://www.amazon.com/Cambridge-Quintet-Scientific-Speculation-Helix/dp/0738201383 https://www.amazon.com/Cambridge-Quintet-Scientific-Speculat...
- cozzyd 6y agoWriting branch-free code (which I find myself sometimes doing to take advantage of simd vectorization) is always really painful. I wonder if someone has made an attempt at better tooling for this.
- klyrs 6y agoI tend to use the same method as the author has presented. 1. Write your branchy code 2. Massage the branches until their code is identical (testing frequently) 3. Trim a useless branch, and eat a piece of chocolate
- tomcam 6y agoI don’t mind boasting that I’m a world class talent at part 2 of step 3
- repsilat 6y agoOne thing people have made is array languages. The "primitive" operations apply to arrays of data, so branches around individual elements can't be expressed. I think it's also generally less expressive, though. Writing Lomuto's partition as efficiently would likely be impossible, but writing it branch-free might not be -- you would compose branch-free primitives like left = filter(array, array < array[0]) right = filter(array, array > array[0]) where `filter` is branch-free and takes an array of Boolean values as its second argument. Shrugs, aside from some standard set of functions/primitives and idioms I'm not sure it would help much, though perhaps a mindset-shift is a more likely solution than something more technical.
- VHRanger 6y agoThis sort of vectorised pseudo branching is often used in SIMD algorithms
- cozzyd 6y agoYes... and the transformations are often non-trivial (especially when considering the possibility of out-of-bounds elements, which can't just safely be multiplied by zero--they might be a NaN, or on the edge of a page). It would be nice if there was a tool (or compiler option!) that could convert my branchy code into an "identical" (assuming floating-point associativity, etc.) branchless version.
- mehrdadn 6y agoNotice that this is on random longs. Of course branch misprediction and memory bandwidth is going to crush you for a branchy sort... you'll be wrong like half the time, and the comparisons and swapping are trivial! Real world data isn't random, so I'd expect branch predictors to do much better with recognizing patterns. And your sorting isn't going to be as simple as sorting integers according to their values all that often. It's a neat exercise, but absent more realistic benchmarking to the contrary, I wouldn't assume I'll get a faster program by just substituting even a typical quicksort with this...
- repsilat 6y agoMaybe? Lots of people replaced their sorting algorithms with Tim-Sort because runs of alrealdy-sorted data are empirically common (at least in some workloads). I've seen it myself, in use-cases where sort keys change slightly from iteration to iteration in some larger algorithm, and sort items need to be dynamically kept in order. It no doubt also happens when grabbing data from multiple places, each of which is theoretically ordered arbitrarily but is in practice ordered predictably. So yeah, the author picked the use-cases where this algorithm is going to show in its best light. But that's not bad either, right? Data is often not well-ordered -- if you're counting occurrences of words, and want to get an ordered list (and never mind that you wouldn't use a comparison-based sort for that) you wouldn't expect much order. Likewise sorting any keys/values from a decent hash table. One worry that I would have applies specifically to C++ and D: sometimes values are big, and copies are expensive. But I guess users can always choose to sort pointers like other languages do, if the standard library uses a copy-heavy, branch-light algorithm.
- TeMPOraL 6y agoI think one example of extremely unsorted data is random data in Monte Carlo simulations, in particular if you need to compute statistical summaries that need the data to be sorted - e.g. percentiles. So you may end up repeatedly sorting million-long random arrays many time a second. Then again, maybe there are algorithms letting you compute percentiles without sorting?
- codeflo 6y agoI’ve read that some vector instruction sets use masking instructions to avoid branching. You execute both arms of the conditional and discard the unwanted computation, which can be cheaper than an X% chance of a branch misprediction. Should CPUs include more masking instructions for regular, non-vectorized code as well?
- banachtarski 6y agoI’m unconvinced because the instruction set sizes are already becoming fairly bloated (increasing microcode translation cost and i-cache pressure) but also because CPUs already do speculative execution which has a nearly equivalent effect to the idiom you’re referring to. *edit: wording
- MauranKilom 6y agoTo be more precise, some CPUs do the "both sides of the conditional" execution (EDIT This link is incorrect! Refer to "Eager execution" in the last link below. /EDIT https://en.wikipedia.org/wiki/Eager_evaluation https://en.wikipedia.org/wiki/Eager_evaluation) - years ago I heard that mobile processors do so for power reasons. No idea if that's still the case. The problem in question is due to predictive execution in which the CPU has to flush the pipeline on misprediction. This is dominant in desktop PC CPUs. I have no knowledge on what is prevalent in e.g. server or mobile CPUs. Both are (according to https://en.wikipedia.org/wiki/Speculative_execution https://en.wikipedia.org/wiki/Speculative_execution) forms of speculative execution.
- banachtarski 6y agoI'm speaking broadly about desktop/console CPUs which I have low-level familiarity with. I don't know of any CPUs in this class that don't perform some form of speculative execution. I'm not sure if eager evaluation is related to the topic at hand and was speaking specifically about speculative execution. Eager evaluation is just what pretty much every language except Haskell (or Haskell-like) does.
- eloff 6y agoIf you have a branch free algorithm, you can vectorize it. If he discussed implementing this with SIMD instructions (whether by human hand or compiler auto vectorization) I missed that part. But that seems an interesting angle to me.
- kccqzy 6y agoNot necessarily. A branch-free algorithm can totally have a data dependency from the previous iteration of the loop to the next, making it impossible to vectorize.
- eloff 6y agoThat's true, although there are sometimes workarounds for that by modifying the algorithm to iterate over a small groups where there is still a data-dependency between iterations, but not within each group, allowing one to use SIMD. e.g. instead of delta compression over an array of integers where you subtract each integer from the prior one, you can subtract each group from the prior one with only a small loss of compression ratio. The question is, is there such a dependency in this algorithm? I didn't check.
- klyrs 6y agoYes, sorting typically (and this one specifically) has long dependency chains. The natural reflex is to split the chains across multiple workers... and that's how you get merge-sort. But even the last pass has a linear dependence chain. Not long ago, somebody posted a clever algorithm based on 4-way swaps, which is a clever way of addressing the issue. Edit: I can't seem to locate that 4-way swapping algorithm, I swear it was posted to HN in the last year... somebody halp!
- kccqzy 6y agoYou might be thinking of this: https://news.ycombinator.com/item?id=22322967 https://news.ycombinator.com/item?id=22322967
- Arcuru 6y agoReminds me of this paper on binary search, which also shows a speed up using branch-free comparisons. "Array Layouts for Comparison-Based Searching" https://arxiv.org/pdf/1509.05053.pdf https://arxiv.org/pdf/1509.05053.pdf
- gautamcgoel 6y agoReminds me of this great article on writing a fast mergesort: http://pvk.ca/Blog/2012/08/13/engineering-a-list-merge-sort/ http://pvk.ca/Blog/2012/08/13/engineering-a-list-merge-sort/
- kleiba 6y agoTo anyone interested in a deeper treatment of quicksort and variants thereof, I can recommend Sebastian Wild's PhD thesis on that topic: https://kluedo.ub.uni-kl.de/frontdoor/deliver/index/docId/4468/file/wild-dissertation.pdf https://kluedo.ub.uni-kl.de/frontdoor/deliver/index/docId/44...
- bachmeier 6y agoOff topic: Is it common practice for a dissertation at a German university to be written in English?
- DaiPlusPlus 6y agoYes - to ensure the widest possible audience. English is the lingua-franca of academia and has been for almost a century now.
- kkaefer 6y agoDepends on the field, but it is very common in computer science and generally in natural sciences. Studying computer science, I don’t think I ever even wrote as much as a paper in German; everything’s English.
- kleiba 6y agoHardly anyone is going to read, let alone cite your work if you were to publish in German. I'm not even aware of any German-speaking conferences.
- ipsofacto 6y agoThere's an even better branch-free (super scalar) sorting algorithm: "In-place Parallel Super Scalar Samplesort (IPS4o)" which we started using: https://github.com/SaschaWitt/ips4o https://github.com/SaschaWitt/ips4o https://arxiv.org/abs/1705.02257 https://arxiv.org/abs/1705.02257 As an example, to sort 10 million random longs on my computer it takes std::sort 766 ms (roughly in line with Andrei's numbers) and ips4o::sort takes 274 ms. [edit:formatting]
- goldenkey 6y agoYou might want to mention if are affiliated with the algorithm you are promoting. ipsofacto ~ ips4o
- ComputerGuru 6y agoOr maybe the throwaway was named after the comment it was intended to be used to post.
- ipsofacto 6y agoNo affiliation, just picked the name because it fit... The company I work at was exploring various sort algorithms to use and this turned out to be the fastest. Another benefit of this algorithm is that it is parallizes extremely well.
- deleted 6y ago[deleted]
- phkahler 6y ago2x-3x improvement doesn't seem like much for something that runs in parallel.
- ipsofacto 6y agoThe 274 ms is for the sequential version of the algorithm (on my i7-9750 laptop). On my office Xeon E5-2690 machine when using multiple threads the runtime decreases like this 840 ms for std::sort 372 ms for IPS4o sequentially 201 ms for 2 threads 104 ms for 4 threads 53 ms for 8 threads 33 ms for 16 threads
- eqvinox 6y agoSo what's the impact of the data dependency chain on "first -= smaller" to the next iteration? (I guess at the very least it prevents vectorization, but other than that ... shouldn't be too much, but probably still the new limiting factor?)
- nightcracker 6y agoHoare partitioning can also be implemented in a branchless manner, my algorithm pdqsort does this: https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort
- andralex 6y agoThanks! I tried that too, but it's slower than Lomuto. Forgot to mention in the article.
- nightcracker 6y ago> I tried that too, but it's slower than Lomuto. That is very strange. I can not reproduce your results in C++, using your code. On my machine (Threadripper 2950x, 64 bit Windows 10, GCC 10.1.0 from MSYS2 MinGW64) my algorithm performs best and your branchless version ends up slower than your branchy one: $ g++ -std=c++17 -O3 -DNDEBUG -DLOMUTO lomuto.cpp && a 10000000 min_milliseconds=828.1250 median_milliseconds=890.6250 $ g++ -std=c++17 -O3 -DNDEBUG -DLOMUTO_BRANCHY lomuto.cpp && a 10000000 min_milliseconds=671.8750 median_milliseconds=671.8750 $ g++ -std=c++17 -O3 -DNDEBUG -DPDQSORT lomuto.cpp && a 10000000 min_milliseconds=343.7500 median_milliseconds=343.7500 On an Intel university machine (Xeon E5-2667 v2 @ 3.3GHz, 64 bit Ubuntu 16.04 LTS, GCC 5.4.0) I get: $ g++ -std=c++17 -O3 -DNDEBUG -DLOMUTO lomuto.cpp && ./a.out 10000000 min_milliseconds=514.8051 median_milliseconds=536.1984 $ g++ -std=c++17 -O3 -DNDEBUG -DLOMUTO_BRANCHY lomuto.cpp && ./a.out 10000000 min_milliseconds=688.2471 median_milliseconds=698.9603 $ g++ -std=c++17 -O3 -DNDEBUG -DPDQSORT lomuto.cpp && ./a.out 10000000 min_milliseconds=340.1935 median_milliseconds=344.7432 Maybe AMD or Windows doesn't like your branchless code or perhaps GCC is generating inferior code for AMD/Windows, as at least on Intel/Linux your Lomuto branchless code can beat the branchy code. But pdqsort (which uses branchless Hoare partitioning) consistently beats both. I didn't change the benchmark, I only added pdqsort to yours, my full changes are the simple inclusion of 1 header and 3 lines of code: https://github.com/orlp/lomuto/commit/29381176f49e3588f6882ca992cbb04f0c19c5f5 https://github.com/orlp/lomuto/commit/29381176f49e3588f6882c... In order for any interested readers to reproduce, simply clone https://github.com/orlp/lomuto https://github.com/orlp/lomuto and run the above commands.
- Ericson2314 6y agoI'm not sure I've ever sorted an array or list. Rather I put things into sets or maps or built in index---I always wanted to access things later, or have an on-line data structure (which a sorted flat thing is not). This whole field is a waste of time, and anachronism from when the master copy was paper/pre-computer and computers were just doing the analytics.
- ComputerGuru 6y agoYour dismissal of “sorted flat thing” as being necessarily not online is incorrect or unnecessarily strict to your detriment. I wrote this comparing the high-level performance of a “set” (AVL or red-black tree) against just that: Faster lookups, insertions, and in-order traversal than a red-black or AVL tree [0] [0]: https://neosmart.net/blog/2019/sorted-list-vs-binary-search-tree/ https://neosmart.net/blog/2019/sorted-list-vs-binary-search-... (Spoiler: it depends on the nature of your data, but sorted vector can be dramatically faster.)
- Ericson2314 6y agoTo be clear I am not against "small sorted flat thing" is an optimization for smaller data structures. My point is I care about the map or set interface. I don't use temporary sets or quicksort to sort....because I don't sort---I don't want a list/array of things in order, basically ever.
- ComputerGuru 6y agoYes, and what I showed you is a set with a set interface, internally implemented as an always-sorted list.
- Ericson2314 6y agoOK sorry, Yes creating a map/set using the small-size optimization is internally doing a sort.
- deleted 6y ago
- ncmncm 6y agoIt is true that more swaps may be cheaper than fewer swaps. The operations to count, nowadays, are not swaps or comparisons, which are very cheap, but instead pipeline stalls, which are very, very expensive. It is easy to better-than-double the speed of vanilla quicksort with a three-line change in the partition step.
- ncmncm 6y agoDetails https://news.ycombinator.com/item?id=23237663 https://news.ycombinator.com/item?id=23237663
- a1369209993 6y agohttps://dlang.org/blog/2020/05/14/lomutos-comeback/ https://dlang.org/blog/2020/05/14/lomutos-comeback/ gives a 404 error. And archive.org ( http://web.archive.org/cdx/search/cdx?url=https://dlang.org/blog/2020/05/14/lomutos-comeback/ http://web.archive.org/cdx/search/cdx?url=https://dlang.org/... ) is also getting nothing but 404s, so it's not a problem on my end. I'm not really sure what's wrong with this site, since other commenters seem not to have noticed a problem.
- zombinedev 6y agoIt's ok now, as far as I can see.
- a1369209993 6y agoActually it's it still giving a 404, but (after remembering and looking up the --content-on-error option to wget) it appears TFA is served just fine as if it were a 404 error page.
- kragen 6y agoI used Lomuto's algorithm in my presentation of Quicksort in http://canonical.org/~kragen/sw/dev3/paperalgo#addtoc_21 http://canonical.org/~kragen/sw/dev3/paperalgo#addtoc_21 because my emphasis there is on using the simplest possible algorithms. It didn't occur to me that it might actually be faster, or be capable of being made faster, and indeed in that page I said you could improve efficiency with Hoare partitioning. Alexandrescu's branch-free code in this article is a thing of beauty, in the same sort of rugged way that Stepanov's code is.
- ncmncm 6y agoIf you define inline bool swap_if( bool c, long& a, long& b) { long ta = a, tb = b; a = c ? tb : ta; b = c ? ta : tb; return c; } and then use it in a partition like right += swap_if( *left < pivot, *left, *right); compiled with Clang (which generates `cmov` instructions), the Hoare partition is still faster, and more than twice as fast as `std::sort`. Using `swap_if` in Lumuto is also faster, but not as much faster. I interpret the difference (vs. array ops) as resulting from reduced L1 bus traffic. A fully general swap_if, template <typename T> bool swap_if( bool c, T& a, T& b) { T v[2] = { a, b }; b = v[c], a = v[1-c]; return c; } could and IMHO should be peephole-optimized to use a pair of `cmov` instructions, but is not in Clang, Gcc, Icc, or MSVC. But even without such an optimization, it makes Quicksort much faster. (Gcc, incidentally, is very, very sensitive to details of the second swap_if. Change the order of assigning a and b, or use `!c` in place of `1-c`, and it gets much slower, on Intel, for very non-(to me-)obvious reasons. Gcc also will never, ever produce two `cmov` instructions in a basic block. I have filed a bug.) If `swap_if` were in the Standard Library, it would probably be implemented optimally on all compilers, and almost half of the Standard algorithms could use it to get, often, ~2x performance.