From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11928 Path: news.gmane.org!.POSTED!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: Wrong info in libc comparison Date: Wed, 13 Sep 2017 15:53:06 -0400 Message-ID: <20170913195306.GU1627@brightrain.aerifal.cx> References: <20170913135154.pfwpg7f32nv4dhja@voyager> <20170913181010.GS1627@brightrain.aerifal.cx> <20170913185106.ddbgztckagdojcdd@voyager> <20170913192528.GA15263@port70.net> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: blaine.gmane.org 1505332397 29852 195.159.176.226 (13 Sep 2017 19:53:17 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 13 Sep 2017 19:53:17 +0000 (UTC) User-Agent: Mutt/1.5.21 (2010-09-15) To: musl@lists.openwall.com Original-X-From: musl-return-11941-gllmg-musl=m.gmane.org@lists.openwall.com Wed Sep 13 21:53:14 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 1dsDij-0007f9-WE for gllmg-musl@m.gmane.org; Wed, 13 Sep 2017 21:53:14 +0200 Original-Received: (qmail 12071 invoked by uid 550); 13 Sep 2017 19:53:19 -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 12046 invoked from network); 13 Sep 2017 19:53:18 -0000 Content-Disposition: inline In-Reply-To: <20170913192528.GA15263@port70.net> Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:11928 Archived-At: On Wed, Sep 13, 2017 at 09:25:29PM +0200, Szabolcs Nagy wrote: > * Markus Wichmann [2017-09-13 20:51:06 +0200]: > > 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, > > i think malloc failure case is the one that matters > for worst case analysis so the comparision table > should say whatever quicksort is doing. 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. 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