```mailing list of musl libc
help / color / mirror / code / Atom feed```
```From: "David Wang" <00107082@163.com>
To: "Rich Felker" <dalias@libc.org>
Cc: musl@lists.openwall.com
Subject: [musl] Re:Re: [musl] qsort
Date: Fri, 17 Feb 2023 09:35:40 +0800 (CST)	[thread overview]
Message-ID: <25b3fe11.99f.1865d0343d3.Coremail.00107082@163.com> (raw)

At 2023-02-17 00:07:35, "Rich Felker" <dalias@libc.org> wrote:
>On Thu, Feb 16, 2023 at 11:15:24PM +0800, David Wang wrote:

>> Strange thing is, I made a textbook implementation of heapsort as in
>> following patch, optimized for size 8, the runtime and comparison
>> improved a lot.
>
>Do you have a good theoretical reason why that might be the case?

Smoothsort is way too complicated for me to make out a clear analyze, according to my reading, smoothsort would make the binary tree quite skewed, make the const factor in O(nlogn) bigger for average performance.
Its advantage  is for best case performance when the input is almost sorted.
Following quote  is from the smoothsort paper "Smoothsort, an alternative for sorting in situ",  written by Esger W. Dijkstra
"""
While heapsort prunes the tree leaf by leaf, smoothsort prunes the tree at the root, and
immediately one of heapsort's charms is lost: while the tree in heapsort remains beautifully
balanced, the tree in smoothsort can get very skew indeed. So why bother about smoothsort at all?
Well, I wanted to design a sorting algorithm of order N in the best case, of order N⋅log N in
the worst case, and with a smooth transition between the two (hence its name).
"""
I think it is safe to conclude:
1. heapsort is better than smoothsort for average performance
2. smoothsort is better than heapsort and  many other sorting algorithm for best case

>
>Yes, I think optimizing out the external memcpy calls for small sizes
>is a good idea regardless of whatever else we do. The code you tested
>is not valid (it has UB via aliasing violations) but we could fix it
>either using __may_alias__ types conditioned on __GNUC__, or exposing
>memcpy intrinsics where they don't result in circular definitions with
>some magic in src/include/string.h. I'd like to do the latter at some
>point anyway.
>

Thanks for pointing this out, I am so not experienced with engineering details, yet.

David
```

```next prev parent reply	other threads:[~2023-02-17  1:36 UTC|newest]

Thread overview: 34+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-01-20  1:49 Guy
2023-01-20 12:55 ` alice
2023-01-30 10:04   ` [musl] " David Wang
2023-02-01 18:01     ` Markus Wichmann
2023-02-02  2:12       ` [musl] " David Wang
2023-02-03  5:22         ` [musl] " David Wang
2023-02-03  8:03           ` Alexander Monakov
2023-02-03  9:01             ` [musl] " David Wang
2023-02-09 19:03       ` Rich Felker
2023-02-09 19:20         ` Alexander Monakov
2023-02-09 19:52           ` Rich Felker
2023-02-09 20:18             ` Rich Felker
2023-02-09 20:27               ` Pierpaolo Bernardi
2023-02-10  4:10             ` Markus Wichmann
2023-02-10 10:00         ` [musl] " David Wang
2023-02-10 13:10           ` Rich Felker
2023-02-10 13:45             ` [musl] " David Wang
2023-02-10 14:19               ` Rich Felker
2023-02-11  5:12                 ` [musl] " David Wang
2023-02-11  5:44                   ` alice
2023-02-11  8:39                     ` Joakim Sindholt
2023-02-11  9:06                       ` alice
2023-02-11  9:31                         ` [musl] " David Wang
2023-02-11 13:35                         ` Rich Felker
2023-02-11 17:18                           ` David Wang
2023-02-16 15:15       ` David Wang
2023-02-16 16:07         ` Rich Felker
2023-02-17  1:35           ` David Wang [this message]
2023-02-17 13:17           ` Alexander Monakov
2023-02-17 15:07             ` Rich Felker
2023-02-11  9:22     ` [musl] " Markus Wichmann
2023-02-11  9:36       ` [musl] " David Wang
2023-02-11  9:51       ` David Wang
2023-01-20 13:32 ` [musl] qsort Valery Ushakov
```

```Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,

Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

switches of git-send-email(1):

git send-email \
--to=00107082@163.com \
--cc=dalias@libc.org \
--cc=musl@lists.openwall.com \

https://kernel.org/pub/software/scm/git/docs/git-send-email.html

```Code repositories for project(s) associated with this public inbox