From nobody Thu Apr 20 06:26:46 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 4Q273b4gTZz46N92; Thu, 20 Apr 2023 06:26:51 +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 4Q273Z1p1gz4P4g; Thu, 20 Apr 2023 06:26:50 +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 6DE502601C7; Thu, 20 Apr 2023 08:26:47 +0200 (CEST) Message-ID: <1287e42d-3176-1d20-1c84-9bee0243d933@freebsd.org> Date: Thu, 20 Apr 2023 08:26:46 +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. 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> Content-Language: en-US From: Hans Petter Selasky In-Reply-To: <0E123CCD-C06E-443F-8C3C-AFDC8258CCF6@freebsd.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 4Q273Z1p1gz4P4g 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 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 >> 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. >> >> 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! >> >> And not at least BSD-2-clause licensed and not covered by any patents, GPLv2 or whatever! > > Rust’s meets that and is MIT or Apache 2.0. The original pdqsort’s also > does and is under the zlib license. I’m not including alloca() free, > because that’s a nonsense restriction that would forbid any local > variables. --HPS