From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS3215 2.6.0.0/16 X-Spam-Status: No, score=-5.1 required=3.0 tests=AWL,BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,NICE_REPLY_A, RCVD_IN_DNSWL_MED,SPF_HELO_PASS,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (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) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 52FA51F8C8 for ; Tue, 7 Sep 2021 17:40:03 +0000 (UTC) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 440C73857422 for ; Tue, 7 Sep 2021 17:40:02 +0000 (GMT) Received: from zimbra.cs.ucla.edu (zimbra.cs.ucla.edu [131.179.128.68]) by sourceware.org (Postfix) with ESMTPS id 8B383385843B for ; Tue, 7 Sep 2021 17:39:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8B383385843B Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=cs.ucla.edu Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=cs.ucla.edu Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id CD145160076; Tue, 7 Sep 2021 10:39:48 -0700 (PDT) Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id Oumbo7iPCrnu; Tue, 7 Sep 2021 10:39:47 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id C86D11600F1; Tue, 7 Sep 2021 10:39:47 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id PlGJ2ESKnhn8; Tue, 7 Sep 2021 10:39:47 -0700 (PDT) Received: from [192.168.1.9] (cpe-172-91-119-151.socal.res.rr.com [172.91.119.151]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 9FCE7160076; Tue, 7 Sep 2021 10:39:47 -0700 (PDT) To: Adhemerval Zanella , Carlos O'Donell References: <20210903171144.952737-1-adhemerval.zanella@linaro.org> <3d2c0890-7a7e-518e-d39e-e3b0df85dd94@cs.ucla.edu> <54a8f384-dfe4-db41-a09e-2209e0e62478@cs.ucla.edu> <6e9bbf08-4a76-6d33-1319-abda26a19692@linaro.org> From: Paul Eggert Organization: UCLA Computer Science Department Subject: Re: [PATCH v3 0/7] Use introsort for qsort Message-ID: <9d8c44d4-4112-4bfe-0ad8-0504e70665ec@cs.ucla.edu> Date: Tue, 7 Sep 2021 10:39:47 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 In-Reply-To: <6e9bbf08-4a76-6d33-1319-abda26a19692@linaro.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: quoted-printable X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: libc-alpha@sourceware.org Errors-To: libc-alpha-bounces+e=80x24.org@sourceware.org Sender: "Libc-alpha" On 9/7/21 7:32 AM, Adhemerval Zanella wrote: > I consider this a QoI to move toward provide memory bounded and async-s= afe > interfaces This is of course fine for new APIs. However, qsort users are accustomed=20 to the longstanding behavior, and good performance is part of their=20 expectations. > Eventually what might happen when some breakage occurs is users like ru= by > to roll out their own qsort() implementation to fulfill its need. Ruby already has its own qsort implementation. Ruby's portability bug=20 (which occurs only in theory) is that at a delicate point during a fork=20 Ruby uses the system qsort rather than its own qsort. For what it's worth I submitted a patch for this bug=20 . Regardless of whether that=20 patch is accepted, this Ruby example is not a good argument for changing=20 glibc qsort behavior, since the bug is not triggered in practical program= s. > We already have some concession about symbols that are not support to w= ork > in some scenarios (such as malloc() after fork()). Yes, often it make sense to go beyond what the standard requires.=20 However, each case is different needs to be decided on its own merits. > The blocks usage is only for *_b symbols, the BSD do provide default > C compliant mergesort and heapsort. The blocks usage in macOS is essential for doing closures (the=20 equivalent of qsort_r). Since we don't want to require blocks, we need a=20 better API than what macOS supplies for non-qsort. Would you like to work together to come up with a new API that addresses=20 both of our concerns? > I really don't think providing a async-safe with constant worst-case sp= ace > and be *clear* about it will 'scare away' uses, specially because we ar= e > making the interface behaving in a more constraint way which imho is go= od > way forward. Users will roll out their implementation due different ne= eds > and tradeoff, such as gcc or python. If we were creating the qsort implementation for the first time, the=20 async-signal-safety arguments could be compelling. However, it is an=20 entirely different thing to ask a significant number of users to change=20 longstanding uses; this would be more work for them simply because the=20 libc maintainers changed their mind about a particular=20 performance-safety tradeoff. > What I think really upsets users it finding out that if they use a diff= erent > element size or a large number its qsort now starts to call mallocs Users can be upset by many things. They can be upset if qsort calls=20 malloc. They can be upset if qsort is slow. They can be especially upset=20 if we make changes to qsort that force them to rewrite their code. No=20 matter what we do, users can be upset. It's our job to manage these=20 tradeoffs, and to do so in a stable and responsible way.