Re: git: a7469c9c0a50 - main - libc: bsort_s() requires both __BSD_VISIBLE and __EXT1_VISIBLE

On 4/20/23 01:43, Brooks Davis wrote:
> On Wed, Apr 19, 2023 at 11:35:56PM +0200, Hans Petter Selasky wrote:
>> On 4/19/23 22:29, Brooks Davis wrote:
>>> This is a formal request to revert all commits related to bsort.  It
>>> should not have been committed without much broader discussion and IMO
>>> does not belong in the tree.  It certainly should not be in the tree
>>> under such a generic name.
>>>
>>> -- Brooks
>>
>> Hi Brooks,
>>
>> I don't have an issue reverting my bsort() patch series, but please
>> clarify your statement first. Who are "we" this time, representing this
>> formal request for revert?
> 
> This is my request.

Hi Brooks,

Maybe bsort() can be an internal symbol to libc, I'm not sure if we 
support that.

At the same time I want a solution forward about our qsort(). I would 
say that qsort() falling back to my bsort() would be a good solution, 
when qsort() already today sporadically exhibit O(N²) behaviour. How to 
do that clean?

Regarding benchmarks, there is:
https://github.com/hselasky/qsortbench

It's basically a fork of a test-suite for sorting algorithms, having my 
bsort() added on top. There you also have the bad-cases for the 
FreeBSD's qsort().

My bsort() scores pretty OK on average.

> 
> I see some review and the thread below, but adding
> non-standard symbols that are likely to collide with other software[0] to
> libc should be subject to a higher bar than a few people helping you
> improve your patch of saying "that's neat".

> 
> New things added to libc should be in a standard or aligned with one
> (e.g., strlcpy, etc) and anything not from a standard should have
> immediate uses where it improves things in the rest of the system.
> Critically I don't see plans or prototype conversions and I don't see
> benchmarks of real systems (which could easily be done with LD_PRELOAD.

See answer above.

> 
>> Regarding "broader discussion" - what do you mean?
>>
>> The initial discussion was started last September:
>>
>> https://lists.freebsd.org/archives/freebsd-arch/2022-September/000225.html
> 
> More pushback here probably would be been good, sorry.  A heads up
> before the actual commit might have been a good idea. I personally
> find your answer to the question, "why not improve qsort instead?"
> unsatisfactory.  It might be that importing your implementation makes
> sense, but I don't think making is a public symbol we're stuck with
> forever if we ship it in 14 is a good way to go.

My plan was to get a broader audience for the bsort() algorithm, get it 
well tested to iron out any bugs in there, and then I see qsort() could 
fallback to bsort() as a remedy, which would be a great use-case.

Regarding the libc symbol name, I could expand the "b" into "bitonic", 
but it will be like "int" vs "int32_t" to me.

> 
>> And several people have been asked for review and comments. Please
>> elaborate what "broader discussion" means? Do you mean like getting
>> something into ANSI first? I don't get it.
> 
> I'd like more "I'd use it for X" and less "that's neat".

Do I have a commitment and plan from your side to work on this if I back 
the bsort() patch series out? I already see Jessica mentioning some 
memswap() patches, and I guess it is due to ongoing work for Cheri? I 
think we need something like bsort(). If it's not exactly like my 
version, something like that _is_ needed from what I can see.

> 
> -- Brooks
> 
> [0] Debian code search finds fewer collisions than I'd feared, but not
> zero: https://codesearch.debian.net/search?q=%5B%5Ea-z%5Dbsort%5C%28&literal=0

Thanks for checking. I did some research already, and it doesn't look 
that bad.

--HPS