Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 20 Jan 2023 13:55:39 +0100
From: "alice" <>
To: <>
Subject: Re: qsort

On Fri Jan 20, 2023 at 2:49 AM CET, Guy wrote:
> Hi,
> I have a program whose bottleneck is qsort.
> I noticed that the performance with musl is much slower then with glibc.

diagnosing why this is the case is somewhat difficult without either seeing
the program, or (better), a specific corpus of things that are being sorted in
both cases (to have a solid test case).

> Why is quick sort not used in musl?

presumably, because:

 /* Smoothsort, an adaptive variant of Heapsort.  Memory usage: O(1).
    Run time: Worst case O(n log n), close to O(n) in the mostly-sorted case. */

vanilla quicksort is O(log(n)) additional memory use, and so the optimisation
is more likely to be on memory use. on top of that, the worst-case performance
of quicksort is O(n^2) (apparently), but i'm not an expert on sorting
algorithms :). so, your specific (problem) case needs a specific example to

commit 22263709eda9f7d692a0f484fd759f757418dbd7 is the one that replaced the
old heapsort with this custom smoothsort implementation, with
52cf5c18f4ad3a7a59fb7113cf115c6fc05c7494 being the one that added the above

> Thanks,
> Guy

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.