Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm.
- Reply: Hans Petter Selasky : "Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm."
- In reply to: Hans Petter Selasky : "git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm."
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Wed, 19 Apr 2023 15:46:38 UTC
On Wed, Apr 19, 2023 at 12:06:26PM +0000, Hans Petter Selasky wrote: > The branch main has been updated by hselasky: > > URL: https://cgit.FreeBSD.org/src/commit/?id=8dcf3a82c54cb216df3213a013047907636a01da > > 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 > > libc: Implement bsort(3) a bitonic type of sorting algorithm. > > The bsort(3) algorithm works by swapping objects, similarly to qsort(3), > and does not require any significant amount of additional memory. > > 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. > > The bsort(3) APIs are identical to those of qsort(3), allowing for > easy drop-in and testing. > > 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. > > 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