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
