6 ms·

This article is missing the important reference to the prior work by Edelkamp and Weiss, on branchless quicksort [1]. I've long since implemented that in pdqso

This article is missing the important reference to the prior work by Edelkamp and Weiss, on branchless quicksort [1]. I've long since implemented that in pdqsort [2], along with other techniques described by me in [3] which is a drop-in replacement for std::sort that's ~twice as fast as std::sort for small data with branchless comparisons. It's also available in Boost.sort [4]. [1] https://arxiv.org/abs/1604.06697 https://arxiv.org/abs/1604.06697 [2] https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort [3] https://arxiv.org/abs/2106.05123 https://arxiv.org/abs/2106.05123 [4] https://www.boost.org/doc/libs/1_76_0/libs/sort/doc/html/sort/single_thread.html https://www.boost.org/doc/libs/1_76_0/libs/sort/doc/html/sor...

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 ago
  There'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 ago
  They 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 ago
  This 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 ago
    Upvoted because this is a fantastic talk all by itself, and also highly topical.
    - ncmncm 5y ago
      As I recall, this was the talk that triggered me to begin the experiments that led to the article.
- Someone 5y ago
  I 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 ago
    In 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 ago
      I 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)
      - 5y ago
- amelius 5y ago
  Hopefully 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 ago
    That seems like something you’d want the developer to handle. Not interested in leaking hardware details into the sort interface.
    - amelius 5y ago
      You 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 ago
  Old, but gold: https://ridiculousfish.com/blog/posts/array.html https://ridiculousfish.com/blog/posts/array.html
  - gumby 5y ago
    This is quite good, and includes source code.
ncmncm 5y ago
> This article is missing the important reference I don't understand why you would complain it is missing reference to Edelkamp and Weiss when its second and third references are to papers by Edelkamp and Weiss. My [3] is identically the paper labeled [1] in the complaint.
- nightcracker 5y ago
  Ah, I'm sorry. I looked over it because I didn't see it mentioned in the text. You did technically link to it as "active literature on sorting" without further details, but then the article goes on to describe exactly their idea without mentioning that it is in fact their idea. There really ought to be a contextual reference that gives proper credit.

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 ago
There'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 ago
They 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 ago
This 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 ago
  Upvoted because this is a fantastic talk all by itself, and also highly topical.
  - ncmncm 5y ago
    As I recall, this was the talk that triggered me to begin the experiments that led to the article.
Someone 5y ago
I 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 ago
  In 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 ago
    I 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)
    - 5y ago
amelius 5y ago
Hopefully 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 ago
  That seems like something you’d want the developer to handle. Not interested in leaking hardware details into the sort interface.
  - amelius 5y ago
    You 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 ago
Old, but gold: https://ridiculousfish.com/blog/posts/array.html https://ridiculousfish.com/blog/posts/array.html
- gumby 5y ago
  This is quite good, and includes source code.

ncmncm 5y ago

> This article is missing the important reference I don't understand why you would complain it is missing reference to Edelkamp and Weiss when its second and third references are to papers by Edelkamp and Weiss. My [3] is identically the paper labeled [1] in the complaint.

nightcracker 5y ago
Ah, I'm sorry. I looked over it because I didn't see it mentioned in the text. You did technically link to it as "active literature on sorting" without further details, but then the article goes on to describe exactly their idea without mentioning that it is in fact their idea. There really ought to be a contextual reference that gives proper credit.