From octave-maintainers-request at bevo dot che dot wisc dot edu Mon Jan 19 09:44:05 2004 Subject: Re: benchmarks - sort From: David Bateman To: Schloegl Alois Cc: David Bateman , Paul Kienzle , octave-maintainers@bevo.che.wisc.edu Date: Mon, 19 Jan 2004 04:40:06 -0600 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 (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 David dot Bateman at motorola dot com 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