[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 10 Feb 2023 18:00:27 +0800 (CST)
From: "David Wang" <00107082@....com>
To: musl@...ts.openwall.com
Cc: "Markus Wichmann" <nullplan@....net>
Subject: Re:Re: Re:Re: qsort
>
>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
View attachment "report.html" of type "text/html" (7239 bytes)
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.
