From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.3 required=5.0 tests=MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 21331 invoked from network); 9 Mar 2021 15:03:42 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 9 Mar 2021 15:03:42 -0000 Received: (qmail 5996 invoked by uid 550); 9 Mar 2021 15:03:35 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 5975 invoked from network); 9 Mar 2021 15:03:34 -0000 Date: Tue, 9 Mar 2021 10:03:22 -0500 From: Rich Felker To: Alexander Monakov Cc: musl@lists.openwall.com, =?utf-8?B?w4lyaWNv?= Nogueira Message-ID: <20210309150320.GU32655@brightrain.aerifal.cx> References: <20210309035652.32453-1-ericonr@disroot.org> <20210309134242.GS32655@brightrain.aerifal.cx> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] [PATCH v2] add qsort_r. On Tue, Mar 09, 2021 at 05:13:39PM +0300, Alexander Monakov wrote: > > 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.. > > First of all it's not necessarily a "call layer". > > You could change cmp call site such that NULL comparator implies that > non-_r version was called and the original comparator address is in ctx: > > static inline int call_cmp(void *v1, void *v2, void *ctx, cmpfun cmp) > { > if (cmp) > return cmp(v1, v2, ctx); > return ((cmpfun)ctx)(v1, v2); > } > > This is just a conditional branch at call site after trivial inlining. This works, but it's not what I would call writing qsort as a wrapper around qsort_r, because it depends on qsort_r having this additional libc-internal contract to treat null cmp specially, and it might be undesirable because it then does something rather awful if the application calls qsort_r with a null cmp pointer (rather than just crashing with PC=0). > Second, if you make a "conventional" wrapper, then on popular architectures > it is a single instruction (powerpc64 ABI demonstrates its insanity here): > > static int wrapper_cmp(void *v1, void *v2, void *ctx) > { > return ((cmpfun)ctx)(v1, v2); > } > > Some examples: > > amd64: jmp %rdx > i386: jmp *12(%esp) > arm: bx r2 > aarch64:br x2 > > How is this not obvious? Now that you mention it it's obvious that the compiler should be able to do this. gcc -Os alone does not, which looks like yet another reason to nuke -Os, but I think in musl it would do the right thing already. It turns out the problem is that gcc emits spurious frame pointer setup and teardown without -fomit-frame-pointer. For some reason though it's gigantic on powerpc64. It fails to do a tail call at all... Rich