On Mon, Sep 01, 2014 at 01:17:48PM +0200, Szabolcs Nagy wrote:
> (i had a few build errors: musl_heapsort and musl_smoothsort were not
> declared in sorters.h and glibc needs -lrt for clock_gettime)

Fixed.

>
> 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)

I've reduced the amount of noise locally.  I haven't pushed this change
yet, because when I tried it I found a bug in my grailsort
implementation that I'd like to fix first.

I had taken the merging code I'd written for my wikisort implementation
and tried to adapt it to grailsort, but it looks like I missed a case.
If some (but not all) blocks contain elements with a uniform value, it
is possible for the block merge step to produce the wrong results.

I'm looking at how best to fix this, but the best solution may be to
bring my merge step more in line with that described by the paper.

>
> another common case is sorting two concatenated sorted arrays
> (merge sort should do better in this case)
>

Added.

> 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)

Once I fix the code, I'll work on this analysis.

>
> > 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
>

Interesting.  When I saw that grailsort was faster even with more
comparisons on my machine, I had attributed it to my swap possibly being
faster.  But I don't see why this wouldn't also be the case on i386, so
maybe something else is going on.

> > #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

I thought I recalled hearing that SSIZE_MAX was the upper bound on all
object sizes in musl, but if we still allow larger mmaps than that, I
guess not.  I'll find a different approach when I send the next version
of the code.

--
Bobby Bingham