[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 10 Feb 2023 08:10:45 -0500
From: Rich Felker <dalias@...c.org>
To: David Wang <00107082@....com>
Cc: musl@...ts.openwall.com, Markus Wichmann <nullplan@....net>
Subject: Re: Re:Re: Re:Re: qsort
On Fri, Feb 10, 2023 at 06:00:27PM +0800, David Wang wrote:
> >
> >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....)
What tool was used for this? gprof or anything else invasive is not
meaningful; for tiny functions, the entire time measured will be the
profiling overhead. perf(1) is the only way I know to get meaningful
numbers.
In particular, it makes no sense that significant time was spent in
wrapper_cmp, which looks like (i386):
0: ff 64 24 0c jmp *0xc(%esp)
or (x86_64):
0: ff e2 jmpq *%rdx
or (arm):
0: 4710 bx r2
but I can imagine it being (relatively) gigantic with a call out to
profiling code.
Rich
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.
