From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11936 Path: news.gmane.org!.POSTED!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: Wrong info in libc comparison Date: Sat, 16 Sep 2017 11:37:53 +0200 Message-ID: <20170916093753.GB15263@port70.net> References: <20170913135154.pfwpg7f32nv4dhja@voyager> <20170913181010.GS1627@brightrain.aerifal.cx> <20170913185106.ddbgztckagdojcdd@voyager> <20170913192528.GA15263@port70.net> <20170913195306.GU1627@brightrain.aerifal.cx> <20170915191846.wvjp2x4u4nobhi52@voyager> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: blaine.gmane.org 1505554693 10876 195.159.176.226 (16 Sep 2017 09:38:13 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 16 Sep 2017 09:38:13 +0000 (UTC) User-Agent: Mutt/1.6.0 (2016-04-01) To: musl@lists.openwall.com Original-X-From: musl-return-11949-gllmg-musl=m.gmane.org@lists.openwall.com Sat Sep 16 11:38:05 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 1dt9Y5-0002ca-B9 for gllmg-musl@m.gmane.org; Sat, 16 Sep 2017 11:38:05 +0200 Original-Received: (qmail 24297 invoked by uid 550); 16 Sep 2017 09:38:09 -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 24265 invoked from network); 16 Sep 2017 09:38:07 -0000 Mail-Followup-To: musl@lists.openwall.com Content-Disposition: inline In-Reply-To: <20170915191846.wvjp2x4u4nobhi52@voyager> Xref: news.gmane.org gmane.linux.lib.musl.general:11936 Archived-At: * Markus Wichmann [2017-09-15 21:18:46 +0200]: > On Wed, Sep 13, 2017 at 03:53:06PM -0400, Rich Felker wrote: > > If you're considering big-O, where n->infinity (or at least to the > > largest value that can fit in memory), malloc most certainly has > > failed (because the array to be sorted already filled memory) and > > you're looking at the "fallback" case. > > > > I think we're getting sidetracked here. Every libc worth its salt uses a > loglinear sorting algorithm. Thus they are all equal in that regard. that is not true at all. embedded libcs are often optimized for size, not worst case behaviour. note that worst-case behaviour is not just big-O.. (e.g. glibc uses mergesort which uses malloc which means it's not as-safe, may introduce arbitrary latency since malloc can be interposed, concurrent mallocs can delay forward progress, large allocation may cause swapping, cancellation or longjmp out of the cmp callback can leak memory etc.) > > Maybe the comparison of sort algorithm used is interesting for reasons > > other than just big-O though, in which case mentioning the "merge > > (when it fits in memory)" would probably be helpful. > > > > Rich > > 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)