5 ms·

Beating Up on Qsort (2019)

81 points by tjalfi 6y ago

lostmsu 6y ago
TL;DR; libc qsort is bad because comparison is not inlined. C++ one is fine. They beat it with optimized radix sort.
SloopJon 6y ago
Just for fun, I added pdqsort to the benchmark: https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort Here are some of the results on an Ivy Bridge hackintosh: size, qsort, inline, sort, stable, pdqsort, radix7 1000, 88.0, 60.6, 31.2, 37.5, 24.6, 12.8 10000, 109.3, 77.1, 45.6, 51.6, 29.1, 12.0 100000, 137.1, 97.7, 57.7, 71.9, 33.3, 12.5 1000000, 159.6, 114.2, 70.6, 88.6, 39.7, 20.4 10000000, 185.2, 133.7, 82.0, 99.7, 43.6, 19.4 Edit: it's not quite as easy to plug radix7 into pdqsort's more varied benchmark program, which expects a template function with a type parameter of int.
- BeeOnRope 6y ago
  Thanks for this! I have a follow-on article to this one with some better radix sort approaches, but I never finished it and it remains unpublished. That one did compare the performance with some other non-standard library sorts, and I'll add prqsort to the list. Admittedly, the benchmark I am using is very simple. In general, radix sort is sensitive to very different characteristics of the input than almost any comparison based sort. E.g., LSD radix sorts (at least like the ones presented here) care about the full range of the input, or how many bits are non-zero in any key (or some similar thing) since the number of passes is related to the number of relevant bits. Similarly, certain patterns that are good for quicksort or merge sort are terrible for radix sort and vice versa. So it's hard to crown an overall winner: it is input dependent.
ganafagol 6y ago
This article is a great lesson to everybody claiming that these binary tree type interview questions are pointless and college classes equally so and we should just focus interviewing/teaching on how to do plumbing in $framework_of_the_day and how to use react and docker. The exact opposite is the case.
- lmm 6y ago
  Where's the evidence that anything useful came out of all the effort in the article, much less that it was a better use of time than some alternative?
- usrnm 6y ago
  Well, algorithm-wise there's absolutely nothing interesting in this article. Every entry-level algorithm class tells you that radix sort is theoretically better for fixed-size integers, all the author did was copy-pasting the implementation from wikipedia and then optimizing the bottlenecks. I'm not saying it dismissively, I enjoyed the article a lot and think the author did a great job, it just isn't the kind of skill you get from knowing cool algorithms and acing whiteboard interviews
ketanhwr 6y ago
Andrei has a pretty amazing CppCon talk similar to this: https://youtu.be/FJJTYQYB1JQ https://youtu.be/FJJTYQYB1JQ
ludocode 6y ago
This article doesn't really make it clear but the merge sort discussion is specifically about glibc's implementation of qsort(). glibc's qsort() and Wine's qsort() are the only ones I know of that use merge sort to implement qsort(). Most implementations use quick sort. I recently did my own benchmarking on various qsort()s since I was trying to implement a faster one. The various BSDs and macOS qsort() are all faster than glibc at sorting integers and they don't allocate memory: https://github.com/ludocode/pottery/tree/master/examples/pottery/qsort https://github.com/ludocode/pottery/tree/master/examples/pot... Of course sorting is much faster if you can inline the comparator so a templated sort algorithm is always going to be faster than a function that takes a function pointer. But this does not require C++; it can be done in plain C. The templated intro_sort from Pottery (linked above) is competitive with std::sort, as are the excellent swensort/sort templates: https://github.com/swenson/sort https://github.com/swenson/sort
- BeeOnRope 6y ago
  Yes, you don't need C++ to get an inlined comparator, but C++ certainly makes it easier in the sense that you can get basically guaranteed inlining [1]. In the C case, your options are fewer, and often more reliant on optimization and the vagaries of the compiler. In particular, I tried to modify glibc's qsort to force inlining of the comparator, using both flatten and always_inline attributes, but failed probably because of the recursive nature of merge sort: the main sorting function is recursive, meaning it cannot be flattened without limit, which ends up inhibiting inlining of the comparator as well. It can definitely be made to work, but it's less automatic than C++ and compatators passed as template arguments. Of course, the "specialize everything" approach of C++ has plenty of downsides too! --- [1] Really, what you get is guaranteed specialization, and then inlining follows easily from that, if the compiler decides it is profitable to inline the small comparator into the sort function.
ehvatum 6y ago
I’m very glad I read through this. Somehow, I didn’t know about __builtin_prefetch or the msvc equivalent, _m_prefetch. Thank you!

81 points by tjalfi 6y ago

TL;DR; libc qsort is bad because comparison is not inlined. C++ one is fine. They beat it with optimized radix sort.

Just for fun, I added pdqsort to the benchmark: https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort Here are some of the results on an Ivy Bridge hackintosh: size, qsort, inline, sort, stable, pdqsort, radix7 1000, 88.0, 60.6, 31.2, 37.5, 24.6, 12.8 10000, 109.3, 77.1, 45.6, 51.6, 29.1, 12.0 100000, 137.1, 97.7, 57.7, 71.9, 33.3, 12.5 1000000, 159.6, 114.2, 70.6, 88.6, 39.7, 20.4 10000000, 185.2, 133.7, 82.0, 99.7, 43.6, 19.4 Edit: it's not quite as easy to plug radix7 into pdqsort's more varied benchmark program, which expects a template function with a type parameter of int.

BeeOnRope 6y ago
Thanks for this! I have a follow-on article to this one with some better radix sort approaches, but I never finished it and it remains unpublished. That one did compare the performance with some other non-standard library sorts, and I'll add prqsort to the list. Admittedly, the benchmark I am using is very simple. In general, radix sort is sensitive to very different characteristics of the input than almost any comparison based sort. E.g., LSD radix sorts (at least like the ones presented here) care about the full range of the input, or how many bits are non-zero in any key (or some similar thing) since the number of passes is related to the number of relevant bits. Similarly, certain patterns that are good for quicksort or merge sort are terrible for radix sort and vice versa. So it's hard to crown an overall winner: it is input dependent.

ganafagol 6y ago

This article is a great lesson to everybody claiming that these binary tree type interview questions are pointless and college classes equally so and we should just focus interviewing/teaching on how to do plumbing in $framework_of_the_day and how to use react and docker. The exact opposite is the case.

lmm 6y ago
Where's the evidence that anything useful came out of all the effort in the article, much less that it was a better use of time than some alternative?
usrnm 6y ago
Well, algorithm-wise there's absolutely nothing interesting in this article. Every entry-level algorithm class tells you that radix sort is theoretically better for fixed-size integers, all the author did was copy-pasting the implementation from wikipedia and then optimizing the bottlenecks. I'm not saying it dismissively, I enjoyed the article a lot and think the author did a great job, it just isn't the kind of skill you get from knowing cool algorithms and acing whiteboard interviews

ketanhwr 6y ago

Andrei has a pretty amazing CppCon talk similar to this: https://youtu.be/FJJTYQYB1JQ https://youtu.be/FJJTYQYB1JQ

ludocode 6y ago

This article doesn't really make it clear but the merge sort discussion is specifically about glibc's implementation of qsort(). glibc's qsort() and Wine's qsort() are the only ones I know of that use merge sort to implement qsort(). Most implementations use quick sort. I recently did my own benchmarking on various qsort()s since I was trying to implement a faster one. The various BSDs and macOS qsort() are all faster than glibc at sorting integers and they don't allocate memory: https://github.com/ludocode/pottery/tree/master/examples/pottery/qsort https://github.com/ludocode/pottery/tree/master/examples/pot... Of course sorting is much faster if you can inline the comparator so a templated sort algorithm is always going to be faster than a function that takes a function pointer. But this does not require C++; it can be done in plain C. The templated intro_sort from Pottery (linked above) is competitive with std::sort, as are the excellent swensort/sort templates: https://github.com/swenson/sort https://github.com/swenson/sort

BeeOnRope 6y ago
Yes, you don't need C++ to get an inlined comparator, but C++ certainly makes it easier in the sense that you can get basically guaranteed inlining [1]. In the C case, your options are fewer, and often more reliant on optimization and the vagaries of the compiler. In particular, I tried to modify glibc's qsort to force inlining of the comparator, using both flatten and always_inline attributes, but failed probably because of the recursive nature of merge sort: the main sorting function is recursive, meaning it cannot be flattened without limit, which ends up inhibiting inlining of the comparator as well. It can definitely be made to work, but it's less automatic than C++ and compatators passed as template arguments. Of course, the "specialize everything" approach of C++ has plenty of downsides too! --- [1] Really, what you get is guaranteed specialization, and then inlining follows easily from that, if the compiler decides it is profitable to inline the small comparator into the sort function.

ehvatum 6y ago

I’m very glad I read through this. Somehow, I didn’t know about __builtin_prefetch or the msvc equivalent, _m_prefetch. Thank you!