From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11926 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: Wed, 13 Sep 2017 20:51:06 +0200 Message-ID: <20170913185106.ddbgztckagdojcdd@voyager> References: <20170913135154.pfwpg7f32nv4dhja@voyager> <20170913181010.GS1627@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: blaine.gmane.org 1505328698 16898 195.159.176.226 (13 Sep 2017 18:51:38 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 13 Sep 2017 18:51:38 +0000 (UTC) User-Agent: NeoMutt/20170113 (1.7.2) To: musl@lists.openwall.com Original-X-From: musl-return-11939-gllmg-musl=m.gmane.org@lists.openwall.com Wed Sep 13 20:51:32 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 1dsCl2-0004Fe-JE for gllmg-musl@m.gmane.org; Wed, 13 Sep 2017 20:51:32 +0200 Original-Received: (qmail 30474 invoked by uid 550); 13 Sep 2017 18:51:36 -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 30450 invoked from network); 13 Sep 2017 18:51:36 -0000 Content-Disposition: inline In-Reply-To: <20170913181010.GS1627@brightrain.aerifal.cx> X-Provags-ID: V03:K0:vfg82Ws+5zZLioXr2aK6rVai/oCyZ3Kd+jbMSK77s5GJozgNp6X 913DqeUEuPtfDK2Gt+QQ2cnZLgVNVhAycpwlpe8XH/ap5nWO9TCgQMX6ICyCwaE21FVyGVJ 7loxGmZJntEFA7ykRFvK3J+/V496UsWNX+VV4Qyjpq95oUkUCB6fcDihnN8u+HTsnBf+3F+ K6+Fi8hMbonsTCBanxG4g== X-UI-Out-Filterresults: notjunk:1;V01:K0:rZ9/uK1+tU8=:37DdXFQfvsR9U76yippAAj 7g6PVUuBNNEKRtSVt2Gw8mLEpo1FDBgFSpOFWXfN/s0JpTtqNLe9cRmm/PyF3Wj8m1niKD0pi Slesjnn32Sl0IU0M/WjV/68VKv6X85a/Y6MlaaA05ggmLcoCYCdNzj8m7a0gu5PcqzDEI9Bhn ZX2TYZHYk4NrU5/rZ0ZVeztcSH7mvooCu+R/2bVKqqlbQy9mjucOgnv/WbTHl6FIObbtI2Jb+ j34Hgq+yYJe/447HAA/aKyWZrwZPzMEwUVwYZfd7jYjvwUWibuXUboGQr5FplnwRuM4bSDHFa 8nYUoQTPi9VStPdQrfpYrvzZE7ZExIOBGrq9YfmBXB6UAoeabdGUbxY0iSmmoUft78UJGkC0e G12OFhy9mX6+acDZ2fdvhLegK8G1qeTfRf4n9oOtyKdoTZ7qMdR+U1xRleBoCT17Uwj27VMXF /6XNFI83g08utno3xB0aNuM0kRh2E84rE86Lf7ACl+IyFzCi210jhc6M/bq0GkQjTKqLwK2BB fIF1D/wxnYtFmzX7iotnu8ccwPmFZcD0R1oOypewtImFtVKFWoE2gFG0DknL2CgzjMq/ajh4W kQF2xZ1+D7r7cc/+aQkouvX++gXRPMYrAZvnMbOiS6A0RChoJAmTU4oh2wvuSjv73tDXPiIMs u2AeEqxNJy28m0TS8fSMjSEUvKSkYIe8JkbI9NyMEqmDDT7GJmV88SoyZ8EH1c9R2/7j7v1N7 U2DfHfQSa6zDNQZfMs3oWJYNj3E+u2WtfxfTByMiSoKo7mMPY+Zl4hfEH194z3OXGPl6Cg4D Xref: news.gmane.org gmane.linux.lib.musl.general:11926 Archived-At: On Wed, Sep 13, 2017 at 02:10:10PM -0400, Rich Felker wrote: > I'm not sure we agree on what introsort means -- normally I take it to > mean doing an O(nē) algorithm with good "typical case" performance to > begin with, but switching to an O(log n) algorithm with a worse > constant factor as soon as it detects a risk that time will grow > quadratically. Normally this is something like starting with quicksort > and possibly switching to heapsort, and my understanding at the time > was that glibc was doing that or something similar, and AFAIK it still > is in the general case where there's insufficient memory for a merge > sort. Does that sound incorrect? > > Rich At least the version I was looking at (2.19) doesn't do that at all. As I said, even in case of failed malloc(), all it does is a quicksort. With an insertion sort afterwards, but that's not introsort by either of our definitions. And in any case, malloc() failure is rare these days, so the main algorithm is merge sort. I just checked the version Debian is currently distributing (2.24) and saw that nothing major has changed. stdlib/msort.c contains the merge sort algorithm, and stdlib/qsort.c contains the quicksort fallback, for your perusal. Ciao, Markus