From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/6037 Path: news.gmane.org!not-for-mail From: Bobby Bingham Newsgroups: gmane.linux.lib.musl.general Subject: Re: [RFC] new qsort implementation Date: Mon, 1 Sep 2014 13:20:05 -0500 Message-ID: <20140901182005.GA7301@duality.lan> References: <20140901071243.GA6828@duality.lan> <20140901111748.GD27258@port70.net> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="5mCyUwZo2JvN/JJP" X-Trace: ger.gmane.org 1409595947 24709 80.91.229.3 (1 Sep 2014 18:25:47 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Sep 2014 18:25:47 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-6044-gllmg-musl=m.gmane.org@lists.openwall.com Mon Sep 01 20:25:38 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 1XOWIL-0001wF-E3 for gllmg-musl@plane.gmane.org; Mon, 01 Sep 2014 20:25:37 +0200 Original-Received: (qmail 23934 invoked by uid 550); 1 Sep 2014 18:25:36 -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 23926 invoked from network); 1 Sep 2014 18:25:36 -0000 Content-Disposition: inline In-Reply-To: <20140901111748.GD27258@port70.net> X-Operating-System: Linux duality 3.13.5-gentoo User-Agent: Mutt/1.5.22 (2013-10-16) Xref: news.gmane.org gmane.linux.lib.musl.general:6037 Archived-At: --5mCyUwZo2JvN/JJP Content-Type: text/plain; charset=utf-8 Content-Disposition: inline On Mon, Sep 01, 2014 at 01:17:48PM +0200, Szabolcs Nagy wrote: > (i had a few build errors: musl_heapsort and musl_smoothsort were not > declared in sorters.h and glibc needs -lrt for clock_gettime) Fixed. > > smooth sort is best for almost sorted lists when only a few elements > are out of order (swap some random elements in a sorted array), this > is common in practice so you should test this case too > > the noise case should use much less noise imho (so you test when > only local rearrangements are needed: buffer[i] += random()%small) I've reduced the amount of noise locally. I haven't pushed this change yet, because when I tried it I found a bug in my grailsort implementation that I'd like to fix first. I had taken the merging code I'd written for my wikisort implementation and tried to adapt it to grailsort, but it looks like I missed a case. If some (but not all) blocks contain elements with a uniform value, it is possible for the block merge step to produce the wrong results. I'm looking at how best to fix this, but the best solution may be to bring my merge step more in line with that described by the paper. > > another common case is sorting two concatenated sorted arrays > (merge sort should do better in this case) > Added. > it would be nice to have a benchmark that is based on common > qsort usage cases > > the qsort-killer test is not very interesting for algorithms other > than quicksort (where it is the worst-case), but it would be nice > to analyze the worst cases for smoothsort and grailsort > (they are both O(n logn) so nothing spectacular is expected but it > would be interesting to see how they compare against the theoretical > optimum: ceil(lgamma(n)/log(2)) compares) Once I fix the code, I'll work on this analysis. > > > 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. > > #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. -- Bobby Bingham --5mCyUwZo2JvN/JJP Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (GNU/Linux) iQIcBAEBAgAGBQJUBLjVAAoJEFedFv6RmqC953gP/0rMv575EyqyuPlrKUWggozo BKNsJ/T4+W8yRvu167ZwnvP79KkYkK1sznMYlzohiJox2+94+0hU8V6oJj056zCS ven6yCBwhxk5PcP/Axk1m325F1tIm3vcNLAJXCRSFQc2TV7t09cFjf7sem9L5AGg ZdNd7Og6zvB/XvB/rQ4D59AQlzbl2WAaNg/l16s1yO0rSxCMzChNlJlBJNoMcEs0 IavDsOxWKmV+jMnLuMdGW+FlQ9CQt9YDmmGcuHxdd8oU06W4Qv2RjS28epmmoeL1 SiHnBuk7ViIQlzzE018U7ODmXSXu/8Rnvq1eOWbp8rvs1tdV2l1nH+9okWC97CGz stn+GLQKsp+qhyFNxIEVLt/r91ny6Fqj5u8/klswaIJNC//kbwoe5Zm/UOWTjqlW lwuaC6wK6tvv+x8NYSnRbDKxMwDt0IkOsUkZ4KLXFv9EVcElxmurwQd78G6a3LR5 rRSfH8Xo8JDyIbLJSyZaW9G3ILxLtlajsKLmKs1gNlf1hI/efIs6JAAR4dcqZdIL mW5E0UjYF4Cr91l+uo855suR+N5XOhYNhS8EyzvNfO+gbJsN0u54dRof7GRgUmmP DFFzB2meFe5bgqZw+pxSp5VMo7mIl4K/gEKsMyj4M6aOAb+QB4HHWTH6Th003Qbi w/GdlKHqyLzabeRPjMCg =OUDk -----END PGP SIGNATURE----- --5mCyUwZo2JvN/JJP--