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.4 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 8DE621F8C6 for ; Mon, 6 Sep 2021 14:13:39 +0000 (UTC) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 86698385AC2F for ; Mon, 6 Sep 2021 14:13:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 86698385AC2F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1630937618; bh=e03vHbz6fZKe2WbhOfbLVyzoHMCr2Jrfxue5wingcow=; 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=FC2mh1JRMjbtX9Kx+bw54i1L3+E2UIqmaCb3HztfKtbYW+KRT48bG0FLd/Pgy+q2N FN6RmUG3kIfG/VtjzuSlD3DNMC7AxQcMncmBU99CoEi+IxOTUCu5Qtn59Cr7KJckt0 pT2z0mHoo93AEl877KJYGwVz2P0xn7mTybXoMPH0= Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id A5FE03858407 for ; Mon, 6 Sep 2021 14:13:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A5FE03858407 Received: from mail-qt1-f197.google.com (mail-qt1-f197.google.com [209.85.160.197]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-391-5FCC1KWGN6yUR_mxERlXnw-1; Mon, 06 Sep 2021 10:13:13 -0400 X-MC-Unique: 5FCC1KWGN6yUR_mxERlXnw-1 Received: by mail-qt1-f197.google.com with SMTP id o22-20020ac872d60000b029029817302575so9291021qtp.10 for ; Mon, 06 Sep 2021 07:13: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:organization :message-id:date:user-agent:mime-version:in-reply-to :content-language:content-transfer-encoding; bh=e03vHbz6fZKe2WbhOfbLVyzoHMCr2Jrfxue5wingcow=; b=GYsqkdBS0W74dEHy7qF6ip/fk19eEXUVH5OXxj7ICLU8Zg6G3V2iHHK+KRUmWsFiQQ qUt4PnFu6BKDwc0aJqXFxbUPbCsaB9xB5sgK9HzQM5vCCFIHTEJRyhcUSzm6rkZRrtaM tBtYGFM6xIQkQqmI/MB6ZT7ET2wZ8SayhRL2Uj79eyR7PtRmCtY3gnhrKoiWiW95Ej7h buVpi3AtjXsX98AXxGZdBEzuMgcUdjw04lLccLsi71JVWRw8Ymq0E0KslcO7JBYmxzbX BeDbCtaYS1PYWgZlyS6HDdIoTMJ9UTTMfvOqDftMJAPm++yP0vM69IbKllLPPOL43vb8 YUtQ== X-Gm-Message-State: AOAM530/xEBPIL1bmN5Zu2jl/AYiTwux5mX0ZTkp1J6OS38GwQs7MH5g 2uAljSPqjsWAJgJmRx5+pv92r0pDo8ienDH+GMx8pJ4dUaNmS/YSQDTEXlqHJjYkL5qlu25HKzW MpKSxNqvsz+Bss1yAlOLVpfcA5cmSQ1Zq/szX5fQNmSoPS71jM0Y3o6ab3v1V1OV5NoQ75A== X-Received: by 2002:a05:6214:c3:: with SMTP id f3mr12129133qvs.1.1630937592647; Mon, 06 Sep 2021 07:13:12 -0700 (PDT) X-Google-Smtp-Source: ABdhPJzBqRotNxvvS211gUsTBPw5M8rmLG5SUtQ1jp9/6yfFGH04H1H082/PJnX2QB1UCW5zY2K0FA== X-Received: by 2002:a05:6214:c3:: with SMTP id f3mr12129067qvs.1.1630937591902; Mon, 06 Sep 2021 07:13:11 -0700 (PDT) Received: from [192.168.1.16] (198-84-214-74.cpe.teksavvy.com. [198.84.214.74]) by smtp.gmail.com with ESMTPSA id s187sm6539194qkf.34.2021.09.06.07.13.10 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 06 Sep 2021 07:13:11 -0700 (PDT) Subject: Re: [PATCH v3 0/7] Use introsort for qsort To: Paul Eggert , Adhemerval Zanella References: <20210903171144.952737-1-adhemerval.zanella@linaro.org> <3d2c0890-7a7e-518e-d39e-e3b0df85dd94@cs.ucla.edu> Organization: Red Hat Message-ID: Date: Mon, 6 Sep 2021 10:13:10 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.11.0 MIME-Version: 1.0 In-Reply-To: <3d2c0890-7a7e-518e-d39e-e3b0df85dd94@cs.ucla.edu> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.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: Carlos O'Donell via Libc-alpha Reply-To: Carlos O'Donell Cc: libc-alpha@sourceware.org Errors-To: libc-alpha-bounces+e=80x24.org@sourceware.org Sender: "Libc-alpha" On 9/3/21 3:18 PM, Paul Eggert wrote: > On 9/3/21 10:11 AM, Adhemerval Zanella wrote: > >> The performance difference with the provided benchmark clearly show >> the tradeoff of using a instrosort over a mergesort. > > Zhang, Meng and Liang report that > introsort is particularly bad with reverse-sorted input; that case > should be added to the benchmarks. It should, and it would be useful, however, I think that Adhemerval's changes to make qsort AS-safe are actually relevant and important. All existing ruby implementations I can see use qsort in an AS-safe-requiring context (process.c) and this would help those scenarios. 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. There is never going to be a qsort that meets all of the workload demands and so we should aim for a good implementation that is as safe as we can make it (limit memory usage, avoid malloc, avoid quadratic performance behaviour). > The proposed change would appear to hurt performance significantly in > the common case of sorting pointers. My guess is that typical glibc > users would prefer speed to hardening against rare signal-handling or > low-memory cases, since portable code will have to assume that qsort > isn't hardened anyway. I disagree. I think users do not expect qsort to be high performance, they expect it to be OK performance, OK memory usage, and lastly safe. My experience with core python developers has been that they expect glibc to provide functions that are safe in as many contexts as possible in order to have them avoid rolling their own for the implementation of the language runtime. Application developers may not care about this AS-safety, but they also have the flexiblity to bring in additional dependencies. We can satisfy those requirements by adding more algorithms under new symbols. > If hardening is a goal, perhaps we should consider an alternate API > instead of changing qsort's implementation. If we do that, we can > improve the API as well as changing the function's name. The new API > could promise to not call malloc, or more generally to be > async-signal-safe if the comparison function is. The comparison > function could take a third void* argument so it can in effect be a > closure (this is qsort's greatest failing), the sorting function > could take a flag argument for options, and it could return an error > indication (in case it detects a comparison function gone haywire, > say). That sort of thing. I'd argue the opposite. Make the current functions safe. Add new high performance versions with explicit algorithms and explicit tradeoffs. >> The improvements over sizes larger than 8 is mostly due the >> optimization done on swap operations. > > A similar optimization could be done to the existing code > independently, no? I expect that an apples-to-apples performance > comparison would be even less favorable to the proposed change. Size is nice, but safety is nicer IMO. -- Cheers, Carlos.