From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on starla X-Spam-Level: X-Spam-Status: No, score=-1.0 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 Received: from server2.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 5F9E91F406 for ; Wed, 6 Dec 2023 12:51:54 +0000 (UTC) Authentication-Results: dcvr.yhbt.net; dkim=pass (2048-bit key; unprotected) header.d=linaro.org header.i=@linaro.org header.a=rsa-sha256 header.s=google header.b=ynl45kuL; dkim-atps=neutral Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5012A3858292 for ; Wed, 6 Dec 2023 12:51:53 +0000 (GMT) Received: from mail-oi1-x229.google.com (mail-oi1-x229.google.com [IPv6:2607:f8b0:4864:20::229]) by sourceware.org (Postfix) with ESMTPS id 263C13858D39 for ; Wed, 6 Dec 2023 12:51:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 263C13858D39 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 263C13858D39 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::229 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701867101; cv=none; b=qc1Pq9UOWQGBA/Qo1VXsc7Y5EfERBhsCgwTwCL6SOAEtTRA8jUqJ5uyIMaIZ+55ibAVMzF6OA/e6tC0Tjp32LSTq7W0ofwEVzsZD3HBtJXdTT3DUerZw/MGxmFeuOJR6sYYu85TjFLRytVLd5PBATsDZ9xWBUxf6yocJDDNCmI4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701867101; c=relaxed/simple; bh=4P7w2JW2gio5O+7WW3rYMnmJHJKRVB55P27tmZew+6w=; h=DKIM-Signature:Message-ID:Date:MIME-Version:Subject:To:From; b=bjFiPAaRHOK7iyhC8bg++gYOzI54k+aU6JKvrgEn4EKWGvHNyd+TraeSxDLC2DSLGrjlZaMMpLHtbhsZMoiTV3K8VtxKdeX0rJejd0+Gz4ZD3Ac84UJkftIUM1uV/Q7qFopKVW/zE8l3l442sFtqDJweEGtqns2EximuzaWtY+Q= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-oi1-x229.google.com with SMTP id 5614622812f47-3b8b80cec8fso2824739b6e.0 for ; Wed, 06 Dec 2023 04:51:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1701867090; x=1702471890; darn=sourceware.org; h=content-transfer-encoding:in-reply-to:organization:from:references :cc:to:content-language:subject:user-agent:mime-version:date :message-id:from:to:cc:subject:date:message-id:reply-to; bh=Sx+R1os4NsMk+iubeDlEGinm69K1mfhxKR9oA4vw50o=; b=ynl45kuLi87WQ6UDgYyndtXREj+yHUidhYDJzQp39rqnVonwG67NpWGGxFO2bn888M gr3ofx4YfclM/mbMlUPk0aIkFr3ElG+zTlHxwJjjT5S8w6z5BxHpgRK49yeNgOBTqVP7 5RrgTxf9XIlZVGwpTiNTep4zrxxtz4rKnUqykfwKKgvkHMCK/e6S9fnqrf7OTehwQhOI cqpgHgG5rUBL/kOAcBx+L+kFE3XVIuI0w7vW3t6qRQQM0QGpAuvz2PbQFf/EG5kZpneN CxkFG7rZWAgnbBGk0XclxzN+N1buz77UH/GYliL2pOMGXOqDuNII0KTOSKuOJH1sQ/xE QGYQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1701867090; x=1702471890; h=content-transfer-encoding:in-reply-to:organization:from:references :cc:to:content-language:subject:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=Sx+R1os4NsMk+iubeDlEGinm69K1mfhxKR9oA4vw50o=; b=a2s77XBL7eHpfsxP4hIZluMhGS+R/tXXZsWReVj5JGkqxP5M+dR+LKMeKKDWwEumqc quhgA7CMbptBqYAdbUJkN61Nf8Y3tZ+KTYn9ug8ckrExo0+A30ivGstbtXWwQjoEkecS hv3QIOUK3Vqwas765PzW1921exlXY7zgVUdr3YTAVhpSrnbD/ddzPyGCsS4FoUKGCi6m 3YHrt0vSp68uH1uAbLafc7UFu7dsi07RbVHe90HT+umuU4wcYY9HJTvsuegvCWqTuVCl ob9sGu/CaLNQTR6u/n+HEtvAq2CiNQnlz2bakUiPki/mymbPV33BIKdUjmdoxtfiJL4L Jdbg== X-Gm-Message-State: AOJu0Yx7MP7kEXosoHw0kEzu5CalDMDRRPC7NBQ0QVewpYmVM2Lxk4CM CWThGqsKIftqCdYADD1uIrEhYkYn+pRtHFW5+pc= X-Google-Smtp-Source: AGHT+IFS7O+7gwKoC6BT/7AlXQqRW36xn4ApM/bI1IFe4TOmlQvcabaBLaDHCM8pEvsRRtr/+NtH2Q== X-Received: by 2002:a05:6808:14ca:b0:3a3:95f9:c99b with SMTP id f10-20020a05680814ca00b003a395f9c99bmr1168187oiw.35.1701867090357; Wed, 06 Dec 2023 04:51:30 -0800 (PST) Received: from ?IPV6:2804:1b3:a7c3:56e1:647c:7ddc:4622:85e4? ([2804:1b3:a7c3:56e1:647c:7ddc:4622:85e4]) by smtp.gmail.com with ESMTPSA id x19-20020a056808145300b003b6caf2accfsm2547208oiv.22.2023.12.06.04.51.28 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 06 Dec 2023 04:51:29 -0800 (PST) Message-ID: <4b7d0325-7c04-458a-8bec-37ca97b62fd7@linaro.org> Date: Wed, 6 Dec 2023 09:51:26 -0300 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH] stdlib: Optimize number of calls to comparison function Content-Language: en-US To: Florian Weimer , Zack Weinberg Cc: Kuan-Wei Chiu , GNU libc development , goldstein.w.n@gmail.com References: <20231202214839.2634493-1-visitorckw@gmail.com> <87y1eaxtst.fsf@oldenburg.str.redhat.com> <87plzjd42s.fsf@oldenburg.str.redhat.com> From: Adhemerval Zanella Netto Organization: Linaro In-Reply-To: <87plzjd42s.fsf@oldenburg.str.redhat.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+e=80x24.org@sourceware.org On 06/12/23 07:21, Florian Weimer wrote: > * Zack Weinberg: > >> On Mon, Dec 4, 2023, at 1:31 PM, Kuan-Wei Chiu wrote: >>> On Mon, Dec 04, 2023 at 09:20:50AM +0100, Florian Weimer wrote: >>>> I think the factor in stdlib/tst-qsort5.c needs to be adjusted: >>>> >>>> /* This is an arbitrary factor which is true for the current >>>> implementation across a wide range of sizes. */ >>>> TEST_VERIFY (factor <= 4.5); >>> >>> It seems that the factor can be adjusted to around 3.5. I can send >>> another patch for this adjustment or resend it as a patch series. >> >> Before you go any further with this patch series I think we need to >> decide whether our backward compatibility constraints mean our qsort >> has to be a stable sort. If so, we should make it *always* be a >> stable sort and write that into the documentation, and that would >> mean junking the entire heapsort implementation. > > That makes sense, although there might not exist an in-place sorting > algorithm that takes constant extra space regardless of element count > and element size and has reasonable performance. Maybe we could say, > “stable if element size is less than 1024 bytes” or something like that. > > What I'm concerned about is that with the current implementation, we > take a performance hit *and* have compatibility problems. The > compatibility problems would be easier to justify if we actually made > things faster. Not calling malloc internally is unlikely to be > compelling to programmers. My initial intention was to remove internal multiple sorting strategies that has different semantics and that might eventually trigger corner cases issues (the stable default mergesort versus the fallback quicksort), and fix the quicksort fallback that had the long standing issue of O(n^2) on adversarial inputs. However it seems that glibc qsort now become an instance on Hyrum's law, where it does not really matter that neither POSIX nor C standard promised sorting stability. So I presume it would be better to keep with mergesort for all input sizes, along with the limited stack buffer (so there is no failure point up a certain input number/size); and fallback to heapsort on memory allocation failure. I will prepare a patch to restore it. Other system does provide mergesort as a different symbol [1], which also returns a failure is case memory can not be allocated. But I don't think it would be an improvement in this situation (no one will really adapt their code to use mergesort if a stable allocation is required). I also though about adding a tunable to enable mergesort on qsort, but it would ending up only add more complexity and required more testing. [1] https://man.freebsd.org/cgi/man.cgi?query=mergesort&sektion=3