From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11922 Path: news.gmane.org!.POSTED!not-for-mail From: Markus Wichmann Newsgroups: gmane.linux.lib.musl.general Subject: Wrong info in libc comparison Date: Wed, 13 Sep 2017 15:51:54 +0200 Message-ID: <20170913135154.pfwpg7f32nv4dhja@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 1505310744 18241 195.159.176.226 (13 Sep 2017 13:52:24 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 13 Sep 2017 13:52:24 +0000 (UTC) User-Agent: NeoMutt/20170113 (1.7.2) To: musl@lists.openwall.com Original-X-From: musl-return-11936-gllmg-musl=m.gmane.org@lists.openwall.com Wed Sep 13 15:52:19 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 1ds85T-0004eZ-FX for gllmg-musl@m.gmane.org; Wed, 13 Sep 2017 15:52:19 +0200 Original-Received: (qmail 15362 invoked by uid 550); 13 Sep 2017 13:52: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 14304 invoked from network); 13 Sep 2017 13:52:24 -0000 Content-Disposition: inline X-Provags-ID: V03:K0:rsXD+Ya3F8EuVFIhNnK9XkgUdcFzsA2fTq3U8Hbwh2cfrSA/16K JQS85b98COQgg7OezRaZaOpHzAvwmaRdLdlLzM2T4jp6N1xXy9LSrwRs33CfHBrfd6UKE4t xQ2kNETeTLALoXf/geBCJXlEFTk0hHOSZ3axdJwpGtOMjQ/Woe3Ni+r+vaAhFdEPv4f1vpC VTfKYwxHZrsMk4N+2bTKg== X-UI-Out-Filterresults: notjunk:1;V01:K0:ShnFSIqmoXM=:E5qpTKeiXFaRxyk4648v2x 3ORV5WncaI9eCjxFezmY0Z4JFpRsBaeoQdV5F0TgeB0JENJSDzc62Zp31xYG+YFcR6imUQcAj YD5cPBDkv3yp8CZPviAO3sNikVnltcQNNK3QW3tpmyv7oESEuNobwwm08Fideq0Y6WCH1kn7X gEzDf+MSgf93zJyWStOjpS6xSOSY3egJyFGhFPf+lejUPUd1pALCmIiNvamgqan+OtN8lQ34q L4vApim8AsQWKeN5AtIGhdowc4ssteqUYMQ+3Vdlf/G65RbzCbNb4X9EHymHd2M7zutFj9sHo bIfzkULHgmAK6NgwMzOHO7hp/Da/T1fjTyH+cWiNyUzwkkdmm34Bq8yMi3icCnR1WV5aTvHs1 zcb5VLsnUDp1soYD91MPmfsAFWDT97S7y4Fn66LMgwahtLBXGA8sFh8vb0OknXl7OTSEtaPiZ R4wIPJxvTzrKZbArTS7FGrl1ByH/mksrgllsNYwrXIZfbyf2fLgMB1RxOKrhQehXBWOLsXTsA UhJa7tFgYnF8IwfAd1baXV/m4NO8nbp2CAT7X5k6sdwa9Rn61m6GQw0kO972nLbmc2nM5dY1B ofbrAj/IjD0qEYhF2TpTHqoSJdC0iujeZGDitSXMmFMcRDBZvjrbZINB/4peA2DnVUO3S1Ll0 KFidCdi3bkm/vgJEe6qQqmBhA0JRdPv+03JJ13JOxLW/F1NaSIgXLIMuZXXLbNBiAmzCMAOuW CEbBsrym2noCzi9E9bbboLJp2LZP5SbT1T7IF56ibUUvu+/qkAMXb7A8GYx3xvXufjoVSnPJ Xref: news.gmane.org gmane.linux.lib.musl.general:11922 Archived-At: 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. Ciao, Markus