Date: Wed, 19 Apr 2023 15:46:38 +0000 From: Brooks Davis <brooks@freebsd.org> To: Hans Petter Selasky <hselasky@freebsd.org> 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: <ZEAM3rO9r5e97BHE@spindle.one-eyed-alien.net> In-Reply-To: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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 <hselasky@FreeBSD.org> > AuthorDate: 2022-09-08 10:16:43 +0000 > Commit: Hans Petter Selasky <hselasky@FreeBSD.org> > 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?ZEAM3rO9r5e97BHE>