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.5 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,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 A6A8B1F8C8 for ; Tue, 7 Sep 2021 18:07:34 +0000 (UTC) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 76664385AC36 for ; Tue, 7 Sep 2021 18:07:33 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 76664385AC36 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1631038053; bh=te4XEZ31tg56aXAUYqmKWgkrsmFylycU9NLbHipGzWc=; h=Subject:To:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=HLVbYi89iMYxxFn+WTs85Pkfg2T3CwRp0Y5S7ld8GTVUDP6AWchVMbGjBJ5PR6yaJ 1OmT/FnvVz2ashf2r67GQD6ZftCO8KWzbw52a9j0jYP7aMP0FxpTpPCSh/Ct9xzUv3 z2JTVyJPr4t5dVAwFXU8cW8jjL7+Kn6QadBBBgVw= Received: from mail-qk1-x735.google.com (mail-qk1-x735.google.com [IPv6:2607:f8b0:4864:20::735]) by sourceware.org (Postfix) with ESMTPS id 924853857C5B for ; Tue, 7 Sep 2021 18:07:13 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 924853857C5B Received: by mail-qk1-x735.google.com with SMTP id w78so11064589qkb.4 for ; Tue, 07 Sep 2021 11:07:13 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=te4XEZ31tg56aXAUYqmKWgkrsmFylycU9NLbHipGzWc=; b=O7fxcUYXG6v6je36Z/BZylhQREP4rbVqzv8KtKfkpeObVWQTIMvGEO6QhPlJ4E7gXh kq8uNhwflriiVlF32xij0ixmNxCvtbf2bFTf0AZXE9agxFM+aN0WTsnDs9987k6HzbnT dEbjGmLMaznaNvarYze3nAMWN3F1PmrrjHklMTj6ibXt/PvnQL9egxXvHlTXxHXOlVw2 dL2ybbdVr7yUi/+i4EQiNKFRw1l5bQg2cKWxEXYKDyMlGrEv4y7BQTxFhlUSRcmFNIqe SsQsS5VmGjxc5GpM36u24wp5Hu5KeaZlNVnrJftXmduS5t59Jb6EZQnZ47duKe0tJGns WADA== X-Gm-Message-State: AOAM533L6MUQIioWZlZg90KwaRT1m2BWjvuQSakj8IINtRB1A1/5hrMQ ouY47OI/k/6NqD6lAJ0bY53A+cDUormPug== X-Google-Smtp-Source: ABdhPJwqMWLBHfCdn2BwA5JkUamtmzMJVXqUveaAqRJEsETESkTfpACR15FcKSVVgqgUd8OkaYG2+Q== X-Received: by 2002:a37:a04e:: with SMTP id j75mr16750127qke.98.1631038032944; Tue, 07 Sep 2021 11:07:12 -0700 (PDT) Received: from ?IPv6:2804:431:c7cb:733d:f360:5bf3:9813:d8f5? ([2804:431:c7cb:733d:f360:5bf3:9813:d8f5]) by smtp.gmail.com with ESMTPSA id v5sm9454870qkh.39.2021.09.07.11.07.11 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 07 Sep 2021 11:07:12 -0700 (PDT) Subject: Re: [PATCH v3 0/7] Use introsort for qsort To: Paul Eggert , 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> <9d8c44d4-4112-4bfe-0ad8-0504e70665ec@cs.ucla.edu> Message-ID: <1a79a7d6-fdaf-c046-d5bf-28fa765df125@linaro.org> Date: Tue, 7 Sep 2021 15:07:10 -0300 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: <9d8c44d4-4112-4bfe-0ad8-0504e70665ec@cs.ucla.edu> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit 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: , From: Adhemerval Zanella via Libc-alpha Reply-To: Adhemerval Zanella Cc: libc-alpha@sourceware.org Errors-To: libc-alpha-bounces+e=80x24.org@sourceware.org Sender: "Libc-alpha" On 07/09/2021 14:39, Paul Eggert wrote: > On 9/7/21 7:32 AM, Adhemerval Zanella wrote: > >> I consider this a QoI to move toward provide memory bounded and async-safe >> interfaces > > This is of course fine for new APIs. However, qsort users are accustomed to the longstanding behavior, and good performance is part of their expectations. > > >> Eventually what might happen when some breakage occurs is users like ruby >> to roll out their own qsort() implementation to fulfill its need. > > Ruby already has its own qsort implementation. Ruby's portability bug (which occurs only in theory) is that at a delicate point during a fork Ruby uses the system qsort rather than its own qsort. > > For what it's worth I submitted a patch for this bug . Regardless of whether that patch is accepted, this Ruby example is not a good argument for changing glibc qsort behavior, since the bug is not triggered in practical programs. I disagree, and stating: "This is not a practical problem with glibc, since glibc qsort is async-signal-safe with small sorts and in practice Ruby's use of qsort is invariably small enough" is even more problematic because it states that we are providing async-safeness depending of the input arguments (which is really a bad interface). And your fix is exactly what is not the really intended: user need to roll out ad-hoc sorting implementation to handle libc limitations. > > >> We already have some concession about symbols that are not support to work >> in some scenarios (such as malloc() after fork()). > > Yes, often it make sense to go beyond what the standard requires. 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 equivalent of qsort_r). Since we don't want to require blocks, we need a better API than what macOS supplies for non-qsort. > My point is blocks neither closures are essential to provide different sort algorithms with different strategies and constraints. > Would you like to work together to come up with a new API that addresses both of our concerns? I am not against your suggestion, but I think this is orthogonal to providing a better semantic and guarantees to the current qsort. > > >> I really don't think providing a async-safe with constant worst-case space >> and be *clear* about it will 'scare away' uses, specially because we are >> making the interface behaving in a more constraint way which imho is good >> way forward.  Users will roll out their implementation due different needs >> and tradeoff, such as gcc or python. > > If we were creating the qsort implementation for the first time, the async-signal-safety arguments could be compelling. However, it is an entirely different thing to ask a significant number of users to change longstanding uses; this would be more work for them simply because the libc maintainers changed their mind about a particular performance-safety tradeoff. > > >> What I think really upsets users it finding out that if they use a different >> 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 malloc. They can be upset if qsort is slow. They can be especially upset if we make changes to qsort that force them to rewrite their code. No matter what we do, users can be upset. It's our job to manage these tradeoffs, and to do so in a stable and responsible way. I agree that performance degradation is really a potential problem, that's why I used an known algorithm used as a default sort algorithm for different library (stdlibc++). And I tend to see async-signal-safeness, along with bounded memory utilization and simple algorithm a better move forward to *the system C library* than providing the state of the art sort algorithm. >From my experience we have much more bug report in the are of broken semantic than from missing performance. As before, users will most likely move to other sorting algorithm if qsort is a hotspot. And if performance is paramount we can either provide it as an alternative API as you suggest or thought a tunable.