From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11939 Path: news.gmane.org!.POSTED!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: Wrong info in libc comparison Date: Sat, 16 Sep 2017 12:18:02 -0400 Message-ID: <20170916161802.GY1627@brightrain.aerifal.cx> 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> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: blaine.gmane.org 1505578695 19913 195.159.176.226 (16 Sep 2017 16:18:15 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 16 Sep 2017 16:18:15 +0000 (UTC) User-Agent: Mutt/1.5.21 (2010-09-15) To: musl@lists.openwall.com Original-X-From: musl-return-11952-gllmg-musl=m.gmane.org@lists.openwall.com Sat Sep 16 18:18:12 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 1dtFnH-00052b-6W for gllmg-musl@m.gmane.org; Sat, 16 Sep 2017 18:18:11 +0200 Original-Received: (qmail 15413 invoked by uid 550); 16 Sep 2017 16:18:15 -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 15395 invoked from network); 16 Sep 2017 16:18:14 -0000 Content-Disposition: inline In-Reply-To: <20170916093753.GB15263@port70.net> Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:11939 Archived-At: On Sat, Sep 16, 2017 at 11:37:53AM +0200, Szabolcs Nagy wrote: > > Algorithms can be compared on a number of metrics, and just the name > > doesn't tell us much (e.g. quicksort with naive "first element" pivot > > selection has a pathological case on sorted input, while quicksort with > > med3 pivot selection handles that very well). If you really want to know > > something specific, you'll have to look it up in source, anyway. > > "mergesort+quicksort" sounds good to me, > it tells enough about what's going on, if there is some > known implementation mistake that can be added to the > description (like "naive" quicksort for dietlibc implying > O(n^2) worst case compares and potentially large stack use) 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. 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