Pattern-defeating quicksort • Hacker News Board

Re: Pattern-defeating quicksort

#41

Post by carussell » Thu, Jun 29, 2017, 11:12 PM UTC

jkabrg wrote: post #17

orlp wrote: post #15

Earlier quoted context omitted.

The overhead of including the fallback to heapsort takes a negligible, non-measurable amount of processing time that guarantees a worst case runtime of O(n log n), and to be more precise, a worst case that is 2 - 4 times as slow as the best case. 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…

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 selectively reheap. Whether this happens is dependent on the state of the heap and your next element, which means the total number of times you reheap will vary with input.

Re: Pattern-defeating quicksort

#42

Post by VHRanger » Fri, Jun 30, 2017, 12:19 AM UTC

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

I have no doubt that PDQSort is faster than the other sorting algorithms, but before I swap std::sort for it in serious commercial apps I'd like some proofs and battle testing.

That said, if it really is an in place swap for std::sort I'll try it out ASAP

Re: Pattern-defeating quicksort

#43

Post by Franciscouzo » Fri, Jun 30, 2017, 3:45 AM UTC

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…

> I long suspected that much of the interest in in-place, O(n ln(n)), stable sorting was due to some unspoken but strong goal of finding some fundamental conservation law of a trade off of processor time and memory space. Well, that didn't really happen. But heap sort is darned clever; I like it.

It did happen, it's called block sort, but it's not used because of the complexity of implementing it, the constants of its runtime, it's not easy to parallelize, and its best case complexity is still O(n ln n).

Re: Pattern-defeating quicksort

#44

Post by gnarbarian » Fri, Jun 30, 2017, 4:45 AM UTC

atilimcetin wrote: post #9

Rust's stable sort is based on timsort ( https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor... ) and unstable sort is based on pattern-defeating quicksort ( https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor... ). The documentation says that 'It [unstable sorting] is generally faster than stable sorting, except in a few special cases, e.g. when the slice consists of several concatenated sorted seq…

I like merge sort. Average time may be worse, but it's upper bound is better and it is conceptually cleaner and easier to understand (IMO).

Re: Pattern-defeating quicksort

#45

Post by badminton1 » Fri, Jun 30, 2017, 4:47 AM UTC

gnarbarian wrote: post #44

atilimcetin wrote: post #9

Rust's stable sort is based on timsort ( https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor... ) and unstable sort is based on pattern-defeating quicksort ( https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor... ). The documentation says that 'It [unstable sorting] is generally faster than stable sorting, except in a few special cases, e.g. when the slice consists of several concatenated sorted seq…

I like merge sort. Average time may be worse, but it's upper bound is better and it is conceptually cleaner and easier to understand (IMO).

Just that it takes extra space and that's sometimes a constraint.

Re: Pattern-defeating quicksort

#46

Post by xenadu02 » Fri, Jun 30, 2017, 4:59 AM UTC

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

It's always good to remember that while Big-O is useful, it isn't the be-all end-all. The canonical example on modern hardware is a linked list. In theory it has many great properties. In reality chasing pointers can be death due to cache misses.

Often a linear search of a "dumb" array can be the fastest way to accomplish something because it is very amenable to pre-fetching (it is obvious to the pre-fetcher what address will be needed next). Even a large array may fit entirely in L2 or L3. For small data structures arrays are almost always a win; in some cases even hashing is slower than a brute-force search of an array!

A good middle ground can be a binary tree with a bit less than an L1's worth of entries in an array stored at each node. The binary tree lets you skip around the array quickly while the CPU can zip through the elements at each node.

It is more important than ever to test your assumptions. Once you've done the Big-O analysis to eliminate exponential algorithms and other basic optimizations you need to analyze the actual on-chip performance, including cache behavior and branch prediction.

Re: Pattern-defeating quicksort

#47

Post by flukus » Fri, Jun 30, 2017, 5:09 AM UTC

xenadu02 wrote: post #46

_hrfd wrote: post #29

Earlier quoted context omitted.

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…

It's always good to remember that while Big-O is useful, it isn't the be-all end-all. The canonical example on modern hardware is a linked list. In theory it has many great properties. In reality chasing pointers can be death due to cache misses. Often a linear search of a "dumb" array can be the fastest way to accomplish something because it is very amenable to pre-fetching (it is obvious to the pre-fetcher what add…

> It's always good to remember that while Big-O is useful, it isn't the be-all end-all. The canonical example on modern hardware is a linked list. In theory it has many great properties. In reality chasing pointers can be death due to cache misses.

My favorite example is adding and ordered list of items into a a simple tree, all you've really done is created a linked list. Big-O doesn't know what your data looks like but you generally should.

Re: Pattern-defeating quicksort

#48

Post by lz400 » Fri, Jun 30, 2017, 6:02 AM UTC

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?

I don't know about improvements but new methods are still being found, like sleep sort

https://www.reddit.com/r/ProgrammerHumor/comments/5vpdw5/sle...

Re: Pattern-defeating quicksort

#49

Post by xoroshiro » Fri, Jun 30, 2017, 6:29 AM UTC

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

Interesting history!

>Sorting is a mostly "solved" problem in theory, but as new hardware emerges different aspects of implementations become more or less important (cache, memory, branch prediction)

This makes me wonder what other hardware tricks might be used for other popular algorithms such as ones used in graphs. I'm sure shortest path is also one of those algorithms that have been "solved" in theory but have a huge amount of research, but personally, what would be more interesting to hear about is something that isn't quite as easy. Something like linear programming with integer constraints or even something like vehicle routing or scheduling. To anyone studying those areas, is there anything you find particularly interesting?

Re: Pattern-defeating quicksort

#50

Post by wiz21c » Fri, Jun 30, 2017, 7:06 AM UTC

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?

There are as many sorting algorithm as their are data distribution. So some algorithm are better suited to some problems. Therefore, each requires specific research.

Moreover, if you study algorithm and if you try to understand/formalize their behaviour, especially theyr memory/speed tradeoffs, then you'll see that they're actually quite complex. See : https://math.stackexchange.com/questions/1313540/a-lower-bou...

Finally, implementing a sort alogirth requires a hell of carefulness. They are super tricky. See for example : http://cs.fit.edu/~pkc/classes/writing/samples/bentley93engi...