Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 30 Jan 2023 18:04:39 +0800 (CST)
From: "David Wang" <00107082@....com>
To: musl@...ts.openwall.com
Subject: Re:Re: qsort

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@...ya.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

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.