[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <4d290220.36d6.1860222ca46.Coremail.00107082@163.com>
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.
