On 4/20/23 19:18, Jessica Clarke wrote:
On 20 Apr 2023, at 18:17, Hans Petter Selasky <[email protected]> wrote:
The branch main has been updated by hselasky:
URL:
https://cgit.FreeBSD.org/src/commit/?id=bb8e8e230d94c9522bd9ff95c13dc9f5b1592929
commit bb8e8e230d94c9522bd9ff95c13dc9f5b1592929
Author: Hans Petter Selasky <[email protected]>
AuthorDate: 2023-04-20 16:50:32 +0000
Commit: Hans Petter Selasky <[email protected]>
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
