Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm.

From: Brooks Davis <brooks_at_freebsd.org>
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