Date: Mon, 1 Sep 2014 13:27:27 -0500 From: Bobby Bingham <koorogi@...rogi.info> To: musl@...ts.openwall.com Subject: Re: [RFC] new qsort implementation 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 Download attachment "signature.asc" of type "application/pgp-signature" (837 bytes)
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.