[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20140901111748.GD27258@port70.net>
Date: Mon, 1 Sep 2014 13:17:48 +0200
From: Szabolcs Nagy <nsz@...t70.net>
To: musl@...ts.openwall.com
Subject: Re: [RFC] new qsort implementation
* Bobby Bingham <koorogi@...rogi.info> [2014-09-01 02:12:43 -0500]:
> 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.
(i had a few build errors: musl_heapsort and musl_smoothsort were not
declared in sorters.h and glibc needs -lrt for clock_gettime)
smooth sort is best for almost sorted lists when only a few elements
are out of order (swap some random elements in a sorted array), this
is common in practice so you should test this case too
the noise case should use much less noise imho (so you test when
only local rearrangements are needed: buffer[i] += random()%small)
another common case is sorting two concatenated sorted arrays
(merge sort should do better in this case)
it would be nice to have a benchmark that is based on common
qsort usage cases
the qsort-killer test is not very interesting for algorithms other
than quicksort (where it is the worst-case), but it would be nice
to analyze the worst cases for smoothsort and grailsort
(they are both O(n logn) so nothing spectacular is expected but it
would be interesting to see how they compare against the theoretical
optimum: ceil(lgamma(n)/log(2)) compares)
> 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:
>
> sorted reverse constant
> compares ms compares ms compares ms
> musl smoothsort 19976 0 268152 8 19976 0
> 199971 2 3327332 59 199971 2
> 1999963 29 40048748 663 1999963 27
> 19999960 289 465600753 7505 19999960 293
>
> grailsort 71024 0 41110 0 28004 0
> 753996 2 412840 5 270727 3
> 7686249 27 4177007 74 2729965 41
> 75927601 277 42751315 901 28243939 436
>
interesting that the sorted case is faster with much more compares
here on i386 smoothsort is faster
sorted reverse constant
compares ms compares ms compares ms
musl smoothsort 19976 0 268152 7 19976 1
199971 8 3327332 103 199971 15
1999963 105 40048748 1151 1999963 103
19999960 1087 465600753 13339 19999960 1103
grailsort 71024 1 41110 3 28004 3
753996 20 412840 23 270727 23
7686249 151 4177007 370 2729965 224
75927601 1438 42751315 4507 28243939 2353
> #include <stdlib.h>
> #include <limits.h>
>
> size_t __bsearch(const void *key, const void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
> {
> size_t baseidx = 0, tryidx;
> void *try;
> int sign;
>
> while (nel > 0) {
> tryidx = baseidx + nel/2;
> try = (char*)base + tryidx*width;
> sign = cmp(key, try);
> if (!sign) return tryidx;
> else if (sign < 0)
> nel /= 2;
> else {
> baseidx = tryidx + 1;
> nel -= nel/2 + 1;
> }
> }
>
> return ~baseidx;
> }
>
> void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
> {
> size_t idx = __bsearch(key, base, nel, width, cmp);
> return idx > SSIZE_MAX ? NULL : (char*)base + idx*width;
> }
musl does not malloc >=SSIZE_MAX memory, but mmap can so baseidx
may be >0x7fffffff on a 32bit system
i'm not sure if current qsort handles this case
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.
