From nobody Thu Apr 20 17:54:12 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 4Q2QJv2FSbz46N77; Thu, 20 Apr 2023 17:54:23 +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 4Q2QJt6Rkvz43Q0; Thu, 20 Apr 2023 17:54:22 +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 72EE3260492; Thu, 20 Apr 2023 19:54:12 +0200 (CEST) Message-ID: Date: Thu, 20 Apr 2023 19:54:12 +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: bb8e8e230d94 - main - Revert "libc: Implement bsort(3) a bitonic type of sorting algorithm." To: Jessica Clarke Cc: "src-committers@freebsd.org" , "dev-commits-src-all@freebsd.org" , "dev-commits-src-main@freebsd.org" References: <202304201717.33KHHJsQ044448@gitrepo.freebsd.org> <145FD575-5987-4BD8-805D-26DB13EBF06A@freebsd.org> Content-Language: en-US From: Hans Petter Selasky In-Reply-To: <145FD575-5987-4BD8-805D-26DB13EBF06A@freebsd.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 4Q2QJt6Rkvz43Q0 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 19:18, Jessica Clarke wrote: > On 20 Apr 2023, at 18:17, Hans Petter Selasky wrote: >> >> The branch main has been updated by hselasky: >> >> URL: https://cgit.FreeBSD.org/src/commit/?id=bb8e8e230d94c9522bd9ff95c13dc9f5b1592929 >> >> commit bb8e8e230d94c9522bd9ff95c13dc9f5b1592929 >> Author: Hans Petter Selasky >> AuthorDate: 2023-04-20 16:50:32 +0000 >> Commit: Hans Petter Selasky >> CommitDate: 2023-04-20 17:16:14 +0000 >> >> Revert "libc: Implement bsort(3) a bitonic type of sorting algorithm." >> >> Some points for the future: >> - libc is not the right place for sorting algorithms. >> Probably libutil is better suited for this purpose or >> a dedicated libsort. Should move all sorting algorithms >> away from libc eventually. > > qsort is part of ISO C, so no. Hi Jessica, I know, and maybe it shouldn't be part of ISO C in the future. >> - CheriBSD uses capabilities for memory access, and could >> benefit from a standard memswap() function. >> - Do something about qsort() in FreeBSD's libc like: >> - Mark it deprecated on FreeBSD, as a first step, >> due to missing limits on CPU time. > > Nobody’s saying that, quite the opposite. It’s in ISO C. https://en.cppreference.com/w/c/algorithm/qsort Quote: "Despite the name, neither C nor POSIX standards require this function to be implemented using quicksort or make any complexity or stability guarantees." This is the definition of chaos. ISO C says qsort() may be just anything? How can programmers rely on this? > >> - Audit the use of qsort() in the FreeBSD base system >> and consider swapping to other existing sorting >> algorithms. > > No. We’re saying to make the implementation better. Someone interested needs to drive it. And it needs to be agreed what qsort() should really do - why not just call heapsort()? We are still in compliance with ISO C by doing that. Anyway, my time budget on sorting problems is far exceeded, and I would like to suggest a general warning flag __may_be_slow, as appropriate for qsort(). Isn't that just what ISO C says about qsort() ? I've put up a review here for you all: https://reviews.freebsd.org/D39723 --HPS