From nobody Thu Apr 20 15:50:01 2023 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4Q2MYX1pq9z46D5W; Thu, 20 Apr 2023 15:50:08 +0000 (UTC) (envelope-from brooks@spindle.one-eyed-alien.net) Received: from spindle.one-eyed-alien.net (spindle.one-eyed-alien.net [199.48.129.229]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4Q2MYW5R4Jz41Y7; Thu, 20 Apr 2023 15:50:07 +0000 (UTC) (envelope-from brooks@spindle.one-eyed-alien.net) Authentication-Results: mx1.freebsd.org; none Received: by spindle.one-eyed-alien.net (Postfix, from userid 3001) id 4343C3C0199; Thu, 20 Apr 2023 15:50:01 +0000 (UTC) Date: Thu, 20 Apr 2023 15:50:01 +0000 From: Brooks Davis To: Hans Petter Selasky Cc: Colin Percival , Jessica Clarke , src-committers , dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm. Message-ID: References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> <3B5734C4-8630-4CD5-BA8D-DE33899161F1@freebsd.org> <2840BE79-CC25-427A-A5E9-476A38E749E3@freebsd.org> <42d63675-9b1f-70dc-a1da-fef3d43790fd@freebsd.org> <010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000@email.amazonses.com> <1ce00b7b-e34b-a91b-59ef-c3ee9683c4a0@freebsd.org> List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable In-Reply-To: <1ce00b7b-e34b-a91b-59ef-c3ee9683c4a0@freebsd.org> X-Rspamd-Queue-Id: 4Q2MYW5R4Jz41Y7 X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:36236, ipnet:199.48.128.0/22, country:US] X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-ThisMailContainsUnwantedMimeParts: N On Thu, Apr 20, 2023 at 08:32:54AM +0200, Hans Petter Selasky wrote: > On 4/20/23 00:28, Colin Percival wrote: > >=20 > > Quicksort with cryptographically randomized pivot selection is O(N^2) w= orst > > case but O(N log N) average-case-for-worst-case-inputs which is good en= ough > > for most purposes. > >=20 > > Quicksort with in-place median-of-medians pivot selection is O(N log N)= =20 > > worst > > case. > >=20 > > Both of them can be easily implemented with O(log N) extra space (for= =20 > > the call > > stack), and with O(1) extra space if you're insane enough to care. >=20 > Yes, I know there are different ways to mitigate O(N^2) behaviour, but=20 > there is not yet after xxx years of research a way to fully mitigate=20 > that behaviour. >=20 > What I think, there should be some statistics done in our qsort() when=20 > it goes to O(N^2), and then it could fallback to bsort() for example, to= =20 > avoid issues with malloc(). >=20 > Or maybe one round of bsort() is enough to make qsort() do its thing=20 > right. I want to investigate that. Like a hybrid. Please perform this investigation out of the tree with without exposing new symbols. For testing there is not need for this to be in libc at all as you can do most testing via LD_PRELOAD replacing qsort. There is certainly room to improve our sort implementations (we've had to replace mergesort entirely in CheriBSD due to it's terrible design that stores unaligned pointers in place of elements) and I encourage work on it, but I see little or no scope for adding more sorts in libc. -- Brooks