4 ms·

Surprised that musl I'd the slowest. Anyone have any insight into why qsort was coded like this?

by mangix 10y ago

tyingq 10y ago
Apparently, to optimize for low memory usage (from reading the comments in the commit) http://git.musl-libc.org/cgit/musl/commit/?id=22263709eda9f7d692a0f484fd759f757418dbd7 http://git.musl-libc.org/cgit/musl/commit/?id=22263709eda9f7...
- pavanky 10y ago
  Doesn't quicksort have the least memory usage ?
  - DSMan195276 10y ago
    Quicksort still requires O(lg n) memory because of its recursive nature. Since (lg n) is generally small, it's not that big of a deal. But with bad data, it's possible for Quicksort to degenerate to O(n) extra memory, which could be an issue (Especially for machines with little stack space). Heapsort (And thus smoothsort) are not recursive, so they require a constant amount of memory for all inputs.
    - eutectic 10y ago
      What if you always recurse into the smaller half, and use tail-recursion/looping to process the rest? Doesn't that keep the space usage bounded to O(log(n))?
      - deathanatos 10y ago
        This is correct, and is noted in the Wikipedia article's discussion of memory usage[1]. (Which I was only reading because I was erroneously thinking that quicksort was O(1) memory – I was completely forgetting stack space.) [1]: https://en.wikipedia.org/wiki/Quicksort#Space_complexity https://en.wikipedia.org/wiki/Quicksort#Space_complexity
pavanky 10y ago
The original post links to this page: http://calmerthanyouare.org/2013/05/31/qsort-shootout.html http://calmerthanyouare.org/2013/05/31/qsort-shootout.html There is an explanation provided that may be the reason, but it is not entirely convincing. Smoothsort is a variation of heapsort that performs especially well on nearly sorted inputs. It’s a pretty complicated beast and it does take some effort to wrap one’s head around it. Keith Schwarz has posted a nice walkthrough that the interested reader should check out. Considering that musl libc puts simplicity among its design goals, the choice of smoothsort could seem odd. The code is however clean and readable and getting an O(nlogn)O(nlog⁡n) worst case with near linear complexity for nearly sorted inputs is a pretty sweet deal.
DSMan195276 10y ago
I can wager a guess: On paper smoothsort appears to be the better sorting algorithm, with identically or better complexity then Quicksort and Mergesort in basically every category. In addition, smoothsort works better with data that's close to being sorted. Why then is it slower in this case, and not as widely used? Part of the reason is that smoothsort is simply not very widely known, and thus not as many people know how it works compared to Quicksort or Mergesort. Nothing that, while complexity is important to take into account and looks good on paper, complexity leaves off the 'constants', which is generally what people attribute heapsort's (And thus, smoothsort's) higher number of comparisons. All that noted, smoothsort (and heapsort) have the big advantages of being in-place (merge is not), requiring O(1) extra space in the worst case (Quicksort can require up to O(n) extra space), and has a guaranteed upper-bound of O(n lg n) in the worst case (Quicksort can degenerate to O(n^2) performance with bad data). This means that heapsort may not always outperform Quicksort, but gives better guarantees about speed and data usage then Quicksort (And much better then Mergesort, which requires a lots of extra allocated data). Smoothsort is essentially just a better heapsort which functions even better when the list is close to already sorted.
- masklinn 10y ago
  Couldn't the implementation use a cheap check for near-sorting and only use smoothsort for near-sorted sequences, or use an insertion sort to increase sorted runs like timsort?

Surprised that musl I'd the slowest. Anyone have any insight into why qsort was coded like this?

by mangix 10y ago

Surprised that musl I'd the slowest. Anyone have any insight into why qsort was coded like this?

Apparently, to optimize for low memory usage (from reading the comments in the commit) http://git.musl-libc.org/cgit/musl/commit/?id=22263709eda9f7d692a0f484fd759f757418dbd7 http://git.musl-libc.org/cgit/musl/commit/?id=22263709eda9f7...

pavanky 10y ago
Doesn't quicksort have the least memory usage ?
- DSMan195276 10y ago
  Quicksort still requires O(lg n) memory because of its recursive nature. Since (lg n) is generally small, it's not that big of a deal. But with bad data, it's possible for Quicksort to degenerate to O(n) extra memory, which could be an issue (Especially for machines with little stack space). Heapsort (And thus smoothsort) are not recursive, so they require a constant amount of memory for all inputs.
  - eutectic 10y ago
    What if you always recurse into the smaller half, and use tail-recursion/looping to process the rest? Doesn't that keep the space usage bounded to O(log(n))?
    - deathanatos 10y ago
      This is correct, and is noted in the Wikipedia article's discussion of memory usage[1]. (Which I was only reading because I was erroneously thinking that quicksort was O(1) memory – I was completely forgetting stack space.) [1]: https://en.wikipedia.org/wiki/Quicksort#Space_complexity https://en.wikipedia.org/wiki/Quicksort#Space_complexity

pavanky 10y ago

The original post links to this page: http://calmerthanyouare.org/2013/05/31/qsort-shootout.html http://calmerthanyouare.org/2013/05/31/qsort-shootout.html There is an explanation provided that may be the reason, but it is not entirely convincing. Smoothsort is a variation of heapsort that performs especially well on nearly sorted inputs. It’s a pretty complicated beast and it does take some effort to wrap one’s head around it. Keith Schwarz has posted a nice walkthrough that the interested reader should check out. Considering that musl libc puts simplicity among its design goals, the choice of smoothsort could seem odd. The code is however clean and readable and getting an O(nlogn)O(nlog⁡n) worst case with near linear complexity for nearly sorted inputs is a pretty sweet deal.

DSMan195276 10y ago

I can wager a guess: On paper smoothsort appears to be the better sorting algorithm, with identically or better complexity then Quicksort and Mergesort in basically every category. In addition, smoothsort works better with data that's close to being sorted. Why then is it slower in this case, and not as widely used? Part of the reason is that smoothsort is simply not very widely known, and thus not as many people know how it works compared to Quicksort or Mergesort. Nothing that, while complexity is important to take into account and looks good on paper, complexity leaves off the 'constants', which is generally what people attribute heapsort's (And thus, smoothsort's) higher number of comparisons. All that noted, smoothsort (and heapsort) have the big advantages of being in-place (merge is not), requiring O(1) extra space in the worst case (Quicksort can require up to O(n) extra space), and has a guaranteed upper-bound of O(n lg n) in the worst case (Quicksort can degenerate to O(n^2) performance with bad data). This means that heapsort may not always outperform Quicksort, but gives better guarantees about speed and data usage then Quicksort (And much better then Mergesort, which requires a lots of extra allocated data). Smoothsort is essentially just a better heapsort which functions even better when the list is close to already sorted.

masklinn 10y ago
Couldn't the implementation use a cheap check for near-sorting and only use smoothsort for near-sorted sequences, or use an insertion sort to increase sorted runs like timsort?