From nobody Thu Apr 20 06:50: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 4Q27b95pkBz46PWT for ; Thu, 20 Apr 2023 06:50:45 +0000 (UTC) (envelope-from jrtc27@jrtc27.com) Received: from mail-wr1-f53.google.com (mail-wr1-f53.google.com [209.85.221.53]) (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 4Q27b92bfbz40Z7 for ; Thu, 20 Apr 2023 06:50:45 +0000 (UTC) (envelope-from jrtc27@jrtc27.com) Authentication-Results: mx1.freebsd.org; none Received: by mail-wr1-f53.google.com with SMTP id ffacd0b85a97d-3010889c6ebso193158f8f.2 for ; Wed, 19 Apr 2023 23:50:45 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681973444; x=1684565444; 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=HlDjRSwfcAkuKvzzpwb/mRA9BopuSKJPfMChSc3hgzA=; b=EiEL2rO0Gde+AaMTar6VN82Y8Jf1x5HSB36kfHvzRDBvQvl5Rr/kH6qAnk2WJNAOqX GjXDrtuOjVbvrqQMnqVcZJcjMOiwzyGnVcUXcam4TksRkBF7G7wlyCgM6+AfQCqD1i7n 7Bl18hi855tR10oRjbI/4VLLGMd3dnKA9mT/K9ZXviY+3AawegqL05zdvJgM4zTFm0ED ZzpvPNJruoKy2D6XcJdxWBanTkAdTjsamAfxQitHeLvboRuH20BAMmipVPD7QU7yq3ML hIInDeTIVX7n+sVih9ueqt/6ympBY+Naww7RmZZTg3gQfkaAQt5UyTZ5HSr7Iv44N5ly cTKg== X-Gm-Message-State: AAQBX9de5ro7Rpfk2ikAl+O6hdYO+sQjruOQ6V7+C7DwRVWyiHDITJ6X h4JmegjnZGVMX/O7nEV+cIb1CQ== X-Google-Smtp-Source: AKy350Zs+nh25fhDgeUnFJ/8QmAnyJNQZE2rgjswa/zq1NUB4YdCY6SDR2GwDg6VeW/G/glX5GdiRQ== X-Received: by 2002:adf:dd85:0:b0:2d1:9c50:5746 with SMTP id x5-20020adfdd85000000b002d19c505746mr358927wrl.12.1681973443791; Wed, 19 Apr 2023 23:50:43 -0700 (PDT) Received: from smtpclient.apple ([131.111.5.246]) by smtp.gmail.com with ESMTPSA id hn3-20020a05600ca38300b003f0ad8d1c69sm4274703wmb.25.2023.04.19.23.50.42 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Wed, 19 Apr 2023 23:50:43 -0700 (PDT) Content-Type: text/plain; charset=utf-8 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 (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: <1287e42d-3176-1d20-1c84-9bee0243d933@freebsd.org> Date: Thu, 20 Apr 2023 07:50:42 +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: <20CF4C97-7C84-4A4E-984E-E95E406D788C@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> To: Hans Petter Selasky X-Mailer: Apple Mail (2.3696.120.41.1.1) X-Rspamd-Queue-Id: 4Q27b92bfbz40Z7 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 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: >>>=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. Jess >>> 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. >=20 > --HPS