From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11942 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 21:34:34 +0200 Message-ID: <20170916193434.x7oxm3fusmt46srz@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> <20170916140110.p4xiuzvsuarfcfk4@voyager> <20170916171154.GC15263@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 1505590489 16634 195.159.176.226 (16 Sep 2017 19:34:49 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 16 Sep 2017 19:34:49 +0000 (UTC) User-Agent: NeoMutt/20170113 (1.7.2) To: musl@lists.openwall.com Original-X-From: musl-return-11955-gllmg-musl=m.gmane.org@lists.openwall.com Sat Sep 16 21:34:44 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 1dtIrT-0004Bx-Rm for gllmg-musl@m.gmane.org; Sat, 16 Sep 2017 21:34:43 +0200 Original-Received: (qmail 22134 invoked by uid 550); 16 Sep 2017 19:34:48 -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 22098 invoked from network); 16 Sep 2017 19:34:48 -0000 Content-Disposition: inline In-Reply-To: <20170916171154.GC15263@port70.net> X-Provags-ID: V03:K0:oDY1OpF11TIkWwLFocdj8JGzYBWqLNzpQaXJ6nXZdnnbn1JwUts vLgp0eyhDasbrnafZ9lhg6/Y3VORDIbc0ohag7aEp/VUuxQ+WGGA3Ms2VYCbIsQtZ/PNDSK kKNokTAmwKx18Ev9FIxsPNB34OHAZmomrMHC/pkl76FA+jn15BGNMFsX9rh/1Wy2nDVKujS vtXNeSQmWcDB/ZUeLxEww== X-UI-Out-Filterresults: notjunk:1;V01:K0:9LdnBmEBk4c=:OktHwMBQtigUjMAcjsBUYU 47YDe8J9cx2vCQhGQXk8FVJnjty8vXgr5HKj5P5SARAwE464eJB/N9ER3qHektH+iVuvxoryG 2fq/3sl2duGrp4i5E/jZ3dKOKLeXn+xxIz7wYOe/iLUO4cjhbsLVOyvkbHr0nficY++BZcIMk t5puRmOj/jAhdQrlp+LkF8yykURwQIT7O0GJk+l4AnkEyC5DTUOWi+YUM8QbOzi1MivQ3NlCA GTtnp+yKAIpZQH3gqlDdm7gBfcn0rnhxtgyXD28F7jWU8IrlWMuQGqVhYBjHLPygd/yBDu9g+ C1UpZDdbj4K5qToLaf9fV/Z5oxBS1Vj2UJ0tyqupxUec+x9lQ+yIgy1bk4UVaqI3qjf53xDVh iERwxjrIboL1qOjpaNrjcf94cJ0vyhzNEYlzOpmjKAMjedfg0xLVUytUssgjEE8SQzIgv/ysu xjwiJ76Xw8f9MjeNkeaBMzT4MEaNlOIqCkOJq3GsLSqtNOpqwmfbcz+MMiassgUMGhfW546gN s8d/Zze/vdQFS/YS5hjdlY1QYU4X3h3Qc36cN3jd53ehVHdm0OUyJgwE2cNn03wdz3VNjBDVE 806coLlaUnVAABAiwqZVD2vTruhlcGgRg1pK4ZyKlQyfHTB/sxfufDqL9NUZ+WdVPhJ4oL3A5 v2PaKRp7CHcRIRMnBcwZWbKD/8X12c1YB87qnAyfpF4jodNJBuFOppzl5UQGIsv32ik2F5Yk5 Kc2M5Thd3QbHw1VHMv4x+kwUWL+Xa4zxsEfU4y5P5e7vHndGDgrXCh9WBHBN13awVrz8rGdf Xref: news.gmane.org gmane.linux.lib.musl.general:11942 Archived-At: On Sat, Sep 16, 2017 at 07:11:54PM +0200, Szabolcs Nagy wrote: > glibc, uclibc, dietlibc, newlib, netbsd, openbsd, freebsd > qsort are all O(n^2) worst-case, musl qsort is O(n log(n)). > Yes, sorry, I mixed that up. Quicksort is loglinear only in the average case. Same for Shell sort being O(sqrt(n^3)). > 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.) No, stack usage is not necessarily linear even with quicksort. dietlibc and avr-libc have linear stack usage (with avr-libc always recursing into the first subproblem, and dietlibc always recursing into both subproblems), that's right, but glibc uses a constant amount of stack (automatic allocation of an array to hold the maximum possible number of subproblems, which is equal to the number of bits in a machine word), and newlib uses recursion into the smaller subproblem, thus using a logarithmic amount of stack (functionally constant, since you can give an upper limit). And uclibc also uses a constant amount of stack. Shell sort doesn't need recursion. Ciao, Markus