Re: benchmarks - sort

[David Bateman]

Alois,

Ok, ignored... In any case I've looked further into the problem over the
weekend and found that the sign issues in IEEE 754 comparison can be treated
more elegantly. Look at the webpage

http://www.stereopsis.com/radix.html

Basically, I've taken his code and rewritten it for doubles, called it
mysort5 (my 5th attempt at getting something faster), and now I get the
benchmarks as follows

octave:2> a=randn(1000000,1); tic; b = mysort5(a); toc
ans = 0.48168

octave:4> a=randn(1000000,1); tic; b = sort(a); toc
ans = 3.4093

and under Matlab R12


I ran the code twice in all cases and took the second result to allow for
issues of dynamically loading the modules, etc

>> a=randn(1000000,1); tic; b = sort(a); toc 

elapsed_time =

    0.5301

So the code I have is basically the same speed as Matlab, correctly
sorts the NaN's and sorts equal values respecting the order as does
Matlab (something I don't believe the current octave code does). I
suspect that they use the same algorithm. The webpage above also
suggests using SSE prefetch instructions to achieve 25% better again,
however I'm not sure I can do that and remain easily compatiable
between platforms.

Now the question becomes one of how to treat the complex sorts. I
could easily sort on the absolute values, but this doesn't respect the
ordering of values with the same magnitude by there phase as matlab
does. What I suspect Matlab does is to convert the complex values to
magnitude and phase with the magnitude being more significant and then
do a radix sort on this.  However, this will be much slower than the
double sort, as I'll have to create 12 histograms and not 6 as at
present, and I'll then have to make 12 passes through the data and not
6 to order the data correctly. Sorting only on the absolute value
without respecting this phase condition should be only twice as slow
as the double sort. This would explain why the sort of complex values
is roughly 20 times slower on Matlab.

Should I aim for exact Matlab compatiability in the sort algorithm, or
"good enough" and lightning fast for the sorting of complex values. It
should be noted that I don't think octave respects this sorting condition
at the moment in any case.

If you want to look at my code, I'll send it seperately, as its not
quite ready for review yet..

Cheers
David








According to Schloegl Alois <address@hidden> (on 01/18/04):
> 
> 
> My previous mail was not ready to go.
> Please, ignore  the last sentence, it was not intended.
> 
> 
> I wanted to conclude that:
> - the algorithm should be of order O(n.log(n))
>     here a different algorithm might be needed
> - and the comparison operator should be as fast and simple as possible
>     here the 2-step approach as outlined in the previous mail could help.
> 
> 
> 
> Alois
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 

-- 
David Bateman                                address@hidden
Motorola CRM                                 +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 1 69 35 77 01 (Fax) 
91193 Gif-Sur-Yvette FRANCE

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary