Re: [RFC] new qsort implementation

[Rich Felker <dalias@libc.org>]

On Mon, Sep 01, 2014 at 01:20:05PM -0500, Bobby Bingham wrote:
> > > 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.

I think it makes sense to test with two different types of cases:
expensive comparisons (costly compare function) and expensive swaps
(large array elements).

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

You are correct and nsz is mistaken on this. musl does not permit any
object size larger than SSIZE_MAX. mmap and malloc both enforce this.
But I'm not sure why you've written bsearch to need this assumption.
The bsearch in musl gets by fine without it.

Rich