From nobody Wed Apr 19 22:31:19 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 4Q1wVy33kdz45JvS for ; Wed, 19 Apr 2023 22:31:22 +0000 (UTC) (envelope-from jrtc27@jrtc27.com) Received: from mail-wr1-f51.google.com (mail-wr1-f51.google.com [209.85.221.51]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "smtp.gmail.com", Issuer "GTS CA 1D4" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4Q1wVy00B7z3Hsd for ; Wed, 19 Apr 2023 22:31:21 +0000 (UTC) (envelope-from jrtc27@jrtc27.com) Authentication-Results: mx1.freebsd.org; none Received: by mail-wr1-f51.google.com with SMTP id ffacd0b85a97d-2eed43bfa4bso121918f8f.2 for ; Wed, 19 Apr 2023 15:31:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681943480; x=1684535480; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=p+6vm2QFIoJXVujiwu4xr7MxRLlWaVj7FPr+YfbNwbM=; b=G71QhXwxp0nMaZ1S9ljN8NavmTfE0rS/xGiH66PXKGs4ekNWPZJe/uI6cFSL4sIon7 zJBB0tvkC58dWiDYoSGSuuPPrWHPLPvTP9tdiaMS4Qkvmy6GRi65R6gEnysNOyQA3W8P Xeuok7OhYC4nFYttIEIPtcuRSHy2AzRfDhlUMxFAHbv2zeiI6SMCiYrDXmTt29EDhtel n361/NrStYWctb8bkD8s9evlL+YOLgGkyga4Y9A3olq2Z2WkEkfpsbaIVuNgXMctp8Dm oqyaBvyHxL/R9JJD3axWXRq/wdXHMB35Y1MnyxVcvbt+3atizCCYd1T1kfhMRvO67co0 YqSw== X-Gm-Message-State: AAQBX9cZfhGXKIk3z7k9KdE+dIdgvjABtzvgeR06TuU8uV8vmc8M72Sd TVBjFEJ8vRsTjcUfAVFHZEhCYg== X-Google-Smtp-Source: AKy350aymeVbEiTZgRPOSwR6ctAf0Hj+3jA1MD86OPqRnfUvroVNHqkFIy4sPkJe+hS6NdWBc73KQA== X-Received: by 2002:adf:d4c7:0:b0:2f6:a7d5:adbe with SMTP id w7-20020adfd4c7000000b002f6a7d5adbemr6128611wrk.37.1681943480407; Wed, 19 Apr 2023 15:31:20 -0700 (PDT) Received: from smtpclient.apple ([131.111.5.246]) by smtp.gmail.com with ESMTPSA id q13-20020adfcd8d000000b002d7a75a2c20sm225694wrj.80.2023.04.19.15.31.19 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Wed, 19 Apr 2023 15:31:20 -0700 (PDT) Content-Type: text/plain; charset=utf-8 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 (Mac OS X Mail 16.0 \(3696.120.41.1.1\)) Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm. From: Jessica Clarke In-Reply-To: <42d63675-9b1f-70dc-a1da-fef3d43790fd@freebsd.org> Date: Wed, 19 Apr 2023 23:31:19 +0100 Cc: Brooks Davis , src-committers , dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org Content-Transfer-Encoding: quoted-printable Message-Id: <0E123CCD-C06E-443F-8C3C-AFDC8258CCF6@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> To: Hans Petter Selasky X-Mailer: Apple Mail (2.3696.120.41.1.1) X-Rspamd-Queue-Id: 4Q1wVy00B7z3Hsd X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:15169, ipnet:209.85.128.0/17, country:US] X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-ThisMailContainsUnwantedMimeParts: N On 19 Apr 2023, at 22:41, Hans Petter Selasky = 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. Citation needed. This directly contradicts Rust=E2=80=99s documentation: > 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 > 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. Jess