From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/6039 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: [RFC] new qsort implementation Date: Mon, 1 Sep 2014 16:53:42 -0400 Message-ID: <20140901205342.GE12888@brightrain.aerifal.cx> References: <20140901071243.GA6828@duality.lan> <20140901111748.GD27258@port70.net> <20140901182005.GA7301@duality.lan> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1409604842 32269 80.91.229.3 (1 Sep 2014 20:54:02 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Sep 2014 20:54:02 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-6046-gllmg-musl=m.gmane.org@lists.openwall.com Mon Sep 01 22:53:56 2014 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1XOYbs-0006iK-4R for gllmg-musl@plane.gmane.org; Mon, 01 Sep 2014 22:53:56 +0200 Original-Received: (qmail 28454 invoked by uid 550); 1 Sep 2014 20:53:55 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 28446 invoked from network); 1 Sep 2014 20:53:55 -0000 Content-Disposition: inline In-Reply-To: <20140901182005.GA7301@duality.lan> User-Agent: Mutt/1.5.21 (2010-09-15) Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:6039 Archived-At: On Mon, Sep 01, 2014 at 01:20:05PM -0500, Bobby Bingham wrote: > > > Here are the numbers comparing musl's current smoothsort with the > > > attached grailsort code for various input patterns and sizes. The test > > > was run on x86_64, compiled with gcc 4.8.3 at -Os: > > > > > > sorted reverse constant > > > compares ms compares ms compares ms > > > musl smoothsort 19976 0 268152 8 19976 0 > > > 199971 2 3327332 59 199971 2 > > > 1999963 29 40048748 663 1999963 27 > > > 19999960 289 465600753 7505 19999960 293 > > > > > > grailsort 71024 0 41110 0 28004 0 > > > 753996 2 412840 5 270727 3 > > > 7686249 27 4177007 74 2729965 41 > > > 75927601 277 42751315 901 28243939 436 > > > > > > > interesting that the sorted case is faster with much more compares > > here on i386 smoothsort is faster > > > > sorted reverse constant > > compares ms compares ms compares ms > > musl smoothsort 19976 0 268152 7 19976 1 > > 199971 8 3327332 103 199971 15 > > 1999963 105 40048748 1151 1999963 103 > > 19999960 1087 465600753 13339 19999960 1103 > > > > grailsort 71024 1 41110 3 28004 3 > > 753996 20 412840 23 270727 23 > > 7686249 151 4177007 370 2729965 224 > > 75927601 1438 42751315 4507 28243939 2353 > > > > Interesting. When I saw that grailsort was faster even with more > comparisons on my machine, I had attributed it to my swap possibly being > faster. But I don't see why this wouldn't also be the case on i386, so > maybe something else is going on. I think it makes sense to test with two different types of cases: expensive comparisons (costly compare function) and expensive swaps (large array elements). > > > #include > > > #include > > > > > > size_t __bsearch(const void *key, const void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *)) > > > { > > > size_t baseidx = 0, tryidx; > > > void *try; > > > int sign; > > > > > > while (nel > 0) { > > > tryidx = baseidx + nel/2; > > > try = (char*)base + tryidx*width; > > > sign = cmp(key, try); > > > if (!sign) return tryidx; > > > else if (sign < 0) > > > nel /= 2; > > > else { > > > baseidx = tryidx + 1; > > > nel -= nel/2 + 1; > > > } > > > } > > > > > > return ~baseidx; > > > } > > > > > > void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *)) > > > { > > > size_t idx = __bsearch(key, base, nel, width, cmp); > > > return idx > SSIZE_MAX ? NULL : (char*)base + idx*width; > > > } > > > > musl does not malloc >=SSIZE_MAX memory, but mmap can so baseidx > > may be >0x7fffffff on a 32bit system > > > > i'm not sure if current qsort handles this case > > I thought I recalled hearing that SSIZE_MAX was the upper bound on all > object sizes in musl, but if we still allow larger mmaps than that, I > guess not. I'll find a different approach when I send the next version > of the code. You are correct and nsz is mistaken on this. musl does not permit any object size larger than SSIZE_MAX. mmap and malloc both enforce this. But I'm not sure why you've written bsearch to need this assumption. The bsearch in musl gets by fine without it. Rich