How long does sortrows take to execute and are there any faster alternatives ?

I am running a long simulation that produces a large table of almost 18 million rows and 70 columns.

That part of the simulation has completed; the last part consists in sorting the table in ascending order with regard to the content of the 66th column of the table. For this I use the code :

    order = sortrows(Table, 66) ;

where Table is a 18million x 70 array. Generating Table took approximately 12 hours. I expected sorting it wouln't take long, but the program has been running for nearly 13 hours now to sort the table.

Is this normal ? How much longer should I expect to wait ? Am I doing something wrong ? Should I stop the simulation and try it again ? Are there any faster alternatives to sortrows, and if yes how should I implement them ?

Thanks for any help!

PS: I am using a Mac (oct. 2011) with an Intel i5 1.7GHz dual core processor, 4GB RAM and flash SSD storage.

Answer 1

[Matt J]

For the case of sorting w.r.t only 1 column, the following approach is faster than SORTROWS on my machine

 [~,idx]=sort(Table(:,66));
 order=Table(idx,:);

However, I don't really understand what you're doing to fit this data in memory. It doesn't seem like you're using RAM alone, and that could be part of what's slowing things down. The data is 10 GB if you're using type double, and that's just for the table itself, not its sorted copy. If you're using uint16, the total data (pre-sorted plus sorted) will still run over 4 GB. Are you using uint8, then?

[Walter Roberson]

The situation is not as bad as it could be as the external memory is SSD instead of hard drive.

Answer 2

[Jan]

Sorting a vector of of size [18e6 x 1] takes less than 4 seconds, and sortrows does not do anything else. If your computer struggles for hours, it either is stuck in another command, or your memory is exhausted by the very large matrix such that slow disk caching wastes the time. Even with a SSD this is slow.

Either buy more RAM. Or split the large matrix to smaller parts. E.g. a cell array allows to store the columns separately, such that the memory is not required as a single contiguous block. But, let me repeat myself, buying more RAM is essential, when you process large problems.

[Walter Roberson]

4 GB of RAM plus an SSD drive and an i5 @ 1.7 Ghz, implies a MacBook Air 13" display with soldered-in RAM that is not upgradable except by changing the entire logic board. :(

[Matt J]

Sorting a vector of of size [18e6 x 1] takes less than 4 seconds, and sortrows does not do anything else.

Based on my experiments below, this doesn't seem to be true, though I'm not entirely sure why

    x=rand(18e6,7);

    tic;
      [~,idx]=sort(x(:,1)); 
      y=x(idx,:);   
    toc
    %Elapsed time is 3.589928 seconds.

     tic; 
      y=sortrows(x,1);
     toc
     %Elapsed time is 14.869106 seconds.

[Walter Roberson]

sortrows() is a .m file whose source can be examined. The case of real, non-sparse, 4 or more elements per row, is handled by a mex file sortrowsc(). No idea what that file does.

[Jan]

The source file sortrowsc.c was shipped with R2009a. See http://www.mathworks.com/matlabcentral/answers/57629-why-does-sort-outperform-sortrows.

Answer 3

[per isakson]

Speculation:

• write the 10GB array to a binary file; use fwrite
• clear all
• open the file with memmapfile. Let the name of the object be mmf
• read the 66th column to col66
• sort

      [~,ix_order] = sort( col66 );

• use ix_order to retrieve data from the array, Table

    data_of_interest = mmf.Table( ix_order(range_of_interest), : );

.

Worth trying?

.

Questions:

• The "large table of almost 18 million rows and 70 columns" is that stored in a file?
• If so, what type of file?

.

An experiment:

• R2012a, 64bit, Win7 and a three years old vanilla PC with 8GB ram and a spinning HD.

This experiment follows the approach outlined above.

    function    memmapfile_huge()
        filespec = 'c:\temp\huge.dat';
    %%Allocate space on HD
    tic    
        M = zeros( 1e6, 70 );
        fid = fopen( filespec, 'a' );
        for ii = 1 : 18
           fwrite( fid, M, 'double' )
        end
        fcose( fid );
    toc    
    %%Create a memmap object
        mmf = memmapfile( filespec                          ...          
            ,   'Format', { 'double', [ 18e6, 70 ], 'x' }   ... 
            ,   'Writable', true                            );

    %%Write data to the file on the HD
    tic
        M = rand( 1e6, 70 );
        for ii = 1 : 18
           mmf.Data.x( 1+(ii-1)*1e6 : ii*1e6, : ) = M + ii;
           fprintf( 'loop %02u done at %s\n', ii, datestr( now, 31 ) )
        end
    toc
    % loop 02 done at ...:00:03
    % loop 03 done at ...:00:11
    % loop 04 done at ...:00:19
    % loop 05 done at ...:00:28
    % ...
    % loop 15 done at ...:04:09
    % loop 16 done at ...:04:34
    % loop 17 done at ...:05:04
    % loop 18 done at ...:05:44
    % Elapsed time is 343.496356 seconds.

    %%Sort on column 66. Second time the data is in system cache.
    tic
        [ ~, ixs ] = sort( mmf.Data.x( :, 66 ) );
    toc
    % Elapsed time is 27.278279 seconds. column 66 first time
    % Elapsed time is 1.845525 seconds.  column 66 with data in system cache  
    % Elapsed time is 3.202180 seconds.  column 1  first time 
    % Elapsed time is 2.894059 seconds.  column 30 first time   
    %    
    %%Reading four rows from different parts of the file   
    tic
        X = mmf.Data.x( ixs( 10e6:10e6+3 ), : );
    toc
    % Elapsed time is 0.267950 seconds.
    % Elapsed time is 0.950517 seconds. Different parts of the file. 
    end

and

    >> tic,  mmf.Data.x( :, 26 ); toc
    Elapsed time is 2.011522 seconds.

.

Discussion:

Timing when the system cache is involved is tricky - or rather to understand the results. To clear the system cache I need to restart Windows.

[Me]

The large table is created by my m-file and the same program directly sorts it (well, it's supposed to).

Thank you all for your answers ; I stopped my simulation because it was taking far too long. I think I will try it on my university's server which shouldn't have any memory problems.

[per isakson]

I guess that there was a lot of swapping between RAM and HD. That rather than anything else takes time.

To learn whether it is the simulation itself or the shuffling of data that takes time make an experiment without saving the simulation result.

If the simulation itself is fast enough, I think you should give memmapfile a try. You have a SSD, but only 4GB. Make an experiment and keep an eye on the memory use as shown by the Windows Task Manager (i.e Apples corresponding tool).

See above the results from my experiment with memmapfile.

Answer 4

[Walter Roberson]

sortrows() uses a decently fast algorithm. It is not the fastest known sorting algorithm (I believe), but the fastest known sorting algorithm is fairly tricky to program and is often slower than a "decently fast" algorithm.

When "fastest algorithm" is being talked about, what is being discussed is the the theoretical behavior on sufficiently large datasets when there are enough computing resources (including memory). "fastest" might not have any advantages until you are sorting peta-entry datasets with exabytes of scratch memory.

In your situation, you are trying to sort without having enough RAM to use sort() efficiently. There are other algorithms which are designed to keep within limited memory resources, writing chunks to slower memory only when necessary. Historically these were known as "tape sort" or merge sort

[Jan]

@Walter: sortrows uses the qsort command from the C-library. Some tests show, that Matlab's stable quicksort implementation in sort is much faster and has a better worst case behavior for sorted input.