Skip site navigation (1)Skip section navigation (2)
Date:      Thu, 20 Apr 2023 07:50:42 +0100
From:      Jessica Clarke <jrtc27@freebsd.org>
To:        Hans Petter Selasky <hselasky@freebsd.org>
Cc:        Brooks Davis <brooks@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:  <20CF4C97-7C84-4A4E-984E-E95E406D788C@freebsd.org>
In-Reply-To: <1287e42d-3176-1d20-1c84-9bee0243d933@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> <0E123CCD-C06E-443F-8C3C-AFDC8258CCF6@freebsd.org> <1287e42d-3176-1d20-1c84-9bee0243d933@freebsd.org>

next in thread | previous in thread | raw e-mail | index | archive | help
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:
>>>=20
>>> On 4/19/23 22:17, Jessica Clarke wrote:
>>>> pdqsort is n log n time, in-place and doesn=E2=80=99t allocate, and =
is used,
>>>> for example, for Rust=E2=80=99s standard sort_unstable.
>>>=20
>>> Hi Jessica,
>>>=20
>>> 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!
>>>=20
>>> 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.
>=20
> Hi,
>=20
>> Citation needed. This directly contradicts Rust=E2=80=99s =
documentation:
>=20
> Sure, look at line 448 in there:
>=20
> https://github.com/orlp/pdqsort/blob/master/pdqsort.h#L448

That=E2=80=99s not Rust, and that=E2=80=99s 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.
>=20
> Unfortunately it can end up allocating memory.

Again. Citation needed. Rust=E2=80=99s documentation says otherwise.

Jess

>>> Current implementation
>>> The current algorithm is based on pattern-defeating quicksort 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.
>> -- =
https://doc.rust-lang.org/std/primitive.slice.html#method.sort_unstable
>>> Please come forward with a "N log N" time algorithm which is =
malloc() and alloca() free, and then we'll talk!
>>>=20
>>> And not at least BSD-2-clause licensed and not covered by any =
patents, GPLv2 or whatever!
>> Rust=E2=80=99s meets that and is MIT or Apache 2.0. The original =
pdqsort=E2=80=99s also
>> does and is under the zlib license. I=E2=80=99m not including =
alloca() free,
>> because that=E2=80=99s a nonsense restriction that would forbid any =
local
>> variables.
>=20
> --HPS




Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20CF4C97-7C84-4A4E-984E-E95E406D788C>