From nobody Thu Apr 20 07:08:42 2023 X-Original-To: dev-commits-src-all@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 4Q27zw2BGFz46QlB; Thu, 20 Apr 2023 07:08:44 +0000 (UTC) (envelope-from hselasky@freebsd.org) Received: from mail.turbocat.net (turbocat.net [IPv6:2a01:4f8:c17:6c4b::2]) (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 4Q27zw0ZMnz4QP9; Thu, 20 Apr 2023 07:08:44 +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) server-digest SHA256) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id BBC2B2602D4; Thu, 20 Apr 2023 09:08:42 +0200 (CEST) Message-ID: <2012a30a-ac2c-46cc-eb25-ea8970e6d170@freebsd.org> Date: Thu, 20 Apr 2023 09:08:42 +0200 List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@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> From: Hans Petter Selasky In-Reply-To: <20CF4C97-7C84-4A4E-984E-E95E406D788C@freebsd.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 4Q27zw0ZMnz4QP9 X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:24940, ipnet:2a01:4f8::/32, 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 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. 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); --HPS