bugGNU Octave - Bugs: bug #57805, Some array permutations are much...


bug #57805: Some array permutations are much slower than others

Submitter:  Marco Caliari <caliari>
Submitted:  Thu 13 Feb 2020 12:51:40 PM UTC
Category:  Libraries Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * 5.1.0 Operating System:  * GNU/Linux
* Mandatory Fields

Add a New Comment (Rich Markup)

Comment Type & Canned Response:


Fri 14 Feb 2020 09:26:45 AM UTC, comment #3: 

Interesting, multithreading benefits specifically the large permutations, where data are definitely out of cache. That puzzles me. So comparing the single-threaded values, octave has a larger dependence on the particular permutation than matlab, and while for the easier permutations octave and matlab are about on par, octave suffers with the harder permutations. Perhaps I find some time and can jot down a simple test implementation of permute that is agnostic of the interpretation of the data (that is, just copying around strings of bytes) and see how close the octave values are to the optimum.

Michael Leitner <mleitner>
Fri 14 Feb 2020 09:12:30 AM UTC, comment #2: 

Thanks Michael.

About multithreading, I observe in Matlab R2019a (yes, I have 9216 kB L3 cache):


average = 0.7401
variance = 9.9383e-04

average = 9.7555
variance = 0.7624

no-multithreaded (matlab -singleCompThread)

average = 1.1056
variance = 0.0384

average = 28.3021
variance = 7.1439

octave 5.1.1

average =  1.5508
variance =  0.27300

average =  37.057
variance =  104.97

Marco Caliari <caliari>
Project Member
Fri 14 Feb 2020 08:41:15 AM UTC, comment #1: 

To answer your question, I would say yes, it is desirable to perform as fast as the specific problem allows. On my computer, I have the timings

t =

   3.990061   3.176484   3.510465   2.557613   2.339767   0.015316

where P is

P =

   3   2   1
   3   1   2
   2   3   1
   2   1   3
   1   3   2
   1   2   3

For completeness, I let i go up to 6. So the permutation with respect to P(6,:) is of course a no-op, so it is naturally the fastest. P(4,:) leaves the third dimension where it is, corresponding to 100 independent 100x100-matrix transpositions, while P(5,:) leaves the first dimensionen, corresponding to a single 100x100-matrix transposition, where the elements are however 100-element columns. So it is not surprising that these two are faster than the first three, and just looking at these results, I would find no aspect in which the present implementation is lacking.

However, you say that Matlab is overall faster, so this means there is potential for optimization. But then you say that Matlab is even more faster if you do it multithreaded. And this is something I find hard to believe. I would have expected these operations to be essentially memory bandwidth-limited, that is, that it is the rate by which data can be transferred from and to main memory that decides the performance, and not the computing power. And if you have multiple CPUs working, they should still have to go through the same memory bus, I think. This should definitely be the case for P(4,:), where you copy around 800 byte chunks. Are you sure that your data are large enough to be out of cache? A 100x100x100-matrix of doubles is just 8000000 bytes, which is in the range of today's L3 caches.

Perhaps somebody can point out the position in the source code where the copying around is actually done (I just could follow up to args(0).permute (vec, inv) in data.cc) to see whether there is something that can be optimized. For a pointer to present investigations of such algorithms see https://doi.org/10.1016/j.aej.2015.03.024

Michael Leitner <mleitner>
Thu 13 Feb 2020 12:51:40 PM UTC, original submission:  

Dear all,

the following code

n = 500;
X = randn (100, 100, 100);
P = perms(1:3);
for i = 1:5
  for k = 1:1000
    permute (X, P(i,:));
  t(i) = toc
average = mean (t)
variance = var (t)

gives me an average elapsed time of 1.5 seconds with a variance of 0.3 seconds in octave (with the first permutation much slower than the others), while an average elapsed time of 1.0 with a variance of 0.03 in matlab (with -singleCompThread, otherwise it is multithreaded and even faster). Is it a desired feature to have permute much faster for some permutations?

Marco Caliari <caliari>
Project Member


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

Attach Files:

No files currently attached


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -email is unavailable- added by mleitner (Posted a comment)
  • -email is unavailable- added by caliari (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 project members can vote.





    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2020-02-27 mtmiller CategoryNone Libraries
    2020-02-14 caliari Item GroupNone Performance

    Back to the top

    Powered by Savane 3.9