Date: Thu, 20 Apr 2023 19:54:12 +0200 From: Hans Petter Selasky <hselasky@freebsd.org> To: Jessica Clarke <jrtc27@freebsd.org> Cc: "src-committers@freebsd.org" <src-committers@FreeBSD.org>, "dev-commits-src-all@freebsd.org" <dev-commits-src-all@FreeBSD.org>, "dev-commits-src-main@freebsd.org" <dev-commits-src-main@FreeBSD.org> Subject: Re: git: bb8e8e230d94 - main - Revert "libc: Implement bsort(3) a bitonic type of sorting algorithm." Message-ID: <e8c11ee1-e01e-4729-949a-79850cfe5230@freebsd.org> In-Reply-To: <145FD575-5987-4BD8-805D-26DB13EBF06A@freebsd.org> References: <202304201717.33KHHJsQ044448@gitrepo.freebsd.org> <145FD575-5987-4BD8-805D-26DB13EBF06A@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?e8c11ee1-e01e-4729-949a-79850cfe5230>