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

[anonymous]

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

In libinterp/octave-value/ov-re-mat.cc, in this function:

octave_matrix::sort (octave_idx_type dim, sortmode mode) const


there is this line:

    return octave_base_matrix<NDArray>::sort (dim, mode);


which seems to create a new copy of each row when sorting an NDArray along
DIM=2, then sorting it and returning it. The extra time seems to be spent
mostly in copying existing values back and forth.

When called with DIM=1, there seems to be an idx_cache and the line

    return octave_lazy_index (*idx_cache).sort (dim, mode);

seems to be invoked instead. Can someone please confirm?

I think the reason it affects only DIM=2 and not DIM=3 for 3-dimensional
arrays, is that for DIM=3 the construction of "octave_base_matrix<NDArray>" is
called only once but for DIM=2 it's called for each row. By this hypothesis,
sorting higher-dimensional arrays will cause DIM=3 to also slow down, by
roughly 1/ncols of the DIM=2 slowdown.

Here's some additional data for sorting a 4D array. As seen, DIM=1 is very
fast, but now both DIM=2 and DIM=3 are slow, presumably from all the copy
constructions? Also the time for DIM=3 is roughly 1/3 that of DIM=2, because
there are 3 columns in the array.

octave:11> tmp = rand (3,3,3,1e5); tic; tmp = sort(tmp,1); toc
Elapsed time is 0.0273931 seconds.
octave:12> tmp = rand (3,3,3,1e5); tic; tmp = sort(tmp,2); toc
Elapsed time is 32.3812 seconds.
octave:13> tmp = rand (3,3,3,1e5); tic; tmp = sort(tmp,3); toc
Elapsed time is 10.9626 seconds.
octave:14> tmp = rand (3,3,3,1e5); tic; tmp = sort(tmp,4); toc
Elapsed time is 0.238446 seconds.


Is this thinking on the right path?


    _______________________________________________________

Reply to this item at:

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

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