Has HN ever discussed the possibilities when purposely crafting worst-case input to amplify a denial-of-service attack?
Pattern-defeating quicksort
31–40 of 79 posts
Re: Pattern-defeating quicksort
#32I 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 sort, sure, just extend the sort keys with a sequence number, do the sort, and remove the key extensions.
Quicksort has good main memory locality of reference and a possibility of some use of multiple threads, and heap sort seems to have neither. But there is a version of heap sort modified for doing better on locality of reference when the array being sorted is really large.
But, if are not too concerned about memory space, then don't have to care about the sort routine being in place. In that case, get O(n ln(n)), a stable sort, no problems with locality of reference, and ability to sort huge arrays with just the old merge sort.
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.
Re: Pattern-defeating quicksort
#33Question 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…
Thanks for the alexandrescu paper
Re: Pattern-defeating quicksort
#34Re: Pattern-defeating quicksort
#35I 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…
Hi stjepang,
If the following criteria is met, then perhaps the branch mis-predict penalty is less of a problem: 1. you are sorting a large amount of data, much bigger than the CPU LLC 2. you can effectively utilize all cores, i.e. your sort algorithm can parallelize Perhaps in this case you are memory bandwidth limited. If so, you are probably spending more time waiting on data than waiting on pipe flushes (i.e. consequence of mis-predicts).
Re: Pattern-defeating quicksort
#36Has HN ever discussed the possibilities when purposely crafting worst-case input to amplify a denial-of-service attack?
If whoever you're targeting uses libc++, I already did the analysis: https://bugs.llvm.org/show_bug.cgi?id=20837
To my knowledge it's still not fixed.
Re: Pattern-defeating quicksort
#37Earlier quoted context omitted.
Hey, author of pdqsort here, the draft paper contains complexity proofs of the O(n log n) worst case and O(nk) best case with k distinct keys: https://drive.google.com/open?id=0B1-vl-dPgKm_T0Fxeno1a0lGT0...
Best case? Give worst and average case when describing complexities.
There's not much value in discussing the asymptotic worst-case or average-case performance of sorting algorithms, because just about every algorithm worth talking about is already optimal in that regard.
The interesting performance differences are all about constant factors.
Re: Pattern-defeating quicksort
#38Earlier quoted context omitted.
I already did, you may want to re-read my comment.
Am I misinterpreting your usage of "best case"?
Without enlightening me on what your interpretation is, I have no way of telling.
pdqsort has a worst case of O(n log n). That means, no matter what, the algorithm never takes more than a constant factor times n log n time to complete.
Since pdqsort is strictly a comparison sort, and comparison sorts can do no better than O(n log n) in the average case, pdqsort is asymptotically optimal in the average case (because the average case can never be worse than the worst case).
On top of the above guarantees, if your input contains only k distinct keys, then pdqsort has a worst case complexity of O(nk). So when k gets small (say, 1-5 distinct elements), pdqsort approaches linear time. That is pdqsort's best case.
Re: Pattern-defeating quicksort
#39I 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…
Hi stjepang, If the following criteria is met, then perhaps the branch mis-predict penalty is less of a problem: 1. you are sorting a large amount of data, much bigger than the CPU LLC 2. you can effectively utilize all cores, i.e. your sort algorithm can parallelize Perhaps in this case you are memory bandwidth limited. If so, you are probably spending more time waiting on data than waiting on pipe flushes (i.e. con…
Absolutely - there are cases when branch misprediction is not the bottleneck. It depends on a lot of factors.
Another such case is when sorting strings because every comparison causes a potential cache miss and introduces even more branching, and all that would dwarf that one misprediction.
Re: Pattern-defeating quicksort
#40Question 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?
What makes things tricky is that there are a couple of common cases that can be sorted in O(n), and that more complicated algorithms might have better asmyptotic behaviour, while being worse for small or even moderately large lists.
To make matters worse there are also more specific sorting algorithms like radix sort, which can be even faster in cases where they can be used.