sortperm performance still has room to improve

[ViralBShah]

sortperm has poor performance compared to matlab.

julia> y = collect(1000000:-1:1);

julia> @time sortperm(y);
elapsed time: 0.0885950756072998 seconds

>> tic; [ign, p] = sort(y); toc
Elapsed time is 0.030718 seconds.

[edit - updated the issue 1/25/2012 -- ViralBShah]

[ViralBShah]

We are still about 1.7x slower than matlab for plain sorting, and about 3x slower for sortperm

>> y= rand(1000000,1);
>> tic; sort(y); toc
Elapsed time is 0.073307 seconds.

julia> y = rand(1000000);
julia> @time sort(y);
elapsed time: 0.12204194068908691 seconds

[StefanKarpinski]

This is highly dependent on the data size and we seem to be doing asymptotically worse than Matlab on sortperm:

       n    Matlab    Julia  ratio
  100000  0.010252 0.021838  2.130
 1000000  0.108941 0.313423  2.877  
10000000  1.326452 4.901360  3.695

This indicates to me that they may be simply using a better stable sorting algorithm for sortperm. We're using a merge sort, which is very good for general purpose usage, but maybe possible to beat in the very specific case of sorting a dense array of integer indices by using them to index into another auxiliary array.

[StefanKarpinski]

Some numbers for sort and sort!:

        n    Matlab     Julia    Julia!  ratio ratio!
    10000  0.000768  0.000898  0.000874  1.169  1.138
   100000  0.009830  0.012044  0.010627  1.225  1.081
  1000000  0.079106  0.145935  0.128114  1.845  1.620
 10000000  0.827866  1.569710  1.508500  1.896  1.822
100000000 11.607730 18.483200 17.849900  1.592  1.537

[alanedelman]

Also an observation @StefanKarpinski
it seems to me sortperm doesn't return the sorted vector , only the permutation
therefore a true timing comparison vs matlab should compare a julia sort and a sortperm (or did I miss the fact
that sortperm gives me the sort as well?)

[ViralBShah]

sortperm now gives only the permutation, and you have to apply it yourself to get the sorted vector.

[alanedelman]

right so any timing against matlab must have the sorted yourself operation applied

[StefanKarpinski]

Yeah, that's how I was doing it.

[amroamroamro]

for reference, MATLAB uses quicksort: http://www.mathworks.com/support/solutions/en/data/1-15K1B/

[StefanKarpinski]

It would be good to check if we're still slower than Matlab here. I suspect we may have caught up.

[jiahao]

Best of 5 timings

log10n Matlab   Julia!  Julia   ratio!  ratio 
4      0.0007   0.0008  0.0008  1.1512  1.1985
5      0.0053   0.0101  0.0102  1.9105  1.9225
6      0.0748   0.1117  0.1153  1.4935  1.5410
7      0.8640   1.3982  1.3864  1.6183  1.6046
8     11.3690   15.5387 16.3090 1.3668  1.4345

Matlab R2012b, Julia 0.2-rc4 on OSX 10.9