Beating Up on Qsort (2019) | Hacker News Reader

Beating Up on Qsort (2019)

travisdowns.github.io

81 pointstjalfi10 comments

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/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

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.

Just for fun, I added pdqsort to the benchmark:

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.

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.

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.

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?

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

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

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

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

Reply on news.ycombinator.com