Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 17 Feb 2023 09:35:40 +0800 (CST)
From: "David Wang" <>
To: "Rich Felker" <>
Subject: Re:Re: qsort

At 2023-02-17 00:07:35, "Rich Felker" <> 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.


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.