From nobody Thu Apr 20 07:12:43 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 4Q284Z3x6bz46R3Z for ; Thu, 20 Apr 2023 07:12:46 +0000 (UTC) (envelope-from jrtc27@jrtc27.com) Received: from mail-wm1-f47.google.com (mail-wm1-f47.google.com [209.85.128.47]) (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 4Q284Z1LBqz4WRt for ; Thu, 20 Apr 2023 07:12:46 +0000 (UTC) (envelope-from jrtc27@jrtc27.com) Authentication-Results: mx1.freebsd.org; none Received: by mail-wm1-f47.google.com with SMTP id 5b1f17b1804b1-3f17b967bfbso11510655e9.1 for ; Thu, 20 Apr 2023 00:12:46 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681974765; x=1684566765; 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=tjx11f8b/phbB6LGhFQG74ix4f7aLFd+FA7m5uQ0zZ8=; b=Cu+5VxvcYQ6L7yzCVvCFUPO9GGKRYhUh0bdLkYuU9b5K6OGLYob6JwXXTGgHYxtiGd x/nyX0pCSlh3w4CBCgg8CIQv49iSl8B1yrX3nCyg9jjTJiOIq1er0Kv1emJUsjOWKCBx mK9C2CodqF+pKlqWynHh50jRaJX/mrSxx30KComDLcPfo/S0+jhJ006HHJU6KCLhNps7 TUrJdvvOLlkdSm30RViHBTHzVtexvaC524NwtNOWEawGj5NVCenAOJFhFAhbKYH6Yk4j fwGJn5tZEOginUvjxZFiSnlsIEHV2OOhvi97M5DkDNxdY8QBw2Mfiw97sJTlXttXgjzq dbXA== X-Gm-Message-State: AAQBX9fVHxpt640i2IrFlpdRvmqbj6A5TS75RLP9mz7z31c5ePgYH0ZS r4NaVLEcqkKIqLyS9Ey8lHtlSzFVdExXRmPo5ucEYg== X-Google-Smtp-Source: AKy350ZE0NN9otiyHmuTFjpnTBKA/w0u9beksbu6scUpgH3XWaeWntjljPCB5XFMl1UxnmqGsOMCKw== X-Received: by 2002:adf:f604:0:b0:2cb:29eb:a35e with SMTP id t4-20020adff604000000b002cb29eba35emr3827005wrp.11.1681974764896; Thu, 20 Apr 2023 00:12:44 -0700 (PDT) Received: from smtpclient.apple ([131.111.5.246]) by smtp.gmail.com with ESMTPSA id n3-20020a05600c294300b003f182c11667sm1040606wmd.39.2023.04.20.00.12.44 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Thu, 20 Apr 2023 00:12:44 -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: <2012a30a-ac2c-46cc-eb25-ea8970e6d170@freebsd.org> Date: Thu, 20 Apr 2023 08:12:43 +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: <6B7B56C5-52CF-4B1C-A4D2-4D4BE0FE30C7@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> To: Hans Petter Selasky X-Mailer: Apple Mail (2.3696.120.41.1.1) X-Rspamd-Queue-Id: 4Q284Z1LBqz4WRt 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 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: >>>>>=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. >=20 > Hi Jessica, >=20 > Here are my citations: >=20 > cd /usr/ports/lang/rust > make extract > less work/rustc-1.68.2-src/library/alloc/src/slice.rs >=20 > /// 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=E2=80=99s just a comment, it=E2=80=99s not a memory = allocation. > less /usr/src/lib/libc/stdlib/heapsort.c >=20 > The first thing heapsort() does is go and grab memory: >=20 >> if ((k =3D malloc(size)) =3D=3D NULL) >> return (-1); That=E2=80=99s our heapsort. Neither Rust=E2=80=99s nor pdqsort=E2=80=99s = calls heapsort(3). So again, point me at the malloc that you claim is made by either Rust or pdqsort despite Rust=E2=80=99s own documentation explicitly stating it = does not do that. This conversation is getting extremely tiresome. Jess