From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/6035 Path: news.gmane.org!not-for-mail From: Alexander Monakov Newsgroups: gmane.linux.lib.musl.general Subject: Re: [RFC] new qsort implementation Date: Mon, 1 Sep 2014 15:25:18 +0400 (MSK) Message-ID: References: <20140901071243.GA6828@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 1409570836 28775 80.91.229.3 (1 Sep 2014 11:27:16 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Sep 2014 11:27:16 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-6042-gllmg-musl=m.gmane.org@lists.openwall.com Mon Sep 01 13:27:09 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 1XOPlM-0003uB-CC for gllmg-musl@plane.gmane.org; Mon, 01 Sep 2014 13:27:08 +0200 Original-Received: (qmail 17632 invoked by uid 550); 1 Sep 2014 11:27:07 -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 17624 invoked from network); 1 Sep 2014 11:27:07 -0000 In-Reply-To: <20140901071243.GA6828@duality.lan> User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) Xref: news.gmane.org gmane.linux.lib.musl.general:6035 Archived-At: Hi, It seems you forgot to commit changes to sorter.h in your repo. 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 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 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? 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? Thanks. Alexander