From: "David Wang" <00107082@163.com>
To: musl@lists.openwall.com
Cc: "Markus Wichmann" <nullplan@gmx.net>
Subject: [musl] Re:Re: [musl] Re:Re: [musl] qsort
Date: Fri, 10 Feb 2023 18:00:27 +0800 (CST) [thread overview]
Message-ID: <75d9cfae.35eb.1863ac4e3c0.Coremail.00107082@163.com> (raw)
In-Reply-To: <20230209190316.GU4163@brightrain.aerifal.cx>
[-- Attachment #1: Type: text/plain, Size: 1143 bytes --]
>
>Before we consider any such change though we should probably see
>profiling data to determine where the time is being spent in
>smoothsort, in case it's stupid stuff that's fixable.
>
>Rich
I made a rough profiling against current implementation of qsort in musl (Just copy the source code and recompile it to expose symbols)
The function call counters are as following:
main: 931387
qsort2: 917148 <----this is qsort
__qsort_r: 911594
trinkle: 811314
sift: 537263
wrapper_cmp: 257403 <--- wrapper cmp function
mycmp: 167410 <---real cmp function
cycle: 105809
shr: 41585
pntz: 27833
_init: 14925
a_ctz_64: 11341
a_ctz_l: 9127
shl: 8333
1. wrapper_cmp took about 25%, overhead (257403-167410) seems high when the real comp functions is very simple(which just compares integer values), could be optimized out for qsort
2. most "qsort" time spend in "trinkle", and most "trinkle" time spend in "sift".
A tree-view profiling report is attached. (There may be several incorrect call-chains collected, but I think the proportion among function-call counters is correct, with high probability....)
FYI
David
[-- Attachment #2: report.html --]
[-- Type: text/html, Size: 7239 bytes --]
next prev parent reply other threads:[~2023-02-10 10:00 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 ` [musl] " David Wang
2023-02-01 18:01 ` 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 ` David Wang [this message]
2023-02-10 13:10 ` [musl] " 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=75d9cfae.35eb.1863ac4e3c0.Coremail.00107082@163.com \
--to=00107082@163.com \
--cc=musl@lists.openwall.com \
--cc=nullplan@gmx.net \
/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).