Lomuto's Comeback
dlang.org
Lomuto's Comeback
1–10 of 104 posts
Re: Lomuto's Comeback
#2I 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-Rebo...
Re: Lomuto's Comeback
#3I 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-Rebo...
Anthony Zee's Quantum Field Theory textbook takes a similar tone.
Re: Lomuto's Comeback
#4Writing 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.
Re: Lomuto's Comeback
#5Notice 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...
Re: Lomuto's Comeback
#6Writing 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.
I 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
Re: Lomuto's Comeback
#7I 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-Rebo...
Oh, I assumed that dialogue between Lomuto and Hoare was real -- at least the gist of it, if not the exact words.
Re: Lomuto's Comeback
#8Notice 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 th…
Maybe?
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.
Re: Lomuto's Comeback
#9I’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?
Re: Lomuto's Comeback
#10I’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?
I’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