|
Message-ID: <20230210131044.GZ4163@brightrain.aerifal.cx> 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.