Skip site navigation (1)Skip section navigation (2)
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>