[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 1 Sep 2014 16:53:42 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: [RFC] new qsort implementation
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
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.
