8 ms·

A Killer Adversary for Quicksort (1999) [pdf]

52 points by beagle3 11y ago

nightcracker 11y ago
I used this technique to prove libc++'s implementation of std::sort is O(n^2). There's still an open bug report for this in libc++: https://llvm.org/bugs/show_bug.cgi?id=20837 https://llvm.org/bugs/show_bug.cgi?id=20837. On a related note, I'm talking to the libc++ and libstdc++ developers about replacing introsort with pdqsort (https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort) as the implementation for std::sort. It solves the worst case in a subtly different (and potentially more efficient) way than introsort. Although that's not the real selling point. EDIT: I forgot I still use my old username on hacker news. To prevent confusion, I'm also the author of pdqsort.
lshevtsov 11y ago
I made an implementation of this algorithm as a university assignment; here's a vanilla implementation of Quicksort https://github.com/leonid-shevtsov/uni-programming/blob/master/kr_may_2012/custom_qsort.cpp#L27 https://github.com/leonid-shevtsov/uni-programming/blob/mast... and here's the function to generate data that causes the custom implementation to go O(n^2) https://github.com/leonid-shevtsov/uni-programming/blob/master/kr_may_2012/generators.cpp#L78 https://github.com/leonid-shevtsov/uni-programming/blob/mast...
graycat 11y ago
What's the problem? From D. Knuth's The Art of Computer Programming: Sorting and Searching, (1) if sorting n records by comparing pairs of keys, then the Gleason bound shows that on average can't sort faster than O( n ln(n) ). (2) Heap sort sorts n records in both worst case and average case in time O( n ln(n) ). Net, when sorting by comparing pairs of keys, in main memory, on a simple machine architecture, with a single processor, ..., can't improve on Heap sort. So, just use Heap sort. That's what I do.
- nightcracker 11y ago
  Big O hides all constants. A hybrid algorithm using Quicksort for the heavy lifting is O(n log n) in the worst case, but is a significant amount faster than heapsort - mainly due to cache effects. See pdqsort for examples (benchmarks included): https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort. It shows that on average it's twice as fast on the random input distribution.
  - graycat 11y ago
    Now and long the usual criterion of performance is big-O notation, and that is what I considered, with the Gleason bound and heap sort and, thus, showed that, with various common assumptions, can't do better than heap sort. As far as I know, I was correct. So, to claim to beat heap sort, have to set aside some of the usual assumptions and the big-O criterion. Quicksort is great with a cache since as it has great locality of reference when working with the partitions that fit into the cache. But, worst case of Quicksort is still O( n^2 ) so what happens if Quicksort encounters such a partition? Just intuitively, it appears that heap sort has a tough time making much exploitation of usual cache designs. We know that. There is a modification of heap sort that helps it work better when have to do virtual memory paging. I used to get torqued at considering big-O, and did this just because it ignores constants; as a programmer, I worked hard to do well with such constants. But in the end I gave in and gave up and just accepted big-O notation as the most appropriate, simple, single criterion. And, for judging algorithms by how they do with cache exploitation, I gave up on that, also: Or, broadly it's the responsibility of such speedup techniques to work on ordinary code written for a simple processor architecture, not the responsibility of such code to do tricky things to exploit tricky architectures. In the land of big-O, a factor of only 2 is considered not very exciting. If relax some of the assumptions, then can beat heap sort and O( n ln(n) ): Use radix sort. That was the sorting algorithm of the old punch card sorting machines. E.g., if have 100 billion records to sort where each key is an alpha-numeric string 10 characters long, then radix sort does all the work in just 10 passes of the 100 billion records. Or for keys m characters long, can sort n records in O( nm ). So that's faster when m < ln(n). Or, to make the arithmetic easier, m < log(n). But log(100 billion) = 12, so radix sort should be faster with m = 10 and n = 100 billion. So, for a hybrid sort routine, consider also radix sort. Am I excited about radix sort? Nope!
- crpatino 11y ago
  In theory, there's no significant differences between theory and practice. In practice, things are never so simple. When you use Big-Oh notation, O(f(n)), you claim that there exist one function F(n) that accurately characterizes the running time of an algorithm based on the size of the input, and that f(n) is the higher order component of that function. I looks something like this: F(n) = A*f(n) + B*g(n) + C*h(n) + ... + K where A,B,C,..K are constants and f,g,h,... are functions. You approximate F(n) ~= Af(n) because for n big enough, this component will dominate the growth of such function. But A is different for different algorithms... so, in the case of sorting, you have several options - quicksort, mergesort, heapsort - that are in paper all "the same" but each has a different constant, and there are real advantages of using the one with the smallest constant. Furthermore, if you are not trying to sort infinitely big data (most real world cases) you must consider that other components of the actual F(n) function, such as g and h, may dominate the performance of the algorithm in the range of data sizes that you are more likely to encounter. There are other measures of algorithmic complexity that deal with this (I recall there is one Small-Oh notation, among others), but they don't teach you that at school unless you are a posgraduate student doing highly relevant work in complexity theory. I suspect most guys, like myself, find out by not taking Knuth as holy gospel and reading further material. And then there are the degenerate cases, where your data can get sorted in quasi-linear time if you apply one of the slow dumb O(n^2) dinosaurs.
jmount 11y ago
I've had bad commercial Quicksort implementations go N^2 on constant data, http://www.win-vector.com/blog/2008/04/sorting-in-anger/ http://www.win-vector.com/blog/2008/04/sorting-in-anger/ . Kind of sours one on the "Quicksort is essentially elegant" idea.
ilzmastr 11y ago
I don't get how you could create an adversarial input in advance for an implementation that uses a randomized-partition (index of pivot drawn from a uniform distribution). Can anyone fill me in? What this article describes (for that, as far as I can tell) is an adversary that modifies the input while quick sort is working. How realistic is that?
- asdfasdfsd 11y ago
  That algorithm is only used to create an input pattern. When it is fed back to the same sorting function, it will cause it to go quadratic. If your target is using the same sorting function it will do the same on their side. This attack is realistic. I have tried it on the glibc qsort, generic quicksort, and Visual Studio qsort, and they were vulnerable.
  - ilzmastr 11y ago
    I'm interested in the way you use the word "attack." I was looking at it from the perspective of you could never run into an input that would consistently sort in O(n^2) using randomized-quicksort. But your perspective (maybe this article's perspective) is that some malicious adversary could force the sorter to do extra work by knowing in advance the steps that they will take. Am I getting that right? Like from a flops security stand point? If so, why care about this situation? This only seems like a realistic scenario in very weird domains, like amazon web services messing with everyone's calls to some standard sorting code to charge them more cents for compute time or something...
    - alejohausner 11y ago
      If I'm not mistaken, the attack is aimed at a quicksort implementation where the pivot value is chosen as a median of first, middle, and last values. It would not work on randomized quicksort, of course.
    - asdfasdfsd 11y ago
      Take a look at Denial-of-service attack.

52 points by beagle3 11y ago

I used this technique to prove libc++'s implementation of std::sort is O(n^2). There's still an open bug report for this in libc++: https://llvm.org/bugs/show_bug.cgi?id=20837 https://llvm.org/bugs/show_bug.cgi?id=20837. On a related note, I'm talking to the libc++ and libstdc++ developers about replacing introsort with pdqsort (https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort) as the implementation for std::sort. It solves the worst case in a subtly different (and potentially more efficient) way than introsort. Although that's not the real selling point. EDIT: I forgot I still use my old username on hacker news. To prevent confusion, I'm also the author of pdqsort.

lshevtsov 11y ago

I made an implementation of this algorithm as a university assignment; here's a vanilla implementation of Quicksort https://github.com/leonid-shevtsov/uni-programming/blob/master/kr_may_2012/custom_qsort.cpp#L27 https://github.com/leonid-shevtsov/uni-programming/blob/mast... and here's the function to generate data that causes the custom implementation to go O(n^2) https://github.com/leonid-shevtsov/uni-programming/blob/master/kr_may_2012/generators.cpp#L78 https://github.com/leonid-shevtsov/uni-programming/blob/mast...

graycat 11y ago

What's the problem? From D. Knuth's The Art of Computer Programming: Sorting and Searching, (1) if sorting n records by comparing pairs of keys, then the Gleason bound shows that on average can't sort faster than O( n ln(n) ). (2) Heap sort sorts n records in both worst case and average case in time O( n ln(n) ). Net, when sorting by comparing pairs of keys, in main memory, on a simple machine architecture, with a single processor, ..., can't improve on Heap sort. So, just use Heap sort. That's what I do.

nightcracker 11y ago
Big O hides all constants. A hybrid algorithm using Quicksort for the heavy lifting is O(n log n) in the worst case, but is a significant amount faster than heapsort - mainly due to cache effects. See pdqsort for examples (benchmarks included): https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort. It shows that on average it's twice as fast on the random input distribution.
- graycat 11y ago
  Now and long the usual criterion of performance is big-O notation, and that is what I considered, with the Gleason bound and heap sort and, thus, showed that, with various common assumptions, can't do better than heap sort. As far as I know, I was correct. So, to claim to beat heap sort, have to set aside some of the usual assumptions and the big-O criterion. Quicksort is great with a cache since as it has great locality of reference when working with the partitions that fit into the cache. But, worst case of Quicksort is still O( n^2 ) so what happens if Quicksort encounters such a partition? Just intuitively, it appears that heap sort has a tough time making much exploitation of usual cache designs. We know that. There is a modification of heap sort that helps it work better when have to do virtual memory paging. I used to get torqued at considering big-O, and did this just because it ignores constants; as a programmer, I worked hard to do well with such constants. But in the end I gave in and gave up and just accepted big-O notation as the most appropriate, simple, single criterion. And, for judging algorithms by how they do with cache exploitation, I gave up on that, also: Or, broadly it's the responsibility of such speedup techniques to work on ordinary code written for a simple processor architecture, not the responsibility of such code to do tricky things to exploit tricky architectures. In the land of big-O, a factor of only 2 is considered not very exciting. If relax some of the assumptions, then can beat heap sort and O( n ln(n) ): Use radix sort. That was the sorting algorithm of the old punch card sorting machines. E.g., if have 100 billion records to sort where each key is an alpha-numeric string 10 characters long, then radix sort does all the work in just 10 passes of the 100 billion records. Or for keys m characters long, can sort n records in O( nm ). So that's faster when m < ln(n). Or, to make the arithmetic easier, m < log(n). But log(100 billion) = 12, so radix sort should be faster with m = 10 and n = 100 billion. So, for a hybrid sort routine, consider also radix sort. Am I excited about radix sort? Nope!
crpatino 11y ago
In theory, there's no significant differences between theory and practice. In practice, things are never so simple. When you use Big-Oh notation, O(f(n)), you claim that there exist one function F(n) that accurately characterizes the running time of an algorithm based on the size of the input, and that f(n) is the higher order component of that function. I looks something like this: F(n) = A*f(n) + B*g(n) + C*h(n) + ... + K where A,B,C,..K are constants and f,g,h,... are functions. You approximate F(n) ~= Af(n) because for n big enough, this component will dominate the growth of such function. But A is different for different algorithms... so, in the case of sorting, you have several options - quicksort, mergesort, heapsort - that are in paper all "the same" but each has a different constant, and there are real advantages of using the one with the smallest constant. Furthermore, if you are not trying to sort infinitely big data (most real world cases) you must consider that other components of the actual F(n) function, such as g and h, may dominate the performance of the algorithm in the range of data sizes that you are more likely to encounter. There are other measures of algorithmic complexity that deal with this (I recall there is one Small-Oh notation, among others), but they don't teach you that at school unless you are a posgraduate student doing highly relevant work in complexity theory. I suspect most guys, like myself, find out by not taking Knuth as holy gospel and reading further material. And then there are the degenerate cases, where your data can get sorted in quasi-linear time if you apply one of the slow dumb O(n^2) dinosaurs.

jmount 11y ago

I've had bad commercial Quicksort implementations go N^2 on constant data, http://www.win-vector.com/blog/2008/04/sorting-in-anger/ http://www.win-vector.com/blog/2008/04/sorting-in-anger/ . Kind of sours one on the "Quicksort is essentially elegant" idea.

ilzmastr 11y ago

I don't get how you could create an adversarial input in advance for an implementation that uses a randomized-partition (index of pivot drawn from a uniform distribution). Can anyone fill me in? What this article describes (for that, as far as I can tell) is an adversary that modifies the input while quick sort is working. How realistic is that?

asdfasdfsd 11y ago
That algorithm is only used to create an input pattern. When it is fed back to the same sorting function, it will cause it to go quadratic. If your target is using the same sorting function it will do the same on their side. This attack is realistic. I have tried it on the glibc qsort, generic quicksort, and Visual Studio qsort, and they were vulnerable.
- ilzmastr 11y ago
  I'm interested in the way you use the word "attack." I was looking at it from the perspective of you could never run into an input that would consistently sort in O(n^2) using randomized-quicksort. But your perspective (maybe this article's perspective) is that some malicious adversary could force the sorter to do extra work by knowing in advance the steps that they will take. Am I getting that right? Like from a flops security stand point? If so, why care about this situation? This only seems like a realistic scenario in very weird domains, like amazon web services messing with everyone's calls to some standard sorting code to charge them more cents for compute time or something...
  - alejohausner 11y ago
    If I'm not mistaken, the attack is aimed at a quicksort implementation where the pivot value is chosen as a median of first, middle, and last values. It would not work on randomized quicksort, of course.
  - asdfasdfsd 11y ago
    Take a look at Denial-of-service attack.