[Octave-bug-tracker] [bug #60928] Performance of sort unexpectedly slow for DIM=2

[Michael Leitner]

Follow-up Comment #10, bug #60928 (project octave):

Further, can you please point out to me where the sort routine that is called
e.g. in line 1812 and that actually does the sorting is to be found? I am not
familiar with C++, only C, so I can read the code line by line, but do not
find my way around the concept of templates etc.

Finally, I really do not think that it is a question of cache efficiency.
Because if it was, the elapsed time in


d=rand(2,2,100000);
tic;sort(d,1);toc
tic;sort(d,2);toc


should be the same -- cache lines are today 64 bytes, meaning 8 doubles, so in
both cases you have the same data transfer between main memory and cache. But
what I see is 0.018 sec for the first line and 7.03 sec for the second.

And here is a very drastic oddity, that should give a strong indication what
is going wrong here: it very much looks like the necessary time goes with the
square of N, the third dimension of d (100000 in the upper example) -- it is
1.74 sec for N=50000, 7.03 sec for N=100000, and 28.09 sec for N=200000. On
the other hand, sorting along the first dimension is rather sub-linear with
time readings of 0.012, 0.018 and 0.028 seconds.

This cannot be, as it is just as hard to sort the first of the N 2x2-matrices
along the second dimension as the last. The quadratic behaviour looks as if
the whole result array is copied around for each elemental sorting -- it has a
length proportional to N, and it is done N times. Please check whether you can
reproduce that, and if yes, then it should be a quite dumb fix. 

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?60928>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/