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

[Michael Leitner]

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

I didn't look at the code, but I would think that at some point inside the
sort method the algorithm (which is timsort as taken from python, it seems)
should be operating on a copy of the raw data buffer as accessible by
fortran_vec(). Thus, all that would be needed to sort along dimensions other
than the first would be to use a stepping that is the product of the
dimensions before the one along which is sorted. Thus, in the case of sorting
a 5x3x5e4 array of doubles along the second dimension one would call five
sorts in a for (j=0;j<5;j++) loop where every buffer[i] in the algorithm would
have to be replaced by buffer[j+5*i]. This would minimize the copying, but
there are situations where it would become inefficient due to bad caching
behaviour.

Thus, I think it would be best to indeed do the permuting (assuming that
permute is implemented cache-efficient) and always sort along the first
dimension (with a special treatment for the case that the size of the
dimension along which to sort is one): in the typical case, a given value will
be copied around during sorting about log(N) times, where N is the size of the
dimension along which to sort, and N will be most times not very small. As a
consequence, the pre- and post-processing by dimensional permuting will be
cheap compared to sorting, and on the other hand sorting along the first
dimension is always optimally cache-efficient. 

For optimal efficiency, one could do the idea of the first paragraph for N
smaller than, say, 20, otherwise the permuting.

    _______________________________________________________

Reply to this item at:

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

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