From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/6038 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:27:27 -0500 Message-ID: <20140901182727.GB7301@duality.lan> References: <20140901071243.GA6828@duality.lan> 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="vGgW1X5XWziG23Ko" X-Trace: ger.gmane.org 1409596385 29467 80.91.229.3 (1 Sep 2014 18:33:05 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Sep 2014 18:33:05 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-6045-gllmg-musl=m.gmane.org@lists.openwall.com Mon Sep 01 20:32:59 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 1XOWPS-00068K-Mv for gllmg-musl@plane.gmane.org; Mon, 01 Sep 2014 20:32:58 +0200 Original-Received: (qmail 27933 invoked by uid 550); 1 Sep 2014 18:32:58 -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 27925 invoked from network); 1 Sep 2014 18:32:57 -0000 Content-Disposition: inline In-Reply-To: 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:6038 Archived-At: --vGgW1X5XWziG23Ko Content-Type: text/plain; charset=utf-8 Content-Disposition: inline On Mon, Sep 01, 2014 at 03:25:18PM +0400, Alexander Monakov wrote: > Hi, > > It seems you forgot to commit changes to sorter.h in your repo. Yes, that's fixed now. > > Comparing musl-heapsort to musl-smoothsort, the former appears significantly > better than the latter except on "sorted" input, and even then it's not 20x > faster like the musl commit adding smoothsort claims (about 6.6x for me). It > does reduce the number of comparisons by 20x there, as the commit says. There is one difference between the musl heapsort in my repo compared to what was used in musl, and that's the swap function. The one in musl worked with 3 memcpys in a loop with a 256 byte temporary buffer. When I added it to my test program, I made it use the swap function I'd already written for grailsort/wikisort, which essentially inlines the same concept. That could explain the speed discrepancy. > > There is variation on how divide-and-conquer algorithms in your test handle > sorting on the lowest level; for instance grailsort_ref uses insertion sort > and your implementations use a sorting network (is that correct?). Would your Correct. > comparison be more apples-to-apples if all compared approaches used the same > sorter on the last level, if appropriate (assuming sorting networks improve > performance in some cases)? > > Why did you choose to use sorting networks in your implementations? Primarily because of I've heard Rich say on IRC a few times now that sorting networks are a better choice for small sizes than insertion sort, and I trust his opinion on this sort of thing. It would be interesting to do a more apples to apples comparison. > > For wikisort and grailsort, their "ref" variants perform about 2x faster > on some tests for me . Is that due to last-level sorter choice, or are there > other significant differences? TBH, I haven't spent as much time as I should deciphering everything that's going on in the reference implementations. I suspect that a large part of their complexity comes from optimizing for all sorts of different cases, and even if it does account for a 2x speedup, I don't think we'd want to introduce that much bloat in musl. > > Thanks. > > Alexander > -- Bobby Bingham --vGgW1X5XWziG23Ko Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (GNU/Linux) iQIcBAEBAgAGBQJUBLqPAAoJEFedFv6RmqC9vDwQAIUyEhO/PKKm1jiFh8BeaTd9 HgfmcQWHOhauTG9n7ea9gZfWrG6J6LMvpQR0wbC0MdOzAiZ4vdzGxEkqn5A9C4/W qkrBxW81PSI/F9BcZhYixKHVW+0nYPnJetX58HUt8AbaUhDVxDeEPg7N+ByMg6kr wc2QUQsJyK0neC3pqE3cFBiYuGEWnkWrbg6MyRDQrplu8QAH19EgziYpwlMyd5fA VeiUWf2B0H2SpUVNKZkLxNB+1UkWmeVv+BximW7LH8ezgIgOO1QYd0Z8iBcTglgG JSC1NOZkAy9wl9CZncbK1jyWXjmNUw11jtojMh7z+O65XvMRq62SVRAak4e7SgYc 8alBroVFqFIDvffGinTdXwhnoaYlXsHfqJa/PIFfbJQfK6PpTldibzQi0l1/1pRy N/leA39QxGKNfweUL7HC9dXVPQPTwAAS+THg6J78n1Ivb8DO0upvg5DV4HA88J50 yDEvx7C9AJqHBr0U7L22joh1fcW0NNVelQBdOt3NMuVa6nUEOiYBoTXTJ1nSah0q GFbliFazgPzPkEWFXb1xcYKUqxjYf9q7eRCCo+Zt48M+j3r1fd/P0cSoFCzp6p8J 32bXdU3keHO1Ns8Tv/w5NnSa253rWK2IfaarxHSj9hjyWjrvUi+RiZS07onpfGwd 05Axskd0WgsB9MryrtmA =/dQm -----END PGP SIGNATURE----- --vGgW1X5XWziG23Ko--