bugGNU Octave - Bugs: bug #53012, Performance of sort on complex...

 
 

bug #53012: Performance of sort on complex values

Submitter:  Michael Leitner <mleitner>
Submitted:  Tue 30 Jan 2018 10:24:11 AM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Wed 31 Jan 2018 05:08:14 PM UTC, comment #5: 

I think that's not a bad trade-off.  Peak memory would be 16N (original array) + 16N(temporary array) + 16N(index vector) or 48N.  The current solution is probably 16N (original array) + 16N (output sorted array) or 32N.  The ratio is only 1.5.

I believe this should be done, but it will require hacking deep in to liboctave.  There is both the sorting routine in liboctave/util and then code which calls it out of Array.cc.  The code in Array.cc is general and shared by all types that derive from it.  If we override each of the Complex object types there are quite a few.


CColVector.h    CMatrix.h       CRowVector.h    fCDiagMatrix.h  fCNDArray.h     fCRowVector.h
CDiagMatrix.h   CNDArray.h      CSparse.h       fCColVector.h   fCMatrix.h


There might be an intermediate ancestor between Array and these final types which could be overridden.  That would be ideal because I would rather not repeat the code 11 times.



Rik <rik5>
Group administrator
Wed 31 Jan 2018 04:25:58 PM UTC, comment #4: 

Yes, it seems you are right, sortrows needs more internal storage than what it needs for the output (this should have been obvious to me). When I limit the available virtual memory for the octave process to 2 GB via bash's ulimit, I can allocate a matrix of dimensions Nx2 with N up to 8.5e7, but I can generate the permutation vector via sortrows only for N=4e7. So it seems that the memory consumption would be 16* N for the input, 16* N for the temporary [abs() arg()], and about 16* N for the generation of the permutation vector (including already the output). That is, going via sortrows the peak consumption is about three times the size of the input, while via the native sort it is about two times.

Probably this cannot be significantly improved anymore, so we have to stick with the time/space dilemma.

Michael Leitner <mleitner>
Wed 31 Jan 2018 03:40:41 PM UTC, comment #3: 

That seems right.  I was just counting blocks of memory, but being more specific about the sizes of those blocks shows that the overhead is only 25% (5/4).

One of the things to verify, or change, would be to make sure that internally sortrows can form the index vector without also forming the sorted array.  If the sorted array must always be generated then the overhead would be 75% (7/4).

When using '~' in the interpreter to discard an output it is the function's responsibility to check for that condition.  Some routines don't bother and calculate every single output and then just let the interpreter silently discard the unused ones.  That is not ideal, but many routines were coded before the '~' feature was even available.

Rik <rik5>
Group administrator
Wed 31 Jan 2018 07:54:19 AM UTC, comment #2: 

It's not quite that bad. Remember that this path would only be taken when the input r is complex, and that abs(r) and arg(r) both are real. Thus, when you sort a vector of N complex doubles, you have an input of 16* N byte and generate an output of 16* N byte in the current implementation. Going via sortrows, you generate in addition to the input 16* N temporary bytes, pass it to sortrows, which gives you back an index vector of 8* N bytes. At this point you can clear the temporary [abs(r) arg(r)] and generate the final output of 16* N bytes. So the peak memory consumption relates as 5/4, which is not so critical, I would say (in fact probably even less, because sort uses additional state internally, and I would guess this to be of the same magnitude in both algorithms).

When you request both sorted array and permutation indices, the memory consumption is exactly equal, and when you only request the permutation indices, it will probably be the same (because I would guess that the traditional sort needs at least the same internal storage as the size of the input, even when it only needs to compute the indices).

Have you tested your quoted values of memory requirements, and have I overlooked something?

Michael Leitner <mleitner>
Tue 30 Jan 2018 05:47:28 PM UTC, comment #1: 

Confirmed.  This is a pretty classic time/space trade-off.  The current solution uses 2N blocks of memory ([1] original array, [2] returned sorted array), but requires on order N log2(N) calculations of abs and a variable number of angle calculations.  Using something like sortrows would require 4N blocks of memory ([1] original array, [2] abs (array), [3] angle (array)], [4] sorted index array) but a guaranteed number of N calculations of abs and angle.

An additional possibility is to consider a threshold where smaller arrays use sortrows and larger arrays use the traditional sort routine.  Note that the threshold could be quite high.  One million complex double values is 16 MB so the sortrows solution would require 64 MB.  Most PCs have RAM measured in GB so this wouldn't necessarily be an issue.

I'm attaching an updated test script.


N = 3e6;

r = complex (rand (N,1), rand (N,1));

## Use sortrows, N calculations of abs and angle, but 4*N memory requirements
tic;
[~,j] = sortrows ([abs(r), angle(r)]);
rs1=r(j);
bm1 = toc

## sort, N*log2(N) calculations of abs and possibly angle, 2*N memory
tic;
rs2=sort(r);
bm2 = toc

isequal(rs1,rs2)


which shows sortrows is ~3X faster.


bm1 =  1.1423
bm2 =  3.0540
ans = 1




(file #43111)

Rik <rik5>
Group administrator
Tue 30 Jan 2018 10:24:11 AM UTC, original submission:  

I am splitting up bug #52919. Now to the performance of sort on complex values:

Sort is unnecessarily slow on complex values. Consider the following code:


N=1e7;
r=floor(randn(N,1)+1i*randn(N,1))+.5+.5*1i;
tic;[~,j]=sortrows([abs(r) angle(r)]);rs1=r(j);toc
tic;rs2=sort(r);toc
isequal(rs1,rs2)


On my computer, the first line takes 2.3 seconds, while the second line takes 8.0 seconds. The results are equal (apart from subtleties that could be introduced as mentioned in bug #53011). Probably, this comparatively low performance is due to sort having to compute two absolute values for each comparison, of which there are about log(N)*N. Indeed, it seems that it does not only compute the absolute value, but also the phase angle (?), because defining


r=randn(N,1)+1i*randn(N,1);


where all absolute values are different so that no angles would have to be computed, does not help at all. In contrast, the sortrows-solution computes only N absolute values and N angles.

With a bit of m-code reshaping, this could be generalized to work also for N-dimensional objects with sorting along a chosen dimension (and thus automatically to an actual sortrows evaluated on complex inputs). Also, Matlab's new option 'ComparisonMethod','real' could of course cheaply be emulated by


sortrows([real(r) imag(r)]);rs1=r(j);


As sort is a built-in function, it is beyond me to make these changes. It would be probably easy to rename the built-in to _sort_ and pull the checking for complex inputs (and the input validation) to an m-code wrapper, but as sort is quite fundamental, it is perhaps worth the while to stay on the C++ level.

As I have argued elsewhere, I am not quite convinced that it is a good idea to sort complex values (or even compare them) at all, because if I want to sort on the absolute values, I would explicitly do so, but unique also uses sort and would hence profit from an increased performance, and here it is obviously meaningful to ask for the unique values of a complex vector.

Michael Leitner <mleitner>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #43111:  bm_complex_sort.m added by rik5 (308B - text/x-matlab)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Updated the item)
  • -email is unavailable- added by mleitner (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-01-30 rik5 Attached File- Added bm_complex_sort.m, #43111
        StatusNone Confirmed
        Release4.2.1 dev

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code