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

41–50 of 104 posts

Re: Lomuto's Comeback

#41

Post by cozzyd »

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.

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

Re: Lomuto's Comeback

#42

Post by kleiba »

bachmeier wrote: post #30
kleiba wrote: post #25

To 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/44...

Off topic: Is it common practice for a dissertation at a German university to be written in English?

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

Re: Lomuto's Comeback

#43

Post by eloff »

kccqzy wrote: post #35
eloff wrote: post #14

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

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

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 compression ratio.

The question is, is there such a dependency in this algorithm? I didn't check.

Re: Lomuto's Comeback

#45

Post by Ericson2314 »

I'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.

Re: Lomuto's Comeback

#46

Post by goldenkey »

ipsofacto wrote: post #31

There'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://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]

You might want to mention if are affiliated with the algorithm you are promoting. ipsofacto ~ ips4o

Re: Lomuto's Comeback

#47

Post by ComputerGuru »

goldenkey wrote: post #46
ipsofacto wrote: post #31

There'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://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]

You might want to mention if are affiliated with the algorithm you are promoting. ipsofacto ~ ips4o

Or maybe the throwaway was named after the comment it was intended to be used to post.

Re: Lomuto's Comeback

#48

Post by ipsofacto »

ComputerGuru wrote: post #47
goldenkey wrote: post #46

Earlier quoted context omitted.

You might want to mention if are affiliated with the algorithm you are promoting. ipsofacto ~ ips4o

Or maybe the throwaway was named after the comment it was intended to be used to post.

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

Re: Lomuto's Comeback

#49

Post by ComputerGuru »

Ericson2314 wrote: post #45

I'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.

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

(Spoiler: it depends on the nature of your data, but sorted vector can be dramatically faster.)

Re: Lomuto's Comeback

#50

Post by atq2119 »

kleiba wrote: post #39
DaiPlusPlus wrote: post #38

Earlier quoted context omitted.

Yes - to ensure the widest possible audience. English is the lingua-franca of academia and has been for almost a century now.

At least in MINT fields, probably less so in the humanities. Correct me if I'm wrong.

You're right. German economics is famously insular, for example. Part of that is cultural, part of it is that they don't write as much in English.
Post reply on HN