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

On 20 Apr 2023, at 08:08, Hans Petter Selasky <hselasky@freebsd.org> wrote:
> On 4/20/23 08:50, Jessica Clarke wrote:
>> On 20 Apr 2023, at 07:26, Hans Petter Selasky <hselasky@freebsd.org> wrote:
>>> On 4/20/23 00:31, Jessica Clarke wrote:
>>>> On 19 Apr 2023, at 22:41, Hans Petter Selasky <hselasky@freebsd.org> wrote:
>>>>> 
>>>>> On 4/19/23 22:17, Jessica Clarke wrote:
>>>>>> pdqsort is n log n time, in-place and doesn’t allocate, and is used,
>>>>>> for example, for Rust’s standard sort_unstable.
>>>>> 
>>>>> Hi Jessica,
>>>>> 
>>>>> Like many many people have tried over the years, to improve the belated QuickSort (*) algorithm since it was invented, by catching bad behaviour and then fallback to other algorithms, pdqsort() is not a solution!
>>>>> 
>>>>> Yes, it is probably "N log N" time, but if you read the code carefully, it falls back to heapsort(), which indeed uses malloc(), which is exactly my point, that I want to avoid.
>>> 
>>> Hi,
>>> 
>>>> Citation needed. This directly contradicts Rust’s documentation:
>>> 
>>> Sure, look at line 448 in there:
>>> 
>>> https://github.com/orlp/pdqsort/blob/master/pdqsort.h#L448
>> That’s not Rust, and that’s also a comment, not a malloc call.
>>>>> This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does not allocate), and O(n * log(n)) worst-case.
>>> 
>>> Unfortunately it can end up allocating memory.
>> Again. Citation needed. Rust’s documentation says otherwise.
> 
> Hi Jessica,
> 
> Here are my citations:
> 
> cd /usr/ports/lang/rust
> make extract
> less work/rustc-1.68.2-src/library/alloc/src/slice.rs
> 
>    /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
>    /// which combines the fast average case of randomized quicksort with the fast worst case of
>    /// heapsort, while achieving linear time on slices with certain patterns. It uses some
>    /// randomization to avoid degenerate cases, but with a fixed seed to always provide
>    /// deterministic behavior.

And? That’s just a comment, it’s not a memory allocation.

> less /usr/src/lib/libc/stdlib/heapsort.c
> 
> The first thing heapsort() does is go and grab memory:
> 
>>        if ((k = malloc(size)) == NULL)
>>                return (-1);

That’s our heapsort. Neither Rust’s nor pdqsort’s calls heapsort(3). So
again, point me at the malloc that you claim is made by either Rust or
pdqsort despite Rust’s own documentation explicitly stating it does not
do that.

This conversation is getting extremely tiresome.

Jess