Date: Thu, 20 Apr 2023 15:50:01 +0000 From: Brooks Davis <brooks@freebsd.org> To: Hans Petter Selasky <hselasky@freebsd.org> Cc: Colin Percival <cperciva@tarsnap.com>, Jessica Clarke <jrtc27@freebsd.org>, src-committers <src-committers@freebsd.org>, dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm. Message-ID: <ZEFfKfH%2BQPpSu5Up@spindle.one-eyed-alien.net> In-Reply-To: <1ce00b7b-e34b-a91b-59ef-c3ee9683c4a0@freebsd.org> References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> <ZEAM3rO9r5e97BHE@spindle.one-eyed-alien.net> <a073fd36-9aa9-e988-0cc5-86af305fb654@freebsd.org> <3B5734C4-8630-4CD5-BA8D-DE33899161F1@freebsd.org> <e2ea5c89-aa48-e257-b9d5-7fe783bf216e@freebsd.org> <2840BE79-CC25-427A-A5E9-476A38E749E3@freebsd.org> <42d63675-9b1f-70dc-a1da-fef3d43790fd@freebsd.org> <010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000@email.amazonses.com> <1ce00b7b-e34b-a91b-59ef-c3ee9683c4a0@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, Apr 20, 2023 at 08:32:54AM +0200, Hans Petter Selasky wrote: > On 4/20/23 00:28, Colin Percival wrote: > >=20 > > Quicksort with cryptographically randomized pivot selection is O(N^2) w= orst > > case but O(N log N) average-case-for-worst-case-inputs which is good en= ough > > for most purposes. > >=20 > > Quicksort with in-place median-of-medians pivot selection is O(N log N)= =20 > > worst > > case. > >=20 > > Both of them can be easily implemented with O(log N) extra space (for= =20 > > the call > > stack), and with O(1) extra space if you're insane enough to care. >=20 > Yes, I know there are different ways to mitigate O(N^2) behaviour, but=20 > there is not yet after xxx years of research a way to fully mitigate=20 > that behaviour. >=20 > What I think, there should be some statistics done in our qsort() when=20 > it goes to O(N^2), and then it could fallback to bsort() for example, to= =20 > avoid issues with malloc(). >=20 > Or maybe one round of bsort() is enough to make qsort() do its thing=20 > right. I want to investigate that. Like a hybrid. Please perform this investigation out of the tree with without exposing new symbols. For testing there is not need for this to be in libc at all as you can do most testing via LD_PRELOAD replacing qsort. There is certainly room to improve our sort implementations (we've had to replace mergesort entirely in CheriBSD due to it's terrible design that stores unaligned pointers in place of elements) and I encourage work on it, but I see little or no scope for adding more sorts in libc. -- Brooks
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?ZEFfKfH%2BQPpSu5Up>