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.3 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 [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 B72C91F8C6 for ; Mon, 6 Sep 2021 18:21:44 +0000 (UTC) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DC871385B83A for ; Mon, 6 Sep 2021 18:21:43 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DC871385B83A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1630952503; bh=ZCWa5ZSg50kU/EFBrUYvPOyWSTI5/1X22bKlGOjOQoE=; h=Subject:To:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=JZxYeOHm+7ymsQA0P/7gxcKTOtJ8jzxRYEpLCT7uK9nTVy0LQ6b8nGY2yVn8lhaVy X8KNB6AlGZcw+ryDnP/31eTQL/3x+U4AGM0wKRvf39uhXVqLvgtZtXXEbMB3R37fCY oB9bVZjcryQNHhlLRgTzVHE8kQ1/ev5cDWx685Wg= Received: from mail-qt1-x82c.google.com (mail-qt1-x82c.google.com [IPv6:2607:f8b0:4864:20::82c]) by sourceware.org (Postfix) with ESMTPS id 323CD385BF9E for ; Mon, 6 Sep 2021 18:19:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 323CD385BF9E Received: by mail-qt1-x82c.google.com with SMTP id s32so6021773qtc.12 for ; Mon, 06 Sep 2021 11:19:31 -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:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=ZCWa5ZSg50kU/EFBrUYvPOyWSTI5/1X22bKlGOjOQoE=; b=JgMoBnwciA7M4dQDGM5axWYFsUop5F16ZuLr8IBYq/9ietXJMttzmBNlqqVcEdRXqr IA+ZyvwYtPfDlYe84strPVbPCSR+O3k93mu735FOPCkZzqxSwvt3DsLfBmsrWmZeAk0l yDCGIwLTNxcXlyEegCua0VcBypJ1d5LTArmLBwKFq8T+xn60IE5ePaOZyHRklkd9anqN jKec9+kqcOL1ku7ffN3xuAi90aa3DQzqHv656pvv65RoZac87AZ1VxEK0OP6FMavZkoI bXhXZFd7BBcrUkFC87yvlzNQkyiZx29chMcggxBGgJOlc2vmDbgjI0QlW2rqsv9uPkJ4 KzXA== X-Gm-Message-State: AOAM533n2f/ITfUmqqPKSoXQ4XBdrdach1rsB5JRx9pWorcSaEtg8AwL TAm2r+cFTyj+JNH6UWaASDFJimgD3Bat7g== X-Google-Smtp-Source: ABdhPJzbfBR1lLcx4iv+VDJPyMaI9ztZMnSFlyNfokJcxzNnFc2cbBzUDSE18xZlJNl7X6tWkLq4gQ== X-Received: by 2002:ac8:5219:: with SMTP id r25mr12406397qtn.282.1630952370737; Mon, 06 Sep 2021 11:19:30 -0700 (PDT) Received: from ?IPv6:2804:431:c7cb:733d:210:e147:8627:2d6? ([2804:431:c7cb:733d:210:e147:8627:2d6]) by smtp.gmail.com with ESMTPSA id s204sm6855508qke.109.2021.09.06.11.19.29 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 06 Sep 2021 11:19:30 -0700 (PDT) Subject: Re: [PATCH v3 0/7] Use introsort for qsort To: libc-alpha@sourceware.org, Zack Weinberg References: <20210903171144.952737-1-adhemerval.zanella@linaro.org> <3d2c0890-7a7e-518e-d39e-e3b0df85dd94@cs.ucla.edu> <6ca95045-a0a6-4d16-8fb9-d06cb9ae961b@www.fastmail.com> Message-ID: <6605ba9b-edd0-65e6-c3ce-69faa64abb3a@linaro.org> Date: Mon, 6 Sep 2021 15:19:28 -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: <6ca95045-a0a6-4d16-8fb9-d06cb9ae961b@www.fastmail.com> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit 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 Errors-To: libc-alpha-bounces+e=80x24.org@sourceware.org Sender: "Libc-alpha" On 06/09/2021 14:03, Zack Weinberg via Libc-alpha wrote: > On Mon, Sep 6, 2021, at 10:13 AM, Carlos O'Donell via Libc-alpha wrote: >> >> In general I think glibc should provide a qsort that is: >> >> - Safe. >> >> - Does not have quadratic performance behaviour. >> >> If we want better performance we need to: >> >> - Add new APIs mirroring what BSD is doing. >> >> - New APIs explicitly call out the *type* of sort algorithm. >> >> - Encourage developers and application authors to contribute those >> new implementations and use them in their applications. > > Do you have a link or other reference for these new APIs being developed by the BSDs? > > (asking out of curiosity; I haven't been following this discussion closely enough to have an opinion) > The FreeBSD provides qsort, which implements a quicksort, heapsort, and mergesort [1]. [1] https://www.freebsd.org/cgi/man.cgi?query=qsort&sektion=3&manpath=freebsd-release