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.4 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HTML_MESSAGE,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 13877 invoked from network); 8 Aug 2021 19:39:28 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 8 Aug 2021 19:39:28 -0000 Received: (qmail 19732 invoked by uid 550); 8 Aug 2021 19:39:26 -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 19711 invoked from network); 8 Aug 2021 19:39:25 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed; d=pobox.com; h= mime-version:references:in-reply-to:from:date:message-id:subject :to:cc:content-type; s=sasl; bh=UL8yvtMl5ivPL3DocxhYV5UmnjQjdWZU r2j1lhMhRlE=; b=hwSoUpwcyGra9TCbG67DK4I4pdc0J3uqpNt8gsACpjVnedTr aMcVB5ioMRRmAgpMhtY3Rf/AT8qwq9PvtRXFhqxj9YN7YX7tzQzqoLUbtg3NMoGu pMVmQw+WuRV27N+Rpol+QguQcVtUavUROZ3h0jkX70ijU23VmAk5ThosSHU= X-Gm-Message-State: AOAM530DltrRAOwmiUUOgJcECqe5qUrHyKwcBut+iDhqTBOchi4Azglw JZQn454MS5iTsRm3O5K6c9Lg4PRnI5o6I0/+3G8= X-Google-Smtp-Source: ABdhPJxbB89zjJ+k51oovq1HGSh8jg3kaAwpHJkMTH6ZXyIdyrk1K4Gc/LSQNgZKI6Zv5vozptqBZyERWvQ67AoaCqo= X-Received: by 2002:a17:906:1c8d:: with SMTP id g13mr971061ejh.116.1628451551523; Sun, 08 Aug 2021 12:39:11 -0700 (PDT) MIME-Version: 1.0 References: <20210808112612.44230-1-galibert@pobox.com> In-Reply-To: From: Olivier Galibert Date: Sun, 8 Aug 2021 21:39:00 +0200 X-Gmail-Original-Message-ID: Message-ID: To: Jon Chesterfield Cc: musl@lists.openwall.com Content-Type: multipart/alternative; boundary="00000000000043369f05c9116c4a" X-Pobox-Relay-ID: 4EBF932A-F880-11EB-9F7B-8B3BC6D8090B-92059326!pb-smtp1.pobox.com Subject: Re: [musl] [PATCH] stdlib: implement qsort_r --00000000000043369f05c9116c4a Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I don=E2=80=99t believe in deep inlining in that case, there=E2=80=99s too = much recursion. As for adding overhead to qsort by sharing qsort_r=E2=80=99s code it is ind= eed trivial to do but I don=E2=80=99t know whether the tradeoff should be done. OG. Le dim. 8 ao=C3=BBt 2021 =C3=A0 14:42, Jon Chesterfield < jonathanchesterfield@gmail.com> a =C3=A9crit : > On Sun, Aug 8, 2021 at 12:29 PM Olivier Galibert > wrote: > >> The extension qsort_r allows calling qsort on a list of indices >> without having a global variable to hold the data to sort. >> > > qsort_r is a strong improvement on qsort. I think it's available outside = of > glibc. > > I remember doing something similar locally. Just looked it up and I > renamed & mutated qsort to pass the context along. Therefore typed into > email, I think something like this would provide an implementation of > qsort in terms of qsort_r. > > // declare qsort_r > typedef int (*cmp_r_t)(const void *, const void *, void * context); > > > void qsort_r(void *base, size_t nel, size_t width, cmp_r_t cmp, void* > context); > > > // pass it a function that extracts the comparator for qsort from the > // context > typedef int (*cmp_t)(const void *, const void *); > > > static int compare_adapter(const void *l, const void *r, void * context) > { > cmpt_t c =3D (cmpt_t) context; > > > return c(l,r); > > > } > > // tail call > void qsort(void *base, size_t nel, size_t width, cmp_t c) > { > return qsort_r(base, nel, width, compare_adapter, (cmp_t_t)c); > > > } > > Given optimism about inlining or an always inline annotation > it should turn into the same machine code as the macro > instantiation approach. Alternatively it's a tail call into qsort_r, so > a couple of indirections in exchange for minimal code size growth. > > I haven't compiled or tested that (or looked up the coding conventions > for musl) so this is a drive by suggestion, written in pseudocode > instead of prose for clarity. > > Thanks all! > > Jon > > --00000000000043369f05c9116c4a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: base64 PGRpdiBkaXI9ImF1dG8iPkkgZG9u4oCZdCBiZWxpZXZlIGluIGRlZXAgaW5saW5pbmcgaW4gdGhh dCBjYXNlLCB0aGVyZeKAmXMgdG9vIG11Y2ggcmVjdXJzaW9uLsKgIEFzIGZvciBhZGRpbmcgb3Zl cmhlYWQgdG8gcXNvcnQgYnkgc2hhcmluZyBxc29ydF9y4oCZcyBjb2RlIGl0IGlzIGluZGVlZCB0 cml2aWFsIHRvIGRvIGJ1dCBJIGRvbuKAmXQga25vdyB3aGV0aGVyIHRoZSB0cmFkZW9mZiBzaG91 bGQgYmUgZG9uZS48L2Rpdj48ZGl2IGRpcj0iYXV0byI+PGJyPjwvZGl2PjxkaXYgZGlyPSJhdXRv Ij7CoCBPRy48L2Rpdj48ZGl2Pjxicj48ZGl2IGNsYXNzPSJnbWFpbF9xdW90ZSI+PGRpdiBkaXI9 Imx0ciIgY2xhc3M9ImdtYWlsX2F0dHIiPkxlwqBkaW0uIDggYW/Du3QgMjAyMSDDoCAxNDo0Miwg Sm9uIENoZXN0ZXJmaWVsZCAmbHQ7PGEgaHJlZj0ibWFpbHRvOmpvbmF0aGFuY2hlc3RlcmZpZWxk QGdtYWlsLmNvbSI+am9uYXRoYW5jaGVzdGVyZmllbGRAZ21haWwuY29tPC9hPiZndDsgYSDDqWNy aXTCoDo8YnI+PC9kaXY+PGJsb2NrcXVvdGUgY2xhc3M9ImdtYWlsX3F1b3RlIiBzdHlsZT0ibWFy Z2luOjBweCAwcHggMHB4IDAuOGV4O2JvcmRlci1sZWZ0LXdpZHRoOjFweDtib3JkZXItbGVmdC1z dHlsZTpzb2xpZDtwYWRkaW5nLWxlZnQ6MWV4O2JvcmRlci1sZWZ0LWNvbG9yOnJnYigyMDQsMjA0 LDIwNCkiPjxkaXYgZGlyPSJsdHIiPjxkaXYgZGlyPSJsdHIiPk9uIFN1biwgQXVnIDgsIDIwMjEg YXQgMTI6MjkgUE0gT2xpdmllciBHYWxpYmVydCAmbHQ7PGEgaHJlZj0ibWFpbHRvOmdhbGliZXJ0 QHBvYm94LmNvbSIgdGFyZ2V0PSJfYmxhbmsiPmdhbGliZXJ0QHBvYm94LmNvbTwvYT4mZ3Q7IHdy b3RlOjxicj48L2Rpdj48ZGl2IGNsYXNzPSJnbWFpbF9xdW90ZSI+PGJsb2NrcXVvdGUgY2xhc3M9 ImdtYWlsX3F1b3RlIiBzdHlsZT0ibWFyZ2luOjBweCAwcHggMHB4IDAuOGV4O2JvcmRlci1sZWZ0 LXdpZHRoOjFweDtib3JkZXItbGVmdC1zdHlsZTpzb2xpZDtwYWRkaW5nLWxlZnQ6MWV4O2JvcmRl ci1sZWZ0LWNvbG9yOnJnYigyMDQsMjA0LDIwNCkiPlRoZSBleHRlbnNpb24gcXNvcnRfciBhbGxv d3MgY2FsbGluZyBxc29ydCBvbiBhIGxpc3Qgb2YgaW5kaWNlczxicj4NCndpdGhvdXQgaGF2aW5n IGEgZ2xvYmFsIHZhcmlhYmxlIHRvIGhvbGQgdGhlIGRhdGEgdG8gc29ydC48YnI+PC9ibG9ja3F1 b3RlPjxkaXY+PGJyPjwvZGl2PjxkaXY+PGRpdj5xc29ydF9yIGlzIGEgc3Ryb25nIGltcHJvdmVt ZW50IG9uIHFzb3J0LiBJIHRoaW5rIGl0JiMzOTtzIGF2YWlsYWJsZSBvdXRzaWRlIG9mPC9kaXY+ PC9kaXY+PGRpdj5nbGliYy48L2Rpdj48ZGl2Pjxicj48L2Rpdj48ZGl2PkkgcmVtZW1iZXIgZG9p bmcgc29tZXRoaW5nIHNpbWlsYXIgbG9jYWxseS4gSnVzdCBsb29rZWQgaXQgdXAgYW5kIEk8L2Rp dj48ZGl2PnJlbmFtZWQgJmFtcDsgbXV0YXRlZCBxc29ydCB0byBwYXNzIHRoZSBjb250ZXh0IGFs b25nLiBUaGVyZWZvcmUgdHlwZWQgaW50bzxicj5lbWFpbCwgSSB0aGluayBzb21ldGhpbmcgbGlr ZSB0aGlzIHdvdWxkIHByb3ZpZGUgYW4gaW1wbGVtZW50YXRpb24gb2Y8YnI+cXNvcnQgaW4gdGVy bXMgb2YgcXNvcnRfci7CoDwvZGl2PjxkaXY+PGJyPjwvZGl2PjxkaXY+Ly8gZGVjbGFyZSBxc29y dF9yPGJyPnR5cGVkZWYgaW50ICgqY21wX3JfdCkoY29uc3Qgdm9pZCAqLCBjb25zdCB2b2lkICos IHZvaWQgKiBjb250ZXh0KTsgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAg wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAg wqAgwqA8YnI+dm9pZCBxc29ydF9yKHZvaWQgKmJhc2UsIHNpemVfdCBuZWwsIHNpemVfdCB3aWR0 aCwgY21wX3JfdCBjbXAsIHZvaWQqIGNvbnRleHQpOyDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oDxicj48YnI+Ly8gcGFzcyBpdCBhIGZ1bmN0aW9uIHRoYXQgZXh0cmFjdHMgdGhlIGNvbXBhcmF0 b3IgZm9yIHFzb3J0IGZyb20gdGhlPGJyPi8vIGNvbnRleHQ8YnI+dHlwZWRlZiBpbnQgKCpjbXBf dCkoY29uc3Qgdm9pZCAqLCBjb25zdCB2b2lkICopOyDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoDxicj5zdGF0aWMg aW50IGNvbXBhcmVfYWRhcHRlcihjb25zdCB2b2lkICpsLCBjb25zdCB2b2lkICpyLCB2b2lkICog Y29udGV4dCk8YnI+ezxicj7CoCBjbXB0X3QgYyA9IChjbXB0X3QpIGNvbnRleHQ7IMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIDxicj7CoCByZXR1cm4gYyhsLHIpOyDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDC oCDCoCA8YnI+fTxicj48YnI+Ly8gdGFpbCBjYWxsPGJyPnZvaWQgcXNvcnQodm9pZCAqYmFzZSwg c2l6ZV90IG5lbCwgc2l6ZV90IHdpZHRoLCBjbXBfdCBjKTxicj57PGJyPsKgIHJldHVybiBxc29y dF9yKGJhc2UsIG5lbCwgd2lkdGgsIGNvbXBhcmVfYWRhcHRlciwgKGNtcF90X3QpYyk7IMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg IMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIDxicj59PGJyPjwvZGl2 PjxkaXY+PGJyPjwvZGl2PjxkaXY+R2l2ZW4gb3B0aW1pc20gYWJvdXQgaW5saW5pbmcgb3IgYW4g YWx3YXlzIGlubGluZSBhbm5vdGF0aW9uPC9kaXY+PGRpdj5pdCBzaG91bGQgdHVybiBpbnRvIHRo ZSBzYW1lIG1hY2hpbmUgY29kZSBhcyB0aGUgbWFjcm88YnI+aW5zdGFudGlhdGlvbiBhcHByb2Fj aC4gQWx0ZXJuYXRpdmVseSBpdCYjMzk7cyBhIHRhaWwgY2FsbCBpbnRvIHFzb3J0X3IsIHNvPGJy PmEgY291cGxlIG9mIGluZGlyZWN0aW9ucyBpbiBleGNoYW5nZSBmb3IgbWluaW1hbCBjb2RlIHNp emUgZ3Jvd3RoLjxicj48L2Rpdj48ZGl2Pjxicj48L2Rpdj48ZGl2PkkgaGF2ZW4mIzM5O3QgY29t cGlsZWQgb3IgdGVzdGVkIHRoYXQgKG9yIGxvb2tlZCB1cCB0aGUgY29kaW5nIGNvbnZlbnRpb25z PC9kaXY+PGRpdj5mb3IgbXVzbCkgc28gdGhpcyBpcyBhIGRyaXZlIGJ5IHN1Z2dlc3Rpb24sIHdy aXR0ZW4gaW4gcHNldWRvY29kZTwvZGl2PjxkaXY+aW5zdGVhZCBvZiBwcm9zZSBmb3IgY2xhcml0 eS48L2Rpdj48ZGl2Pjxicj48L2Rpdj48ZGl2PlRoYW5rcyBhbGwhPC9kaXY+PC9kaXY+PC9kaXY+ PGRpdiBkaXI9Imx0ciI+PGRpdiBjbGFzcz0iZ21haWxfcXVvdGUiPjxkaXY+PGJyPjwvZGl2Pjxk aXY+Sm9uPC9kaXY+PGRpdj48YnI+PC9kaXY+PC9kaXY+PC9kaXY+DQo8L2Jsb2NrcXVvdGU+PC9k aXY+PC9kaXY+DQo= --00000000000043369f05c9116c4a--