Re: git: bb8e8e230d94 - main - Revert "libc: Implement bsort(3) a bitonic type of sorting algorithm."
Date: Thu, 20 Apr 2023 17:54:12 UTC
On 4/20/23 19:18, Jessica Clarke wrote: > On 20 Apr 2023, at 18:17, Hans Petter Selasky <hselasky@FreeBSD.org> wrote: >> >> The branch main has been updated by hselasky: >> >> URL: https://cgit.FreeBSD.org/src/commit/?id=bb8e8e230d94c9522bd9ff95c13dc9f5b1592929 >> >> commit bb8e8e230d94c9522bd9ff95c13dc9f5b1592929 >> Author: Hans Petter Selasky <hselasky@FreeBSD.org> >> AuthorDate: 2023-04-20 16:50:32 +0000 >> Commit: Hans Petter Selasky <hselasky@FreeBSD.org> >> CommitDate: 2023-04-20 17:16:14 +0000 >> >> Revert "libc: Implement bsort(3) a bitonic type of sorting algorithm." >> >> Some points for the future: >> - libc is not the right place for sorting algorithms. >> Probably libutil is better suited for this purpose or >> a dedicated libsort. Should move all sorting algorithms >> away from libc eventually. > > qsort is part of ISO C, so no. Hi Jessica, I know, and maybe it shouldn't be part of ISO C in the future. >> - CheriBSD uses capabilities for memory access, and could >> benefit from a standard memswap() function. >> - Do something about qsort() in FreeBSD's libc like: >> - Mark it deprecated on FreeBSD, as a first step, >> due to missing limits on CPU time. > > Nobody’s saying that, quite the opposite. It’s in ISO C. https://en.cppreference.com/w/c/algorithm/qsort Quote: "Despite the name, neither C nor POSIX standards require this function to be implemented using quicksort or make any complexity or stability guarantees." This is the definition of chaos. ISO C says qsort() may be just anything? How can programmers rely on this? > >> - Audit the use of qsort() in the FreeBSD base system >> and consider swapping to other existing sorting >> algorithms. > > No. We’re saying to make the implementation better. Someone interested needs to drive it. And it needs to be agreed what qsort() should really do - why not just call heapsort()? We are still in compliance with ISO C by doing that. Anyway, my time budget on sorting problems is far exceeded, and I would like to suggest a general warning flag __may_be_slow, as appropriate for qsort(). Isn't that just what ISO C says about qsort() ? I've put up a review here for you all: https://reviews.freebsd.org/D39723 --HPS