From nobody Wed Apr 19 15:46:38 2023 X-Original-To: dev-commits-src-all@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 4Q1lX53VC7z467GD; Wed, 19 Apr 2023 15:46:45 +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 4Q1lX46jTCz3hKQ; Wed, 19 Apr 2023 15:46:44 +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 131E43C0199; Wed, 19 Apr 2023 15:46:38 +0000 (UTC) Date: Wed, 19 Apr 2023 15:46:38 +0000 From: Brooks Davis To: Hans Petter Selasky Cc: src-committers@freebsd.org, 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> List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable In-Reply-To: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> X-Rspamd-Queue-Id: 4Q1lX46jTCz3hKQ 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 Wed, Apr 19, 2023 at 12:06:26PM +0000, Hans Petter Selasky wrote: > The branch main has been updated by hselasky: >=20 > URL: https://cgit.FreeBSD.org/src/commit/?id=3D8dcf3a82c54cb216df3213a013= 047907636a01da >=20 > commit 8dcf3a82c54cb216df3213a013047907636a01da > Author: Hans Petter Selasky > AuthorDate: 2022-09-08 10:16:43 +0000 > Commit: Hans Petter Selasky > CommitDate: 2023-04-19 12:04:22 +0000 >=20 > libc: Implement bsort(3) a bitonic type of sorting algorithm. > =20 > The bsort(3) algorithm works by swapping objects, similarly to qsort(= 3), > and does not require any significant amount of additional memory. > =20 > The bsort(3) algorithm doesn't suffer from the processing time issues > known the plague the qsort(3) family of algorithms, and is bounded by > a complexity of O(log2(N) * log2(N) * N), where N is the number of > elements in the sorting array. The additional complexity compared to > mergesort(3) is a fair tradeoff in situations where no memory may > be allocated. > =20 > The bsort(3) APIs are identical to those of qsort(3), allowing for > easy drop-in and testing. > =20 > The design of the bsort(3) algorithm allows for future parallell CPU > execution when sorting arrays. The current version of the bsort(3) > algorithm is single threaded. This is possible because fixed areas > of the sorting data is compared at a time, and can easily be divided > among different CPU's to sort large arrays faster. > =20 > Reviewed by: gbe@, delphij@, pauamma_gundo.com (manpages) > Sponsored by: NVIDIA Networking > Differential Revision: https://reviews.freebsd.org/D36493 Why was this needed? I'm not really a fan to adding new, non-standard sorts without a clear use case. I understand it has some specific advantages vs qsort, but are we going to use it? Doing so will make our code less portable so we almost certainly can't s/qsort/bsort/. I also note that the swap code is pointlessly slow for size > 256 and should almost certainly use aliasing with matching words like memcpy implementations do. Doing so would make it easier to port this code to CHERI where that is required. -- Brooks