From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from wout1-smtp.messagingengine.com (wout1-smtp.messagingengine.com [64.147.123.24]) by sourceware.org (Postfix) with ESMTPS id ED3CA3858C60 for ; Tue, 5 Dec 2023 20:35:57 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org ED3CA3858C60 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=owlfolio.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=owlfolio.org ARC-Filter: OpenARC Filter v1.0.0 sourceware.org ED3CA3858C60 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=64.147.123.24 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701808559; cv=none; b=QxM9bPO7dfF1RiFj7S4SWpYgE0MmWU30775eLC+goGRxGCcUmLcxayDK728hGzD8fgMD9eZZgahupfXRAnty516o5ZvUhOsyQCA1d6hjFMEsaRlKeJsip9M3HZ9f7BuGA1LYFXdN7yy18vnr0+oiOEO/7R0eD8fERAFlxyyY3kg= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1701808559; c=relaxed/simple; bh=m8JREOX6f+B/izqKJTvBlP7k1x9pr8Sw2NNnlqXDhhk=; h=DKIM-Signature:DKIM-Signature:MIME-Version:Message-Id:Date:From: To:Subject; b=sG86IeHCzkOsj4EbnsCprhPZX9XSyIAUOyX1Y/1lLQn+0pRFMhhngZqm+745OxpaRs9dIZQ05U4Vm4I/edMmZ71DzDh6nHwxUgQKvxrCFXwDp7WNQ1qy6NDvAc48gWuBewt25ot2Afwi3SJyreCHKGlAp6NZPQP0H2nAJ1oH+Lo= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailout.west.internal (Postfix) with ESMTP id 03D4F3200B22; Tue, 5 Dec 2023 15:35:54 -0500 (EST) Received: from imap45 ([10.202.2.95]) by compute5.internal (MEProxy); Tue, 05 Dec 2023 15:35:55 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=owlfolio.org; h= cc:cc:content-type:content-type:date:date:from:from:in-reply-to :in-reply-to:message-id:mime-version:references:reply-to:sender :subject:subject:to:to; s=fm3; t=1701808554; x=1701894954; bh=tS tTAzEs/s9vcx8FTT4S2MpCfOXN8TvkFwwl5AAC0ho=; b=D5q//GDOo+cHeCBzgZ Kxrw5zjLND8ZoKTwmSUTGLrMhNqlvP0jAnJycyMexCuBPej9BpqTWMAziUJ2d3FZ qFlH1fOS1f+1S1dCMpagiu/H/22izFIajAm0bS8AWAB+uu9OGXb6E9vInQSaQRHR 3xkkLzQB/Sa/Grtni5/jOPCHT/A4uqykTKJDs1gTKoo6ex8m0LR7+FkfkMCoiCyT 3IvortfsUPERdlv/fsLsyfzOl6i5r5ZOp0vCiE4CJD7Pd3CW7tWWFR5AGkxCp8LB r909gZMPd7uouvr+MAOSjBs3fAj6ebq4zXj1STnn1N9eu700wymEWkEVMQQwB3sv u/gQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:sender:subject :subject:to:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm1; t=1701808554; x=1701894954; bh=tStTAzEs/s9vc x8FTT4S2MpCfOXN8TvkFwwl5AAC0ho=; b=f/kdbmXNh3twB9g+lQ895SilaUkBd 70BJyaaTeUq2hvLqY0px40/N1dH+Du/S8yqZShx8LA3HzZT2VveAQJ8b5fF2fBct 7OGzmwZl57TRa0LPVY4vnITUrYraHVE4LZB0V6mdNishQh5pqesHFx5z19+DqdQz xu9LBC3vtfEL7JvUTjLE2/Ayuy9tZ7XqVYZj8shYENtiXlVsPv4gZ21KBVr/8q7z FDvjr0adL2lrje4rIGJ6r/glyzoKBpJT1vfH8NHaNvJnUUBP8IivAgNrrEGegc89 xi/JM50z27CtTzSedg81zEQo3SS/oEWL8AU0iiPZsdtWABhdjy/+AzWhQ== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvkedrudejkedgudefkecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpefofgggkfgjfhffhffvvefutgesthdtredtreertdenucfhrhhomhepfdgk rggtkhcuhggvihhnsggvrhhgfdcuoeiirggtkhesohiflhhfohhlihhordhorhhgqeenuc ggtffrrghtthgvrhhnpefhleefheduhfelgeehgeejveehueeihedvgfeuueetteelieei teehfefhleduieenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfh hrohhmpeiirggtkhesohiflhhfohhlihhordhorhhg X-ME-Proxy: Feedback-ID: i876146a2:Fastmail Received: by mailuser.nyi.internal (Postfix, from userid 501) id 31C3A272007B; Tue, 5 Dec 2023 15:35:54 -0500 (EST) X-Mailer: MessagingEngine.com Webmail Interface User-Agent: Cyrus-JMAP/3.9.0-alpha0-1178-geeaf0069a7-fm-20231114.001-geeaf0069 MIME-Version: 1.0 Message-Id: In-Reply-To: References: <20231202214839.2634493-1-visitorckw@gmail.com> <87y1eaxtst.fsf@oldenburg.str.redhat.com> Date: Tue, 05 Dec 2023 15:35:33 -0500 From: "Zack Weinberg" To: "Kuan-Wei Chiu" , "Florian Weimer" Cc: "GNU libc development" , "Adhemerval Zanella" , goldstein.w.n@gmail.com Subject: Re: [PATCH] stdlib: Optimize number of calls to comparison function Content-Type: text/plain X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,JMQ_SPF_NEUTRAL,RCVD_IN_DNSWL_LOW,RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL,SPF_HELO_PASS,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: 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. I do not have a strong opinion either way, but I do think it should either *always* or *never* be stable, i.e. not the previous state of "whether you get a stable sort depends on the size of the input and various other undocumented factors." Also, I think that the behavior should not depend on which version of glibc a program was compiled against. zw