[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <CPX182QJK5D6.2Y2DE5NACZ1I@sumire>
Date: Fri, 20 Jan 2023 13:55:39 +0100
From: "alice" <alice@...ya.dev>
To: <musl@...ts.openwall.com>
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
diagnose.
commit 22263709eda9f7d692a0f484fd759f757418dbd7 is the one that replaced the
old heapsort with this custom smoothsort implementation, with
52cf5c18f4ad3a7a59fb7113cf115c6fc05c7494 being the one that added the above
comment.
>
> 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.
