[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 9 Mar 2021 08:42:43 -0500
From: Rich Felker <dalias@...c.org>
To: Alexander Monakov <amonakov@...ras.ru>
Cc: musl@...ts.openwall.com,
Érico Nogueira <ericonr@...root.org>
Subject: Re: [PATCH v2] add qsort_r.
On Tue, Mar 09, 2021 at 12:11:37PM +0300, Alexander Monakov wrote:
> On Tue, 9 Mar 2021, Érico Nogueira wrote:
>
> > since most discussion around the addition of this function has centered
> > around the possible code duplication it requires or that qsort would
> > become much slower if implemented as a wrapper around qsort_r
>
> How much is "much slower", did anyone provide figures to support this claim?
> The extra cost that a wrapper brings is either one indirect jump instruction,
> or one trivially-predictable conditional branch per one comparator invocation.
Quite a bit I'd expect. Each call to cmp would involve an extra level
of call wrapper. With full IPA/inlining it could be optimized out, but
only by making a non-_r copy of all the qsort code in the process at
optimize time.
> Constant factor in musl qsort is quite high, I'd be surprised if the extra
> overhead from one additional branch is even possible to measure.
I don't think it's just a branch. It's a call layer. qsort_r internals
with cmp=wrapper_cmp, ctx=real_cmp -> wrapper_cmp(x, y, real_cmp) ->
real_cmp(x, y). But I'm not opposed to looking at some numbers if you
think it might not matter. Maybe because it's a tail call it does
collapse to essentially just a branch in terms of cost..
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.
