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: AS17314 8.43.84.0/22 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 [8.43.85.97]) (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 590921F8C6 for ; Tue, 7 Sep 2021 00:14:54 +0000 (UTC) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id CE5BE3854819 for ; Tue, 7 Sep 2021 00:14:52 +0000 (GMT) Received: from zimbra.cs.ucla.edu (zimbra.cs.ucla.edu [131.179.128.68]) by sourceware.org (Postfix) with ESMTPS id 5615D3858413 for ; Tue, 7 Sep 2021 00:14:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5615D3858413 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 662DB160111; Mon, 6 Sep 2021 17:14:40 -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 SoWWSxDsVRaE; Mon, 6 Sep 2021 17:14:39 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 8FF7916011C; Mon, 6 Sep 2021 17:14:39 -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 Ni1oG2ggi0vV; Mon, 6 Sep 2021 17:14:39 -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 6783F160111; Mon, 6 Sep 2021 17:14:39 -0700 (PDT) To: Carlos O'Donell References: <20210903171144.952737-1-adhemerval.zanella@linaro.org> <3d2c0890-7a7e-518e-d39e-e3b0df85dd94@cs.ucla.edu> From: Paul Eggert Organization: UCLA Computer Science Department Subject: Re: [PATCH v3 0/7] Use introsort for qsort Message-ID: <54a8f384-dfe4-db41-a09e-2209e0e62478@cs.ucla.edu> Date: Mon, 6 Sep 2021 17:14:39 -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: 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/6/21 7:13 AM, Carlos O'Donell wrote: > All existing ruby implementations I can see use qsort in an > AS-safe-requiring context (process.c) and this would help those scenari= os. I don't see how those scenarios are practical. Assuming glibc and the=20 standard Ruby implementation, any async signal problems could occur only=20 if Ruby's spawn method has more than 32 redirects, as this is the=20 minimum number that would cause qsort to call malloc on practical=20 platforms. In practice Ruby spawns don't have that many redirects, so=20 Ruby programs won't run into a problem unless they're contrived to=20 illustrate this portability bug in the Ruby implementation. > If we want better performance we need to: >=20 > - Add new APIs mirroring what BSD is doing. BSD's APIs are not good, partly because they rely on nonportable C=20 extensions (blocks) that I doubt whether glibc can insist on, partly for=20 other reasons discussed below. An API like what I suggested in my=20 previous email would be better, if we want to add new APIs. > - New APIs explicitly call out the *type* of sort algorithm. "Type" should not mean "heapsort" vs "quicksort" vs "mergesort" as in=20 BSD. Users need performance, async-signal-safety, and stability; the BSD=20 "type" approach is merely a means to that end and any new API should=20 focus on their needs rather than on "type". > we should aim for a good implementation that is as safe as we > can make it (limit memory usage, avoid malloc, avoid quadratic performa= nce > behaviour). If such an approach doesn't significantly hurt typical performance, I'm=20 all for it. I'm skeptical that it's doable, though. Let's not underestimate ordinary users' desires for performance here.=20 qsort is used in other core apps (e.g., Emacs) without running afoul of=20 async-signal-safety bugs. Also, this is not merely about core apps like Emacs and Ruby; it's also=20 about user one-off apps. I often see Glibc qsort in benchmarks, and if=20 the benchmarks results become significantly worse we'll be more likely=20 to scare users away from Glibc and toward other platforms. Unless we can=20 fix the significant performance issues in the proposed patch, the=20 benefit of working around an only-theoretical bug in Ruby's=20 implementation doesn't seem worth this cost.