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.