Lomuto's Comeback • Hacker News Board

Re: Lomuto's Comeback

#31

Post by ipsofacto » Sun, May 17, 2020, 6:09 PM UTC

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]

Re: Lomuto's Comeback

#32

Post by gumby » Sun, May 17, 2020, 6:10 PM UTC

zengid wrote: post #2

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

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

Re: Lomuto's Comeback

#33

Post by eqvinox » Sun, May 17, 2020, 6:14 PM UTC

So 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?)

Re: Lomuto's Comeback

#34

Post by kccqzy » Sun, May 17, 2020, 6:19 PM UTC

TeMPOraL wrote: post #23

repsilat wrote: post #8

Earlier quoted context omitted.

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

I 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?

Extracting percentile information doesn't require sorting. Even if you're too lazy to implement anything custom, a few invocations of std::nth_element will likely outperform sorting: https://en.cppreference.com/w/cpp/algorithm/nth_element

Re: Lomuto's Comeback

#35

Post by kccqzy » Sun, May 17, 2020, 6:27 PM UTC

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.

Re: Lomuto's Comeback

#36

Post by turndown » Sun, May 17, 2020, 6:35 PM UTC

zengid wrote: post #2

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

If you enjoy books like that, I recommend The Cambridge Quintet[0]; it's a wonderful book.

0. https://www.amazon.com/Cambridge-Quintet-Scientific-Speculat...

Re: Lomuto's Comeback

#37

Post by cozzyd » Sun, May 17, 2020, 6:51 PM UTC

TeMPOraL wrote: post #23

repsilat wrote: post #8

Earlier quoted context omitted.

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

I 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?

Yeah, you can histogram the values if you just need an approximate answer (or if you have few enough discrete values, you can just have a bin per value). Once you have an approximate answer, if you need a more precise answer, you can go through the data again and only consider values within the right bin (which hopefully will be a lot fewer, if you've chosen your bins wisely) and then use something like std::nth_element.

Re: Lomuto's Comeback

#38

Post by DaiPlusPlus » Sun, May 17, 2020, 6:52 PM UTC

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?

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

Re: Lomuto's Comeback

#39

Post by kleiba » Sun, May 17, 2020, 6:54 PM UTC

DaiPlusPlus wrote: post #38

bachmeier wrote: post #30

Earlier quoted context omitted.

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

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.

Re: Lomuto's Comeback

#40

Post by kkaefer » Sun, May 17, 2020, 6:54 PM UTC

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?

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