From nobody Thu Apr 20 07:25:05 2023 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4Q28Lr5jN3z46RGr; Thu, 20 Apr 2023 07:25:08 +0000 (UTC) (envelope-from hselasky@freebsd.org) Received: from mail.turbocat.net (turbocat.net [88.99.82.50]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4Q28Lr1b8lz3N9Q; Thu, 20 Apr 2023 07:25:08 +0000 (UTC) (envelope-from hselasky@freebsd.org) Authentication-Results: mx1.freebsd.org; none Received: from [10.36.2.154] (unknown [46.212.121.255]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id D7CE82601C7; Thu, 20 Apr 2023 09:25:06 +0200 (CEST) Message-ID: <6253bac6-4c65-ed77-96c9-6a1d9f69e21e@freebsd.org> Date: Thu, 20 Apr 2023 09:25:05 +0200 List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:102.0) Gecko/20100101 Thunderbird/102.10.0 Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm. Content-Language: en-US To: Jessica Clarke Cc: Brooks Davis , src-committers , dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> <3B5734C4-8630-4CD5-BA8D-DE33899161F1@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> <6B7B56C5-52CF-4B1C-A4D2-4D4BE0FE30C7@freebsd.org> From: Hans Petter Selasky In-Reply-To: <6B7B56C5-52CF-4B1C-A4D2-4D4BE0FE30C7@freebsd.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 4Q28Lr1b8lz3N9Q X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:24940, ipnet:88.99.0.0/16, country:DE] X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-ThisMailContainsUnwantedMimeParts: N On 4/20/23 09:12, Jessica Clarke wrote: > On 20 Apr 2023, at 08:08, Hans Petter Selasky wrote: >> On 4/20/23 08:50, Jessica Clarke wrote: >>> On 20 Apr 2023, at 07:26, Hans Petter Selasky wrote: >>>> On 4/20/23 00:31, Jessica Clarke wrote: >>>>> On 19 Apr 2023, at 22:41, Hans Petter Selasky 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. > Hi Jessica, FreeBSD's libc is written in C and not Rust. Please point to something written in C. Probably that malloc() can be on-stack for small sizes in libc's heapsort(). On GitHub : hselasky/qsortbench you can apply this patch: > diff --git a/Makefile b/Makefile > index a0d85e0..634fabc 100644 > --- a/Makefile > +++ b/Makefile > @@ -1,5 +1,5 @@ > -CC := gcc > -CFLAGS = -Ofast -march=native -Wall -Wextra -std=c11 # -Dcheck=1 > +CC := clang # gcc > +CFLAGS = -O3 -march=native -Wall -Wextra -std=c11 # -Dcheck=1 > #CFLAGS = -Os -march=native -Wall -Wextra -std=c11 # -Dcheck=1 > LDFLAGS = -flto > > diff --git a/qsort.c b/qsort.c > index b18a4f9..079fb07 100644 > --- a/qsort.c > +++ b/qsort.c > @@ -175,6 +175,7 @@ int main(int argc, char *argv[]) { > { musl_qsort, "musl" , 0, 0 }, > { diet_qsort, "diet" , 0, 0 }, > { bsort_qsort, "bsort" , 0, 0 }, > + { heapsort, "heapsort", 0, 0 }, > { bsd_qsort, "bsd" , 0, 0 }, > { uclibc_qsort, "uclibc" , 0, 0 }, > { plan9_qsort, "plan9" , 0, 0 }, Then you do "gmake" and run the test-bench: ./qsort 1000000 Comparing heapsort() to bsort() gives the following results: leaderboard 1. illumos 0.998335 1.000000 2. mine 1.013954 1.015645 3. system 1.154811 1.156737 4. glibc 1.033140 1.034864 5. freebsd 1.212156 1.214178 6. plan9 1.503944 1.506453 7. bsd 1.467272 1.469719 8. wada 1.713490 1.716349 9. mini 2.545149 2.549395 10. bsort 2.819615 2.824318 11. linux 2.051919 2.055342 12. musl 3.194471 3.199800 13. diet 2.242223 2.245964 14. uclibc 3.561086 3.567026 15. heapsort 2.879076 2.883879 Our libc's heapsort() is on the bottom. --HPS