From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11937 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 16:01:10 +0200 Message-ID: <20170916140110.p4xiuzvsuarfcfk4@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> 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 1505570487 13675 195.159.176.226 (16 Sep 2017 14:01:27 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 16 Sep 2017 14:01:27 +0000 (UTC) User-Agent: NeoMutt/20170113 (1.7.2) To: musl@lists.openwall.com Original-X-From: musl-return-11950-gllmg-musl=m.gmane.org@lists.openwall.com Sat Sep 16 16:01:22 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 1dtDer-0003Ol-DH for gllmg-musl@m.gmane.org; Sat, 16 Sep 2017 16:01:21 +0200 Original-Received: (qmail 7311 invoked by uid 550); 16 Sep 2017 14:01:24 -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 7293 invoked from network); 16 Sep 2017 14:01:24 -0000 Content-Disposition: inline In-Reply-To: <20170916093753.GB15263@port70.net> X-Provags-ID: V03:K0:Mpq91OSAKPDJxrctMNJpm/zz6rmCFA6dYvmneWdmx6p54Eii+0n nD37IheOdrOtANVD001Z8jaN62sLrZapyFIepL5+1att/80A0nv9glrM21RTmftezuz3FeU oHZeVli0bk3E9pURvNXlgsststR+AjeioW41xhek6h3w8RWg8KPmUSB4vvWmfZXNzZjrY1G i4WF2dnewSwKObLRf0Tvg== X-UI-Out-Filterresults: notjunk:1;V01:K0:VbdkTXPCf9M=:S9gnz/NMdoE1CHWwPaWiLE fXgLO1YgsBc5tCPtimMYV2Q7YyHTj+sHEQxMgZ8AphNj8jDVtBivWCRM7A5s5VbdlqsRHHwAo 1Fr46WCDAEcV8+LA7Gw20vPs+Xbx37X2L+fLw023VVwCiVwAFYr2f5Rqzg7vCvuf/JEB4oTT3 nk35XjSo8sMLIgnNUq+hUL4713nlWkCbQUp+vFXtZcvqjnIGCxiMYlzadQfL2Ye8t9aX//prM j3XiitLdC45+CoMweWEJcqG/0zN02XCu1mTcwvni8l+heRJ94eh7axCpXnsHmPaT7po6k/dvJ izW7MG1posPZ/B2Yv8NU21AjhjCyDUbLahQ/V+C3uf7/iX/+/b3G9zbhZ6tl26S77qA004UA4 gAIvYnr8g4KNkp/x/YI0SMLYVQojtkWOy/gMUnXpWu6ZmWxlmXxSL6f5z+RS7qmxXDrrGApIy 5a4/WH9keFTwEp+fo+JtiCMEZnti1DDWi/PUxPvayOypCyCM10ojfTivevVr+GivEAUUzHGTk usNFbOiNAkgl88NmHTcocsaViY8OeFFJdG+tQOpapnnJwpqXjmAxGPWkUkpsUFACHRCk+ZACG BBAH7+nI1FIYLg4aH+LinDrkcZONA4NmOoe5RkQouV44PBWgfR5oWDvzLudU7kjO3Z1Wjx8Og Gnl6uZw5kpoomwyZgNJcSyJJcMrKfl+3T6G27VflnMVohYdco9VfkEbfRxJSiBm98+rd9U9yh luGT7pEAht9Ro69aLn+3sPtddjV5St0zImepm5zJXb+8TtPcDqZn/iUFHUFYq4nxumZCmUuT Xref: news.gmane.org gmane.linux.lib.musl.general:11937 Archived-At: On Sat, Sep 16, 2017 at 11:37:53AM +0200, Szabolcs Nagy wrote: > * 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.) > Did you even read what I wrote? Rich talked about big-O, i.e. complexity theory, to which I remarked that most algorithms in use are loglinear and thus equal _in_that_regard_. And I wrote a bit later that the only exception to this that I know of is uclibc, which uses Shell sort with Pratt's sequence. uclibc claimed to be optimized for smaller systems and is thus exactly an example of your second sentence here. And your third point is what I wrote just a few lines further below, albeit with a different example. BTW, in addition to the libcs presented on the libc comparison page, I had a look at newlib and avr-libc, and they both feature quicksort (and at least for avr-libc I can't figure out why they did that. Maybe habit). > > > 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) Agreed. As I said, if you want to know specifics, looking up keywords is not the way to go, anyway, and since all of these libcs are open source, someone wanting to more will have no excuse for not looking up what they want to know in source. It is in the end the only way to be sure. Ciao, Markus