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

Pattern-defeating quicksort

github.com

Post reply on HN
Print view View original

51–60 of 79 posts

Re: Pattern-defeating quicksort

#51

Post by [deleted] »

carussell wrote: post #41
jkabrg wrote: post #17

Earlier quoted context omitted.

Thanks for your reply. > Your logic also would mean that any sorting function that is publicly facing (which is basically any interface on the internet, like a sorted list of Facebook friends) would need to use heapsort (which is 2-4 times as slow), as otherwise DoS attacks are simply done by constructing worst case inputs. Why is that a wrong conclusion? It might be, I'm not a dev. But if I found myself caring about…

I'm sympathetic because it may not be clear: pdqsort is a hybrid sort; when it encounters apparently pathological input, it switches from a strategy resembling quicksort to heapsort—it doesn't share quicksort's worst case characteristics. Your thesis is wrong: > you might as well use an algorithm that takes the same amount of time every time, which I think means heapsort Heapsort has a variable runtime. It will selec…

[deleted]

Re: Pattern-defeating quicksort

#52

Post by [deleted] »

[deleted] wrote: post #51
carussell wrote: post #41

Earlier quoted context omitted.

I'm sympathetic because it may not be clear: pdqsort is a hybrid sort; when it encounters apparently pathological input, it switches from a strategy resembling quicksort to heapsort—it doesn't share quicksort's worst case characteristics. Your thesis is wrong: > you might as well use an algorithm that takes the same amount of time every time, which I think means heapsort Heapsort has a variable runtime. It will selec…

[deleted]

[deleted]

Re: Pattern-defeating quicksort

#53

Post by sgift »

_hrfd wrote: post #19

I think it's fair to say that pdqsort (pattern-defeating quicksort) is overall the best unstable sort and timsort is overall the best stable sort in 2017, at least if you're implementing one for a standard library. The standard sort algorithm in Rust is timsort[1] (slice::sort), but soon we'll have pdqsort as well[2] (slice::sort_unstable), which shows great benchmark numbers.[3] Actually, I should mention that both…

Thanks for making it clear if a sort is stable or unstable in the function name. One of my longer debug sessions was tracing a porting error from Java to C# where the default sort functions are stable vs unstable.

Re: Pattern-defeating quicksort

#54

Post by torrent-of-ions »

I can see why one might blindly call qsort on already sorted data (when using user input), but why sorted data with one out of place element? Presumably that element has been appended to a sorted array, so you would place it properly in linear time using insertion and not call a sort function at all. Why does such a pattern arise in practice?

Re: Pattern-defeating quicksort

#55

Post by torrent-of-ions »

graycat wrote: post #32

I always wondered if there would be a way to have quicksort run slower than O(n ln(n)). Due to that possibility, when I code up a sort routine, I use heap sort. It is guaranteed O(n ln(n)) worst case and achieves the Gleason bound for sorting by comparing keys which means that on average and worst case, on the number of key comparisons, it is impossible to do better than heap sort's O(n ln(n)) forever. For a stable s…

It's cool to play with a pack of cards and run sorting algorithms on them. To see the worst case of quicksort, use the first element as the pivot and give it an already sorted list. It will take quadratic time to give back the same list.

Re: Pattern-defeating quicksort

#56

Post by lorenzhs »

_hrfd wrote: post #19

I think it's fair to say that pdqsort (pattern-defeating quicksort) is overall the best unstable sort and timsort is overall the best stable sort in 2017, at least if you're implementing one for a standard library. The standard sort algorithm in Rust is timsort[1] (slice::sort), but soon we'll have pdqsort as well[2] (slice::sort_unstable), which shows great benchmark numbers.[3] Actually, I should mention that both…

To illustrate the point about branch misprediction, I implemented quicksort with intentionally skewed pivot selection. You can see the results here: https://github.com/lorenzhs/quicksort-pivot-imbalance

For this demo I'm sorting a permutation of the range 1 to n, so obtaining perfect or arbitrarily skewed pivots is free, which isn't realistic, but that's not the point. My experiments show that quicksort is fastest on my machine when 15% of the elements are on one side and 85% on the other. This is a tradeoff between branch prediction (if it always guesses "right side", it's right 85% of the time) and recursion depth (which grows as the pivot becomes more and more imbalanced).

Of course, skewing the pivot is not what you want to do. You should rather look at sorting algorithms which don't suffer from branch mispredictions (as much), such as pdqsort, super-scalar sample sort [1,2] or block quicksort [3]

[1] excellent paper on a parallel in-place adaptation by some of my colleagues: https://arxiv.org/abs/1705.02257 - code will become available soon

[2] my less sophisticated implementation: https://github.com/lorenzhs/ssssort/, I also have a version using pdqsort as base case sorter, which is faster: https://github.com/lorenzhs/ssssort/blob/pdq/speed.pdf (in that plot, ssssort = super scalar sample sort with pdqsort as base case)

[3] https://arxiv.org/abs/1604.06697, implementation at https://github.com/weissan/BlockQuicksort - pdqsort uses the same technique

Re: Pattern-defeating quicksort

#57

Post by lorenzhs »

_hrfd wrote: post #29
dpcx wrote: post #18

Question as a non low-level developer, and please forgive my ignorance: How is it that we're essentially 50 years in to writing sorting algorithms, and we still find improvements? Shouldn't sorting items be a "solved" problem by now?

Basically all comparison-based sort algorithms we use today stem from two basic algorithms: mergesort (stable sort, from 1945) and quicksort (unstable sort, from 1959). Mergesort was improved by Tim Peters in 2002 and that became timsort. He invented a way to take advantage of pre-sorted intervals in arrays to speed up sorting. It's basically an additional layer over mergesort with a few other low-level tricks to min…

Don't count out sample-sort just yet, it lends itself to parallelisation very well and is blazingly fast. See https://arxiv.org/abs/1705.02257 (to be presented at ESA in September) for an in-place parallel implementation that overcomes the most important downsides of previous sample-sort implementations (linear additional space).

Re: Pattern-defeating quicksort

#58

Post by nightcracker »

torrent-of-ions wrote: post #54

I can see why one might blindly call qsort on already sorted data (when using user input), but why sorted data with one out of place element? Presumably that element has been appended to a sorted array, so you would place it properly in linear time using insertion and not call a sort function at all. Why does such a pattern arise in practice?

You would be surprised how often people just use a (repeatedly) sorted vector in spite of a proper data structure or proper insertion calls. It's a lot simpler to just append and sort again. Or the appending happens somewhere else in the code entirely.

As a real-world example, consider a sprite list in a game engine. Yes, you could keep it properly sorted as you add/remove sprites, but it's a lot simpler to just append/delete sprites throughout the code, and just sort it a single time each frame, even if it only adds a single sprite.

So yes, technically this pattern is not needed if everyone always recognized and used the optimal data structure and algorithm at the right time. But that doesn't happen, and it isn't always the simplest solution for the programmer.

Re: Pattern-defeating quicksort

#59

Post by [deleted] »

carussell wrote: post #41
jkabrg wrote: post #17

Earlier quoted context omitted.

Thanks for your reply. > Your logic also would mean that any sorting function that is publicly facing (which is basically any interface on the internet, like a sorted list of Facebook friends) would need to use heapsort (which is 2-4 times as slow), as otherwise DoS attacks are simply done by constructing worst case inputs. Why is that a wrong conclusion? It might be, I'm not a dev. But if I found myself caring about…

I'm sympathetic because it may not be clear: pdqsort is a hybrid sort; when it encounters apparently pathological input, it switches from a strategy resembling quicksort to heapsort—it doesn't share quicksort's worst case characteristics. Your thesis is wrong: > you might as well use an algorithm that takes the same amount of time every time, which I think means heapsort Heapsort has a variable runtime. It will selec…

[deleted]

Re: Pattern-defeating quicksort

#60

Post by [deleted] »

carussell wrote: post #41
jkabrg wrote: post #17

Earlier quoted context omitted.

Thanks for your reply. > Your logic also would mean that any sorting function that is publicly facing (which is basically any interface on the internet, like a sorted list of Facebook friends) would need to use heapsort (which is 2-4 times as slow), as otherwise DoS attacks are simply done by constructing worst case inputs. Why is that a wrong conclusion? It might be, I'm not a dev. But if I found myself caring about…

I'm sympathetic because it may not be clear: pdqsort is a hybrid sort; when it encounters apparently pathological input, it switches from a strategy resembling quicksort to heapsort—it doesn't share quicksort's worst case characteristics. Your thesis is wrong: > you might as well use an algorithm that takes the same amount of time every time, which I think means heapsort Heapsort has a variable runtime. It will selec…

[deleted]
Post reply on HN