[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20140901071243.GA6828@duality.lan>
Date: Mon, 1 Sep 2014 02:12:43 -0500
From: Bobby Bingham <koorogi@...rogi.info>
To: musl@...ts.openwall.com
Subject: [RFC] new qsort implementation
Hi all,
As I mentioned a while back on IRC, I've been looking into wikisort[1]
and grailsort[2] to see if either of them would be a good candidate for
use as musl's qsort.
The C-language reference implementations of both of these algorithms are
inappropriate, as they're both very large, not type-agnostic, and are
not written in idiomatic C. Some of the complexity of both comes from
the fact that they are stable sorts, which qsort is not required to be.
Attached is an implementation of qsort based on a predecessor of the
paper that grailsort is based on, which describes an unstable block
merge sort. The paper is available at [3]. My algorithm deviates a
little bit from what the paper describes, but it should be pretty easy
to follow.
You can find my test program with this algorithm and others at [4].
Some of the implementations included are quicksort variants, so the
"qsort-killer" testcase will trigger quadratic behavior in them. If you
want to run this you should consider reducing the maximum input size in
testcases.h, disabling the qsort-killer input at the bottom of
testcases.c, or disabling the affected sort algorithms ("freebsd",
"glibc quicksort", and depending on your libc, "system") in sorters.c.
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:
random sorted reverse constant sorted+noise reverse+noise qsort-killer elements
compares ms compares ms compares ms compares ms compares ms compares ms compares ms
musl smoothsort 327818 11 19976 0 268152 8 19976 0 142608 5 289637 8 139090 4 10000
4352267 97 199971 2 3327332 59 199971 2 2479200 45 3826143 68 1803634 37 100000
54441776 945 1999963 29 40048748 663 1999963 27 32506944 577 47405848 798 21830972 411 1000000
652805234 12300 19999960 289 465600753 7505 19999960 293 402201458 6891 572755136 9484 259691645 4741 10000000
grailsort 161696 2 71024 0 41110 0 28004 0 143195 1 125943 1 89027 0 10000
1993908 27 753996 2 412840 5 270727 3 1818802 15 1640569 17 1064759 10 100000
23428984 330 7686249 27 4177007 74 2729965 41 21581351 192 19909192 211 12325132 119 1000000
266520949 3884 75927601 277 42751315 901 28243939 436 248048604 2343 232357446 2575 139177031 1368 10000000
As far as code size, here are before and after sizes as reported by
size(1) for bsearch.o, qsort.o, and a minimal statically linked program
using qsort:
before after
bsearch.o 116 160
qsort.o 1550 1242
statictest 2950 2819
At -O2, the before and after sizes show the same basic pattern. At -O3,
gcc performs more aggressive inlining on the grailsort code, and it
balloons to more than twice the size of musl's current code.
For the sake of soft-float targets, I'd also like to look at replacing
the call to sqrt with an integer approximation. But before I go much
further, I'd like to post the code here and get some feedback.
1. https://github.com/BonzaiThePenguin/WikiSort
2. https://github.com/Mrrl/GrailSort
3. http://akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/04/Huang88.pdf
4. http://git.koorogi.info/cgit/qsort_compare/
--
Bobby Bingham
View attachment "bsearch.c" of type "text/x-c" (697 bytes)
View attachment "qsort.c" of type "text/x-c" (4854 bytes)
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.
