[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <25b3fe11.99f.1865d0343d3.Coremail.00107082@163.com>
Date: Fri, 17 Feb 2023 09:35:40 +0800 (CST)
From: "David Wang" <00107082@....com>
To: "Rich Felker" <dalias@...c.org>
Cc: musl@...ts.openwall.com
Subject: Re:Re: qsort
At 2023-02-17 00:07:35, "Rich Felker" <dalias@...c.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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
