mailing list of musl libc
 help / color / mirror / code / Atom feed
From: "David Wang" <00107082@163.com>
To: musl@lists.openwall.com
Subject: [musl] Re:Re: [musl] qsort
Date: Mon, 30 Jan 2023 18:04:39 +0800 (CST)	[thread overview]
Message-ID: <4d290220.36d6.1860222ca46.Coremail.00107082@163.com> (raw)
In-Reply-To: <CPX182QJK5D6.2Y2DE5NACZ1I@sumire>

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

  reply	other threads:[~2023-01-30 10:05 UTC|newest]

Thread overview: 34+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-01-20  1:49 Guy
2023-01-20 12:55 ` alice
2023-01-30 10:04   ` David Wang [this message]
2023-02-01 18:01     ` [musl] " Markus Wichmann
2023-02-02  2:12       ` [musl] " David Wang
2023-02-03  5:22         ` [musl] " David Wang
2023-02-03  8:03           ` Alexander Monakov
2023-02-03  9:01             ` [musl] " David Wang
2023-02-09 19:03       ` Rich Felker
2023-02-09 19:20         ` Alexander Monakov
2023-02-09 19:52           ` Rich Felker
2023-02-09 20:18             ` Rich Felker
2023-02-09 20:27               ` Pierpaolo Bernardi
2023-02-10  4:10             ` Markus Wichmann
2023-02-10 10:00         ` [musl] " David Wang
2023-02-10 13:10           ` Rich Felker
2023-02-10 13:45             ` [musl] " David Wang
2023-02-10 14:19               ` Rich Felker
2023-02-11  5:12                 ` [musl] " David Wang
2023-02-11  5:44                   ` alice
2023-02-11  8:39                     ` Joakim Sindholt
2023-02-11  9:06                       ` alice
2023-02-11  9:31                         ` [musl] " David Wang
2023-02-11 13:35                         ` Rich Felker
2023-02-11 17:18                           ` David Wang
2023-02-16 15:15       ` David Wang
2023-02-16 16:07         ` Rich Felker
2023-02-17  1:35           ` [musl] " David Wang
2023-02-17 13:17           ` Alexander Monakov
2023-02-17 15:07             ` Rich Felker
2023-02-11  9:22     ` [musl] " Markus Wichmann
2023-02-11  9:36       ` [musl] " David Wang
2023-02-11  9:51       ` David Wang
2023-01-20 13:32 ` [musl] qsort Valery Ushakov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=4d290220.36d6.1860222ca46.Coremail.00107082@163.com \
    --to=00107082@163.com \
    --cc=musl@lists.openwall.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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).