Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lomuto's Comeback

dlang.org

Post reply on HN
Print view View original

61–70 of 104 posts

Re: Lomuto's Comeback

#61

Post by ncmncm »

cozzyd wrote: post #41
mehrdadn wrote: post #15

Earlier quoted context omitted.

My comment wasn't inherently about sorting either. Branch-free in general is faster in the worst cases, i.e. if the branch is difficult to predict. Except most real-world branches are predictable... that's why we have branch predictors. So in general you should expect branch-free to be slower, unless you have reason to assume your branches are actually close to random.

Branches also can't be vectorized, so going branch free can lead to a substantial speedup if you can use vector instructions (you might be doing twice the work, but your vector instruction may let you do it 4-16 times faster).

Indeed, AVX512 instructions can sort 16 int32 or well-behaved float values optimally, with no branches. It is a good final pass to any other algorithm.

Re: Lomuto's Comeback

#62

Post by derefr »

mehrdadn wrote: post #15
sesuximo wrote: post #11

Earlier quoted context omitted.

Sorting is the case study but not the insight. I think the cool/surprising part of the article is that doing more work can be faster... Even more memory work (which per conventional wisdom is not trivial!)

My comment wasn't inherently about sorting either. Branch-free in general is faster in the worst cases, i.e. if the branch is difficult to predict. Except most real-world branches are predictable... that's why we have branch predictors. So in general you should expect branch-free to be slower, unless you have reason to assume your branches are actually close to random.

> unless you have reason to assume your branches are actually close to random.

I mean, to the degree that you need to sort the data at all, it contains informational entropy.

Many "presents as sorted" data structures trade space for time by keeping track of the internal sortedness of chunks of the data, between sortation passes. Heck, any insert-optimized data structure (B+ trees; LevelDB's sorted-string-tables; N-ary tries generally) will get most of its performance gains by being able to guarantee, at node split time, that the children of any particular node are sorted relative to one-another.

So, in many cases, by the very fact that you don't already have metadata attached to your data asserting that it's sorted, it's highly likely to have no branch-predictability.

(Couple that to the fact that load-balancing in OLTP distributed systems favors writes to evenly-keyspace-distributed partitioning keys, ala Dynamo, and you'll frequently find that your inputs to an index-like data structure can be guaranteed random.)

Re: Lomuto's Comeback

#63

Post by kccqzy »

klyrs wrote: post #55
eloff wrote: post #43

Earlier quoted context omitted.

That'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 co…

Yes, 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 swe…

You might be thinking of this: https://news.ycombinator.com/item?id=22322967

Re: Lomuto's Comeback

#64

Post by klyrs »

kccqzy wrote: post #63
klyrs wrote: post #55

Earlier quoted context omitted.

Yes, 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 swe…

You might be thinking of this: https://news.ycombinator.com/item?id=22322967

Bingo, thanks!

Re: Lomuto's Comeback

#65

Post by cozzyd »

snovv_crash wrote: post #56
cozzyd wrote: post #20

Earlier quoted context omitted.

Yes... 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.

The Eigen Array [1] object is fairly close to this. Combining the 'select' with comparisons, chained operators etc. Eigen vectorized stuff pretty effectively too. 1. https://eigen.tuxfamily.org/dox/group__TutorialArrayClass.ht...

Interesting... I've used Eigen for matrix operations before, I did not know they had such a smart general-purpose array implementation!

Re: Lomuto's Comeback

#66

Post by mehrdadn »

cozzyd wrote: post #41
mehrdadn wrote: post #15

Earlier quoted context omitted.

My comment wasn't inherently about sorting either. Branch-free in general is faster in the worst cases, i.e. if the branch is difficult to predict. Except most real-world branches are predictable... that's why we have branch predictors. So in general you should expect branch-free to be slower, unless you have reason to assume your branches are actually close to random.

Branches also can't be vectorized, so going branch free can lead to a substantial speedup if you can use vector instructions (you might be doing twice the work, but your vector instruction may let you do it 4-16 times faster).

True! Though I have yet to see vectorized sorting in production...

Re: Lomuto's Comeback

#67

Post by phkahler »

ipsofacto wrote: post #60
phkahler wrote: post #52

Earlier quoted context omitted.

2x-3x improvement doesn't seem like much for something that runs in parallel.

The 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

So starting off better on a single, and then scaling well with threads. Nice!

Re: Lomuto's Comeback

#68

Post by andralex »

mehrdadn wrote: post #5

Notice 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…

(Author here.) That is incorrect. The difficult case is and the real benchmark is with unpredictable data. The low-entropy cases will be about as fast with both partitioning schemes.

This is only a smart part of the benchmarks I've run because I wanted to drive one point home within a limited space. I've run many tests on various data types and shapes, and Lomuto does better than Hoare on most. (E.g. its improvement on double is even larger than on integrals.)

Re: Lomuto's Comeback

#69

Post by andralex »

derefr wrote: post #62
mehrdadn wrote: post #15

Earlier quoted context omitted.

My comment wasn't inherently about sorting either. Branch-free in general is faster in the worst cases, i.e. if the branch is difficult to predict. Except most real-world branches are predictable... that's why we have branch predictors. So in general you should expect branch-free to be slower, unless you have reason to assume your branches are actually close to random.

> unless you have reason to assume your branches are actually close to random. I mean, to the degree that you need to sort the data at all, it contains informational entropy. Many "presents as sorted" data structures trade space for time by keeping track of the internal sortedness of chunks of the data, between sortation passes. Heck, any insert-optimized data structure (B+ trees; LevelDB's sorted-string-tables; N-ar…

This. Thanks!
Post reply on HN