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
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

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):

multithreaded:

100x100x100
average = 0.7401
variance = 9.9383e-04

200x200x200
average = 9.7555
variance = 0.7624

no-multithreaded (matlab -singleCompThread)

100x100x100
average = 1.1056
variance = 0.0384

200x200x200
average = 28.3021
variance = 7.1439

octave 5.1.1

100x100x100
average =  1.5508
variance =  0.27300

200x200x200
average =  37.057
variance =  104.97

Marco Caliari <caliari>
Group 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
  P(i,:)
  tic
  for k = 1:1000
    permute (X, P(i,:));
  end
  t(i) = toc
end
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>
Group Member

 

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

Attach Files:
   
   
Comment:
   

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 group 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.13-4448.
    Corresponding source code