From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11941 Path: news.gmane.org!.POSTED!not-for-mail From: Markus Wichmann Newsgroups: gmane.linux.lib.musl.general Subject: Re: Wrong info in libc comparison Date: Sat, 16 Sep 2017 20:38:24 +0200 Message-ID: <20170916183824.6i6m2chfwgyvslzp@voyager> References: <20170913135154.pfwpg7f32nv4dhja@voyager> <20170913181010.GS1627@brightrain.aerifal.cx> <20170913185106.ddbgztckagdojcdd@voyager> <20170913192528.GA15263@port70.net> <20170913195306.GU1627@brightrain.aerifal.cx> <20170915191846.wvjp2x4u4nobhi52@voyager> <20170916093753.GB15263@port70.net> <20170916161802.GY1627@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: blaine.gmane.org 1505587119 12565 195.159.176.226 (16 Sep 2017 18:38:39 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 16 Sep 2017 18:38:39 +0000 (UTC) User-Agent: NeoMutt/20170113 (1.7.2) To: musl@lists.openwall.com Original-X-From: musl-return-11954-gllmg-musl=m.gmane.org@lists.openwall.com Sat Sep 16 20:38:34 2017 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by blaine.gmane.org with smtp (Exim 4.84_2) (envelope-from ) id 1dtHz7-00035g-RY for gllmg-musl@m.gmane.org; Sat, 16 Sep 2017 20:38:33 +0200 Original-Received: (qmail 32289 invoked by uid 550); 16 Sep 2017 18:38:38 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 32268 invoked from network); 16 Sep 2017 18:38:38 -0000 Content-Disposition: inline In-Reply-To: <20170916161802.GY1627@brightrain.aerifal.cx> X-Provags-ID: V03:K0:NBj2vDoAhqSo4Rg546yRXluYoo9WBDj2U0LGZyTZYnTLHqj27Vw +hEuCUV+sjISGjXP1eick/7iHRXa3jPyAeZ9E+KmLLmqAIzzamFsZmdKolb8Vvip2sRA7kc dMMS45eiRA2ctgq9v6sVbNd32BvhC9b9zw0M3EOPxYnFNdfzvCRsYnKa1mOp9Vjxj3ZUD2w gyyRflc3oIQvX+URXlTiQ== X-UI-Out-Filterresults: notjunk:1;V01:K0:BElTluxnqio=:O1T+gfkaI9PW2a1aYNcxQE mnkC6ExQVY7jvx1dASRd7VqPy5eiKtbxnJ/06BkJPBSdVbCCAc4HUia+RvMcD74BFwSQTSCxe 6eSMXfMisKUxrKkgL8qoXaoL7OYiugH1plttZhM5BpKT9LvcbRjsuTM74n1FAf6e2gKtAxYNe fpq0EFAgwt5loHfZ5s9u+2pJbctN4pZUZau81MesZDgaqQBvEvrS2MAlRLqsXhC6eBCkah18f aO6rYLjUuMbdqVQJasdSYcSrQj3mDxqsxM2bmx82s0E99uLwNNwU4XbR/+Ec/6MdJnQWcFl3F Q1ar9Gu+ZcKqyHZeYNuG/IkwHFhzSnPhvI2+8iIb43RiN1FVQzZIbQ9fGOAhdwKYjuAlmjp4Y JSeXmgyr02hRLsFcaz9tplBYalDdiHVwd9bJ8MJuI4OvWWH0VXAqnr/e5rrEvAiRRP+T2GCni 2fUCPH3NRp2HueYYsxIRQmXb6c+mZwlsPw2w9TAH20gcnXZwqovbknk+6vm4NY6Xd0QAJm9pJ oWE3j3ahBpl1IKzSomEdni1WBY1bU1qhwmPnx48AXZ58RkTGrIxOKISJ9GILqwtoiK0E/sv7i eFp/M6f6RdD1v5La1MUF9qBo6x21sCn5xsdUVqVw3rSyD2/klxCjFhrzZzH2USU3yNMuYe2HQ Xm2pqAlqG/TKjNae0zJtw6SmOI9GdJrHi8h1wO9VJzcZiuBVIhMfZ7d530r9XGedqTfNowLRS r1jwtKUxHue03aPjNiQH/1kbrOeY6SubuwqSonR2lmkEqq5Gn+lauzZXB63+H9EctNBMPH30 Xref: news.gmane.org gmane.linux.lib.musl.general:11941 Archived-At: On Sat, Sep 16, 2017 at 12:18:02PM -0400, Rich Felker wrote: > Even non-naive quicksort has O(nē) time; there is a way to avoid this > with an esoteric efficient algorithm for finding the median to use as > the pivot, but nobody does it because the constant is so bad. The only > known practical way to avoid the nē worst-case is some kind of > introsort. So "naive" is really only about the problem of blowing up > the stack. > Oh crap, yes, I forgot about that. Median-of-three only solves the quadratic time problem on sorted inputs but quadratic sequences still exist. My bad. > I agree something like "mergesort+quicksort" sounds good, but just to > make sure, was mergesort already in use in the glibc version in the > comparison? i.e. can I make this fix without inconsistently reflecting > information from different glibc versions? > > Rich Yes, I previously looked at glibc 2.19 and it had the same code. Apparently, the files are really old with only minor changes over the years. At least, that's what I gathered from the changelogs. Ciao, Markus