Date: Mon, 1 Sep 2014 15:25:18 +0400 (MSK) From: Alexander Monakov <amonakov@...ras.ru> To: musl@...ts.openwall.com Subject: Re: [RFC] new qsort implementation 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
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.