Date: Thu, 20 Apr 2023 08:12:43 +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: <6B7B56C5-52CF-4B1C-A4D2-4D4BE0FE30C7@freebsd.org> In-Reply-To: <2012a30a-ac2c-46cc-eb25-ea8970e6d170@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> <20CF4C97-7C84-4A4E-984E-E95E406D788C@freebsd.org> <2012a30a-ac2c-46cc-eb25-ea8970e6d170@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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: >>>>>=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. >=20 > Hi Jessica, >=20 > Here are my citations: >=20 > cd /usr/ports/lang/rust > make extract > less work/rustc-1.68.2-src/library/alloc/src/slice.rs >=20 > /// 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=E2=80=99s just a comment, it=E2=80=99s not a memory = allocation. > less /usr/src/lib/libc/stdlib/heapsort.c >=20 > The first thing heapsort() does is go and grab memory: >=20 >> if ((k =3D malloc(size)) =3D=3D NULL) >> return (-1); That=E2=80=99s our heapsort. Neither Rust=E2=80=99s nor pdqsort=E2=80=99s = calls heapsort(3). So again, point me at the malloc that you claim is made by either Rust or pdqsort despite Rust=E2=80=99s own documentation explicitly stating it = does not do that. This conversation is getting extremely tiresome. Jess
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?6B7B56C5-52CF-4B1C-A4D2-4D4BE0FE30C7>