[ODE] Sweep-and-Prune space for ODE

[Graham Fyffe]

Fitting curves to the results gives the following speeds on my poor
little Athlon 1600+:

std::sort:     0.3E-7 n log2 n seconds  (fits like a glove)
stereopsis:  0.32E-8 n^1.1 log2 n seconds  (fits like a glove for >
8,000 elements)

The 1.1 exponent in the stereopsis results is odd, but it's definitely
there.  There's no way I was going to get a strictly n log n result to
fit that thing.  I based this on many tests from 1000 to 50,000,000
elements.  The long and the short of it is that stereopsis is
significantly faster than std::sort for array sizes up to 5 billion. 
Then, based on extrapolation of the really, really straight lines I
got, I estimate they will cross over and std::sort will be king!  Now
if somebody wants to buy me a 64-bit machine with 32 GB of RAM I'll
test it out ;)

Man... there are so many conflicting articles on the net about this topic.

- Graham

On Fri, 26 Nov 2004 09:17:25 -0400, Graham Fyffe <gfyffe at gmail.com> wrote:
> 
> 
> Okay, now THAT is a nice implementation of radix sort.  For floats, it
> is 2.3 times faster than std::sort!  That means it's 5 times faster
> than Pierre's code.  Five.  I would strongly suggest that anyone using
> Pierre's code should switch to the stereopsis code.
> 
> - Graham
> 
> On Fri, 26 Nov 2004 00:21:56 -0000, Simon Barratt
> <barog at pineapple-interactive.com> wrote:
> > I'm not sure about OPCODE's radix sort speed wise but this link might be
> > interesting..
> >
> > http://www.stereopsis.com/
> >
> > It contains a "Radix sort for floating point" page which has some
> > optimisations based on OPCODE's radix sort and claims to get some good
> > speed boosts, it may be doing some floating point tricks which might
> > need #ifdef'ing to not scare some people away.
> >
> > Hope that helps!
> >
> > --
> > Simon Barratt, Lead Developer, Pineapple Interactive Ltd
> > e: barog at pineapple-interactive.com
> > w: www.pineapple-interactive.com
> >
> >
> >
> > -----Original Message-----
> > From: ode-bounces at q12.org [mailto:ode-bounces at q12.org] On Behalf Of
> > Graham Fyffe
> > Sent: Thursday, November 25, 2004 5:13 PM
> > To: Brian Marshall
> > Cc: ode
> > Subject: Re: [ODE] Sweep-and-Prune space for ODE
> >
> > On the subject, I did try several implementations of Radix Sort, and the
> > fastest one for integers was twice as fast as std::sort.  If I took that
> > implementation, and added Pierre's trick for handling signed floats,
> > maybe it would still beat std::sort after all...
> >
> > - Graham
> > _______________________________________________
> >
> >
> > ODE mailing list
> > ODE at q12.org
> > http://q12.org/mailman/listinfo/ode
> >
> >
>