4 ms·
An ignorant question: Why don’t default sort implementations provide multiple approaches under the hood and switch based on collection size?
by Waterluvian 5y ago
An ignorant question:
Why don’t default sort implementations provide multiple approaches under the hood and switch based on collection size?
- abatilo 5y agoThere's at least some precedent for conditional execution in standard libraries. At least, in Python, the default sort is https://en.m.wikipedia.org/wiki/Timsort https://en.m.wikipedia.org/wiki/Timsort
- ot 5y agoThey do, to a degree. Modern implementations generally use hardcoded routines for very small numbers (say, up to 5), then some quadratic sort like insertion sort, then quicksort. The dispatching can happen at all levels of the recursion, so quicksort's leaves are actually optimized sorts for small collections.
- anaphor 5y agoThis is a thing, see https://www.youtube.com/watch?v=FJJTYQYB1JQ https://www.youtube.com/watch?v=FJJTYQYB1JQ (talk by Andrei Alexandrescu at CppCon 2019 about this exact idea)
- jiggawatts 5y agoUpvoted because this is a fantastic talk all by itself, and also highly topical.
- ncmncm 5y agoAs I recall, this was the talk that triggered me to begin the experiments that led to the article.
- Someone 5y agoI expect many do. Recursive ones in particular, switch when things get relatively easy. For example glibc’s qsort switches to insertion sort for small sizes. https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdlib/qsort.c;hb=refs/heads/master https://sourceware.org/git/?p=glibc.git;a=blob_plain;f=stdli...: “Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving insertion sort to order the MAX_THRESH items within each partition. This is a big win, since insertion sort is faster for small, mostly sorted array segments.” The comment on the definition of MAX_THRESH is very funny/something worth crying about. “This particular magic number was chosen to work best on a Sun 4/260.” That was a 16.67MHz machine with 128 megabytes of RAM, tops. If that magic constant has been checked since 1990, maybe, it’s worth updating that comment.
- kragen 5y agoIn a lot of cases, parameters like this have a fairly broad plateau where they provide almost optimal performance, and then drop off sharply when you get too far away. MAX_THRESH is 4, but I'm guessing that you'd get less than a factor of 2 difference in performance for any value from 4 to 32 on modern hardware, and above that you'd start seeing a quadratic slowdown, and maybe you'd see a factor of 2 or 3 slowdown if you set it to 1. If you decide to do the experiment, I'm interested in hearing your results.
- Someone 5y agoI don’t think they archived their benchmarks. Even then, I think that would be a multi-month project, to verify whether the test cases still are representative of real-world usage. A factor of 2 would IMO be worth it, though. Cursory reading https://github.com/freebsd/freebsd-src/blob/de1aa3dab23c06fec962a14da3e7b4755c5880cf/lib/libc/stdlib/qsort.c#L131 https://github.com/freebsd/freebsd-src/blob/de1aa3dab23c06fe..., I get the impression FreeBSD switches over to a ¿bubble sort? (I didn’t look close) at <7 elements. That function also seems newer (it claims to implement https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engineering.pdf https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engi..., which is from 1993)
- kragen 5y agoYou could certainly spend multiple months benchmarking it and trying to figure out what real-world usage looks like, but you could get preliminary results in a few hours. It's mostly a matter of writing a short shell script. I agree that a factor of 2, or even 1.03, would be worthwhile. But the biggest problem facing standard library authors is not frequently performing 1.5× or 2× worse than optimal; it's occasionally performing 10000× worse than optimal, like the story Bentley & McIlroy start out with in that paper about the organ-pipe array. (And that's why the Golang stdlib uses introsort.) BTW, just because someone was optimizing their library parameters on a machine from 01987 (like the Sun-4/260) doesn't necessarily mean they were doing it before 01993. In 01993 I was using a VAX-11/785 from 01984. Hardware lasted longer in those days (it was less common to drop your SPARC on the sidewalk and spiderweb the touchscreen) and its higher cost forced it into longer service. https://books.google.com.ar/books?id=JRgDwCkMX_cC&pg=PP121&lpg=PP121&dq=vax-11/785+list+price&source=bl&ots=i0BUrf9Dxw&sig=ACfU3U1Sx9eAVqZkQ6-N2WQMiykGEVLF5Q&hl=es-419&sa=X&ved=2ahUKEwjd3P74mfDxAhXEHLkGHeIGAE0Q6AEwEHoECAkQAQ#v=onepage&q=vax-11%2F785%20list%20price&f=false https://books.google.com.ar/books?id=JRgDwCkMX_cC&pg=PP121&l... says the VAX-11/785's list price in 01984 was US$200k, equivalent to US$513k in 02021 according to the BLS CPI. Not counting the terminals and printers! (About 2000 kids learned to program on that beast, so it was probably a good expenditure for the school district.) In 01988 Sun listed the Sun-4/260 at a base price of US$40k (http://www.bitsavers.org/pdf/sun/Sun_Price_List_Dec88.pdf http://www.bitsavers.org/pdf/sun/Sun_Price_List_Dec88.pdf) but probably more realistically US$80k if you wanted a disk and some way to back it up. US$80k in 01988 is US$180k in 02021. So you might find yourself running a big machine long after it was obsolete. But surely that sort of penny-pinching was unique to high schools like mine, not serious professionals like those writing FreeBSD's libc, GNU libc, and Bentley's SP&E article, written from the lofty sanctuary of Bell Labs? Well, Bentley's 01993 paper reports benchmark results (from 01992) on a MIPS R3000 (introduced 01988) and a VAX 8550 (introduced 01986). Why didn't he benchmark it on any machine from that decade? Probably he didn't have one. And the glibc folks were mostly volunteers at that point. CSRG was still DoD-funded, but they disbanded in 01995 after 4.4. (I think a bunch of them were at BSDI for a while.) — ⁂ — The FreeBSD code is doing an insertion sort. Insertion sort looks a lot like bubble sort, and it took me a long time to appreciate the difference. One difference that's sometimes relevant for this sort of thing is that, on nearly-sorted data, insertion sort is O(N) and bubble sort is O(N²). But in this case that's not relevant because it's not running a single insertion-sort pass over the whole array after nearly-sorting it via quicksort; it's insertion-sorting each tiny partition. (The sorted part of the partition is the range from a up to pm.) After N iterations of the outer loop of either insertion sort or bubble sort, one end of your array has N sorted items in it. (The bottom of the partition from a to a+n, in this case.) The difference is that insertion sort grows that sorted region by inserting the nearest unsorted element into it, while bubble sort grows it by inserting the smallest unsorted element into it (or largest, if you're sorting toward the top). So bubble sort only makes as much progress per pass as insertion sort, but it does a bunch of unnecessary extra work to do it (basically, the same work selection sort does); when sorting M randomly ordered items, insertion sort does on average ¼M† comparisons and swaps on each of the M passes, while bubble sort does ½M comparisons (and still ¼M swaps). Never use bubble sort. ______ † Actually the number is something like ¼√(M² - M), I think. I'd have to go calculate it to be exact.
- amelius 5y agoHopefully not just collection size, but also based on storage medium. You might want to sort stuff which is stored on disk or tape. Why should a standard library only offer solutions for objects stored in memory?
- Waterluvian 5y agoThat seems like something you’d want the developer to handle. Not interested in leaking hardware details into the sort interface.
- amelius 5y agoYou want the sort interface to have call-backs for loading/writing stuff from/to disk. But most sort interfaces don't have this. They only support memory.
- ralfd 5y agoOld, but gold: https://ridiculousfish.com/blog/posts/array.html https://ridiculousfish.com/blog/posts/array.html
- gumby 5y agoThis is quite good, and includes source code.