mailing list of musl libc
 help / color / mirror / code / Atom feed
* [musl] qsort
@ 2023-01-20  1:49 Guy
  2023-01-20 12:55 ` alice
  2023-01-20 13:32 ` [musl] qsort Valery Ushakov
  0 siblings, 2 replies; 4+ messages in thread
From: Guy @ 2023-01-20  1:49 UTC (permalink / raw)
  To: musl

Hi,

I have a program whose bottleneck is qsort.
I noticed that the performance with musl is much slower then with glibc.
Why is quick sort not used in musl?

Thanks,
Guy

^ permalink raw reply	[flat|nested] 4+ messages in thread

* Re: [musl] qsort
  2023-01-20  1:49 [musl] qsort Guy
@ 2023-01-20 12:55 ` alice
  2023-01-30 10:04   ` [musl] " David Wang
  2023-01-20 13:32 ` [musl] qsort Valery Ushakov
  1 sibling, 1 reply; 4+ messages in thread
From: alice @ 2023-01-20 12:55 UTC (permalink / raw)
  To: musl

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


^ permalink raw reply	[flat|nested] 4+ messages in thread

* [musl] Re: qsort
  2023-01-20  1:49 [musl] qsort Guy
  2023-01-20 12:55 ` alice
@ 2023-01-20 13:32 ` Valery Ushakov
  1 sibling, 0 replies; 4+ messages in thread
From: Valery Ushakov @ 2023-01-20 13:32 UTC (permalink / raw)
  To: musl

Guy <galfandary@gmail.com> wrote:

> I have a program whose bottleneck is qsort.
> I noticed that the performance with musl is much slower then with glibc.
> Why is quick sort not used in musl?

Sorry for a random drive by remark that is only very tangentially
related to your question...  quicksort is not guaranteed to be quick
and can be quadratic on "bad" input.  Everyone probably knows that in
a kind of theoretical way, but you can run into these pathological
cases in quite mundane circumstances.  E.g. the NNTP overviews for the
Lua mailing list archives (gmane.comp.lang.lua.general) at gmane.io
used to trigger this worst case scenario for me (~120s to enter the ng
and sort/thread articles with qsort(3) vs. ~15s for heapsort).

-uwe


^ permalink raw reply	[flat|nested] 4+ messages in thread

* [musl] Re:Re: [musl] qsort
  2023-01-20 12:55 ` alice
@ 2023-01-30 10:04   ` David Wang
  0 siblings, 0 replies; 4+ messages in thread
From: David Wang @ 2023-01-30 10:04 UTC (permalink / raw)
  To: musl

I made a test comparing the performance difference  about qsort between   musl and glibc, the code is just sorting some random set of data, and collect how many times the compare operation   invoked,  also I collect the counters for c++ sort  which also is designed to throttle the worse case performance of quick sort.
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>

using namespace std;
typedef long long LL;
#define MAXN 200000
int as[MAXN];
int bs[MAXN];

LL c1=0, c2=0;
bool rcmp(int a, int b) { c2++; return a>b; }
int myrcmp(const void *a, const void *b) {c1++; return *(const int*)b-*(const int*)a;}
 
int main() {
  int i, j, k, t;
  time_t tx = time(NULL);
  srand(tx);
  for (k=0; k<1024; k++) {
    for (i=0; i<MAXN; i++) as[i]=i;
    for (i=MAXN-1; i>0; i--) {
      j=rand()%(i+1);
      if (j!=i) { t=as[i]; as[i]=as[j]; as[j]=t; }
    }
    for (i=0; i<MAXN; i++) bs[i]=as[i];
    qsort(as, MAXN, sizeof(as[0]), myrcmp);
    sort(bs, bs+MAXN, rcmp);
  }
  printf("qsort:%lld  vs   sort:%lld\n", c1, c2);
  return 0;
}
```

WIth glibc,  average report is  "qsort:3351271634  vs   sort:4358412048"
But on alpine,  it is "qsort:9585927992  vs   sort:4354856330"

On average, qsort with musl is significantly slower than c++ sort, while with glibc the average performance of qsort is bettern than c++ sort.

I think something is strange here,  the O(n*n) worse case performance of quick sort is really an issue, but why the average performance is  that bad,  comparing  with c++ sort.
Is there any story about the implementation of qsort in musl?  I feel it focused on performance improvement for some special kind of domain, but not clear what it is.

David Wang


At 2023-01-20 20:55:39, "alice" <alice@ayaya.dev> wrote:
>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

^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2023-01-30 10:05 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-01-20  1:49 [musl] qsort Guy
2023-01-20 12:55 ` alice
2023-01-30 10:04   ` [musl] " David Wang
2023-01-20 13:32 ` [musl] qsort Valery Ushakov

Code repositories for project(s) associated with this public inbox

	https://git.vuxu.org/mirror/musl/

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).