5 ms·

Oh my. Comparison sorts are still slower than counting sorts on typical architectures, esp. radix sort. (Coupled with insertion sort of small sizes.) Or bursts

Oh my. Comparison sorts are still slower than counting sorts on typical architectures, esp. radix sort. (Coupled with insertion sort of small sizes.) Or burstsort if the data size is truly huge. As usual, StackOverflow is missing the forest for the trees.

jacobolus 7y ago
I enjoyed Alexandrescu’s CppCon 2019 talk “Speed Is Found In The Minds of People” About optimizing generic sorting routines for modern hardware. https://www.youtube.com/watch?v=FJJTYQYB1JQ https://www.youtube.com/watch?v=FJJTYQYB1JQ
lorenzhs 7y ago
It's not even the fastest comparison-based sorter for the vast majority of inputs. There are much faster sorters out there that exploit the details of modern hardware (branch prediction is a big one, parallelism is also an obvious win if you can make use of it, etc), e.g. https://github.com/SaschaWitt/ips4o/ https://github.com/SaschaWitt/ips4o/ (sequential and parallel, disclaimer: the authors are my colleagues) or https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort (sequential)
- gpderetta 7y ago
  Well, nobody really uses plain quicksort in practice (maybe libc qsort?), but a lot of practical fast sort algorithms are variant (or based on) quicksort (including the ips4o you linked to if I'm reading the paper correctly). A better claim would be that, among the comparison based sorts, algos in the quicksort family tend to be faster in practice.
  - lorenzhs 7y ago
    Yeah, my implicit comparison was to something like std::sort from GNU's libstdc++, which is introsort, a quicksort-insertionsort-hybrid. Plain quicksort is indeed not great. ips4o is a samplesort-derivative (the name stands for Inplace Super-Scalar Sample SOrt), which is kinda quicksort-derived, but doesn't use one pivot, but many (in the case of ips4o, 255, iirc). It's heritage traces back to quicksort, if you will, but it's also very different.
RavlaAlvar 7y ago
Can you elaborate on why bubble sort is fast on huge dataset? Also, If counting based sorting algorithm is faster in practice , why we are not seeing more of it in database system?
- taneq 7y ago
  That was burst sort, not bubble sort. (That said, bubblesort can be fast if the data are usually very close to sorted - one example here is depth-sorting polygons for a rendering engine on a highly constrained platform.)
  - aratakareigen 7y ago
    See also: https://en.m.wikipedia.org/wiki/Adaptive_sort https://en.m.wikipedia.org/wiki/Adaptive_sort Another example application of adaptive sorts is the sweep-and-prune broadphase collision detection algorithm that's somewhat commonly used in physics engines.
- AstralStorm 7y ago
  Database systems do not operate on large strings and sort by keys rather than whole rows. And they tend to use hash maps as input invoking truly flat distributions. They also require sort stability. Burstsort and radix sort are best for cases where you actually sort based on whole or almost whole structure comparison - as in memcmp. Burstsort is also equivalent to walking a trie index in a database. So yes, you see it quite a lot.
heavenlyblue 7y ago
What if all elements are unique?
opencl 7y ago
I remember learning in my college algorithms class that radix sort is 'slow in practice' because it's 'not cache friendly' then when we had a sorting speed competition project the fastest entry was a radix sort.
senderista 7y ago
In principle, you can use radix sort for pretty much any real-world data. All you need is a canonical binary "sort key" representation, and you can implement MSD radix sort on top of that. (For variable-length data like strings, the sort key can be a lazy iterator in case you need to break ties for initially equal sort keys, which of course requires MSD not LSD radix sort.) Composite data types can just concatenate the sort keys of their members, recursively, much like we build hash code implementations. At some point I want to release a sorting library which introduces a new Rust trait for this purpose.

jacobolus 7y ago

I enjoyed Alexandrescu’s CppCon 2019 talk “Speed Is Found In The Minds of People” About optimizing generic sorting routines for modern hardware. https://www.youtube.com/watch?v=FJJTYQYB1JQ https://www.youtube.com/watch?v=FJJTYQYB1JQ

lorenzhs 7y ago

It's not even the fastest comparison-based sorter for the vast majority of inputs. There are much faster sorters out there that exploit the details of modern hardware (branch prediction is a big one, parallelism is also an obvious win if you can make use of it, etc), e.g. https://github.com/SaschaWitt/ips4o/ https://github.com/SaschaWitt/ips4o/ (sequential and parallel, disclaimer: the authors are my colleagues) or https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort (sequential)

gpderetta 7y ago
Well, nobody really uses plain quicksort in practice (maybe libc qsort?), but a lot of practical fast sort algorithms are variant (or based on) quicksort (including the ips4o you linked to if I'm reading the paper correctly). A better claim would be that, among the comparison based sorts, algos in the quicksort family tend to be faster in practice.
- lorenzhs 7y ago
  Yeah, my implicit comparison was to something like std::sort from GNU's libstdc++, which is introsort, a quicksort-insertionsort-hybrid. Plain quicksort is indeed not great. ips4o is a samplesort-derivative (the name stands for Inplace Super-Scalar Sample SOrt), which is kinda quicksort-derived, but doesn't use one pivot, but many (in the case of ips4o, 255, iirc). It's heritage traces back to quicksort, if you will, but it's also very different.

RavlaAlvar 7y ago

Can you elaborate on why bubble sort is fast on huge dataset? Also, If counting based sorting algorithm is faster in practice , why we are not seeing more of it in database system?

taneq 7y ago
That was burst sort, not bubble sort. (That said, bubblesort can be fast if the data are usually very close to sorted - one example here is depth-sorting polygons for a rendering engine on a highly constrained platform.)
- aratakareigen 7y ago
  See also: https://en.m.wikipedia.org/wiki/Adaptive_sort https://en.m.wikipedia.org/wiki/Adaptive_sort Another example application of adaptive sorts is the sweep-and-prune broadphase collision detection algorithm that's somewhat commonly used in physics engines.
AstralStorm 7y ago
Database systems do not operate on large strings and sort by keys rather than whole rows. And they tend to use hash maps as input invoking truly flat distributions. They also require sort stability. Burstsort and radix sort are best for cases where you actually sort based on whole or almost whole structure comparison - as in memcmp. Burstsort is also equivalent to walking a trie index in a database. So yes, you see it quite a lot.

heavenlyblue 7y ago

What if all elements are unique?

opencl 7y ago

I remember learning in my college algorithms class that radix sort is 'slow in practice' because it's 'not cache friendly' then when we had a sorting speed competition project the fastest entry was a radix sort.

senderista 7y ago

In principle, you can use radix sort for pretty much any real-world data. All you need is a canonical binary "sort key" representation, and you can implement MSD radix sort on top of that. (For variable-length data like strings, the sort key can be a lazy iterator in case you need to break ties for initially equal sort keys, which of course requires MSD not LSD radix sort.) Composite data types can just concatenate the sort keys of their members, recursively, much like we build hash code implementations. At some point I want to release a sorting library which introduces a new Rust trait for this purpose.