From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11940 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 19:11:54 +0200 Message-ID: <20170916171154.GC15263@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> <20170916093753.GB15263@port70.net> <20170916140110.p4xiuzvsuarfcfk4@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 1505581925 7265 195.159.176.226 (16 Sep 2017 17:12:05 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 16 Sep 2017 17:12:05 +0000 (UTC) User-Agent: Mutt/1.6.0 (2016-04-01) To: musl@lists.openwall.com Original-X-From: musl-return-11953-gllmg-musl=m.gmane.org@lists.openwall.com Sat Sep 16 19:12:02 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 1dtGdN-0001jx-Mh for gllmg-musl@m.gmane.org; Sat, 16 Sep 2017 19:12:01 +0200 Original-Received: (qmail 13366 invoked by uid 550); 16 Sep 2017 17:12:06 -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 13344 invoked from network); 16 Sep 2017 17:12:06 -0000 Mail-Followup-To: musl@lists.openwall.com Content-Disposition: inline In-Reply-To: <20170916140110.p4xiuzvsuarfcfk4@voyager> Xref: news.gmane.org gmane.linux.lib.musl.general:11940 Archived-At: * Markus Wichmann [2017-09-16 16:01:10 +0200]: > 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_. > glibc, uclibc, dietlibc, newlib, netbsd, openbsd, freebsd qsort are all O(n^2) worst-case, musl qsort is O(n log(n)). i think this is not a sidetrack, but relevant detail for a libc comparision page. (the openbsd proof of concept stack clash exploit relied on the unbounded stack use in qsort, that would not work against musl, but all the other libcs are affected.)