[ODE] Sweep-and-Prune space for ODE

[Pierre Terdiman]

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

Of course you noticed that Michael's version is not a rank sorter, did you ?

That is, if you use the piece of code on his website "as is", it doesn't
give you anything but a sorted list of floats. This is useless since you
don't have a mapping between this list and the original one.

Now if you rewrote it completely and have something more advanced, we'll be
happy to look at this new version.


>Sorry guys, but I just *have* to ask.  Has anybody done any conclusive
>benchmarks on the radix sorting code?  I remember a while back I did
>some pretty extensive tests and I found that radix sorting was 2x as
>fast as std::sort for integers, but the floating point version (that
>handled signs) was 2.5x slower!

This is a bit surprising since the code is almost the same for both. In
particular when all floating-point values are positive. I'll be interested
to see a small test app reproducing this.


>One thing I don't think that article covers is caching behaviour. On modern
>computers caching behaviour can dominate sorting performance

Yes. And radix sort is not cache-friendly.


>Alas, I never got time to implement that,

What about using the implementation in OPCODE ?


- Pierre