[Octave-bug-tracker] [bug #60928] Performance of sort, not sure if this is expected behavior?

[anonymous]

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

                 Summary: Performance of sort, not sure if this is expected
behavior?
                 Project: GNU Octave
            Submitted by: None
            Submitted on: Fri 16 Jul 2021 11:50:46 PM UTC
                Category: Octave Function
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Performance
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
                 Release: dev
         Discussion Lock: Any
        Operating System: GNU/Linux

    _______________________________________________________

Details:

Hello,

The time performance of the sort() function is very non-intuitive for
3-dimensional arrays when trying to sort each row (like 1000 times). I am
assuming some CPU cache effect is at work here but am dubious whether a 1000x
difference is attributable to that alone.

Test:

tmp = rand(5,3,5e5);
tic; tmp2 = sort(tmp,2); toc
tic; tmp1 = permute (sort (permute (tmp, [2 1 3]), 1), [2 1 3]); toc
assert(all(all(all(tmp1 == tmp2))))


Time difference:

Elapsed time is 0.154699 seconds.
Elapsed time is 152.283 seconds.


That's a 1000x difference between sorting rows and sorting columns, even after
the extra calls to permute.

One workaround therefore is to always wrap the sort() inside two calls to
permute(), so that the sort is only happening down the first dimension, which
seems to be fast. I do not know if this is the same problem in Matlab or not.

If the above is expected behavior for sort(), please consider calling
permute() from inside sort to get that overall performance boost. Maybe only
if the input has 3 or more dimensions and is bigger than say 2^16 elements? I
will accept the dev team's decision either way.




    _______________________________________________________

Reply to this item at:

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

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