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

 
 

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

Submitted by:  Marco Caliari <caliari>
Submitted on:  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

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

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>
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
  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>
Project 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)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    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.5