From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11924 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 14:10:10 -0400 Message-ID: <20170913181010.GS1627@brightrain.aerifal.cx> References: <20170913135154.pfwpg7f32nv4dhja@voyager> 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 1505326226 6229 195.159.176.226 (13 Sep 2017 18:10:26 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 13 Sep 2017 18:10:26 +0000 (UTC) User-Agent: Mutt/1.5.21 (2010-09-15) To: musl@lists.openwall.com Original-X-From: musl-return-11937-gllmg-musl=m.gmane.org@lists.openwall.com Wed Sep 13 20:10:21 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 1dsC7A-0001Tx-P7 for gllmg-musl@m.gmane.org; Wed, 13 Sep 2017 20:10:20 +0200 Original-Received: (qmail 18201 invoked by uid 550); 13 Sep 2017 18:10: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 18177 invoked from network); 13 Sep 2017 18:10:23 -0000 Content-Disposition: inline In-Reply-To: <20170913135154.pfwpg7f32nv4dhja@voyager> Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:11924 Archived-At: On Wed, Sep 13, 2017 at 03:51:54PM +0200, Markus Wichmann wrote: > Hello, > > there's a mistake on the libc comparison page > http://www.etalabs.net/compare_libcs.html: Namely it states that glibc > uses introsort as sorting algorithm. It doesn't. Glibc uses a > bog-standard merge sort as main sorting algorithm. A major part of the > implementation is actually just devoted to optimized copying, and for > arrays of large objects it uses an interesting way to indirectly sort > them (i.e. it then allocates an array of references, sorts the > references, then uses a clever algorithm to get from sorted references > to a sorted array). But it's all just a standard merge sort. > > However, merge sort on arrays requires a linear amount of scratch space, > so this merge sort has to allocate memory. Memory allocation is allowed > to fail, but sorting isn't, so, as a fallback, in case the allocation > fails (or would use more than half the physical memory, for some > reason), it falls back to quicksort. This quicksort is implemented with > a really funky scheme for an explicit stack (i.e., while I'd use > > push_total_problem(); > while (stack_not_empty()) { > pop_subprob(); > if (subprob_worth_bothering_with()) { > sort_partition(); > push_larger_subprob(); > push_smaller_subprob(); > } > } > > they do something more like: > > push_pseudo_problem(); > while (stack_not_empty()) { > if (subprob_worth_bothering_with()) { > sort_partition(); > figure_out_next_subproblem(); > then_maybe_push_or_pop_stuff(); > } > } > > ), a median-of-three pivot selection, two-way partitioning (why couldn't > you be perfect for me?), and a minimum partition size of 4, > necessitating an insertion sort stage afterwards. > > So, yeah, no introsort in sight. Introsort would be merge sort on large > arrays, then quicksort on smaller partitions, and finally insertion sort > for the smallest partitions. 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