Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm.

On Thu, Apr 20, 2023 at 08:32:54AM +0200, Hans Petter Selasky wrote:
> On 4/20/23 00:28, Colin Percival wrote:
> > 
> > Quicksort with cryptographically randomized pivot selection is O(N^2) worst
> > case but O(N log N) average-case-for-worst-case-inputs which is good enough
> > for most purposes.
> > 
> > Quicksort with in-place median-of-medians pivot selection is O(N log N) 
> > worst
> > case.
> > 
> > Both of them can be easily implemented with O(log N) extra space (for 
> > the call
> > stack), and with O(1) extra space if you're insane enough to care.
> 
> Yes, I know there are different ways to mitigate O(N^2) behaviour, but 
> there is not yet after xxx years of research a way to fully mitigate 
> that behaviour.
> 
> What I think, there should be some statistics done in our qsort() when 
> it goes to O(N^2), and then it could fallback to bsort() for example, to 
> avoid issues with malloc().
> 
> Or maybe one round of bsort() is enough to make qsort() do its thing 
> 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