15

The permutation operation needs to output a different matrix to the output, it's not like reshape, where the data is not modified, permute does modify the data.

However, if one tests the memory usage of a multidimensional permutation, it's the same as the variable used. So, my question is, how does MATLAB execute this permutation in order to avoid using any extra memory?

Extra question: Is there any scenario in which MATLAB actually uses extra memory?

Test code:

function out=mtest() 
   out = ones(1e3,1e3,1e3); % Caution, 8Gb
   out=permute(out,[3 1 2]);
end

Call this with:

profile -memory on
a=mtest;
profreport

CAUTION, its 8Gb of data.

Ander Biguri
  • 35,140
  • 11
  • 74
  • 120

2 Answers2

13

Your argument is flawed because the MATLAB memory profiler is not telling you the truth!

The permute method in fact does create a second copy of the matrix with the data permuted and returns it...

I just tried this myself:

  • In Windows 10, I opened the "task manager" on the "performance" tab with the "memory" graphs in view. I also set the "update speed" to "high" to get a finer time resolution.

  • I only have 8 gigs of RAM on my laptop, so to avoid thrashing I modified your function as:

    function out = mtest()
    out = rand([1e3,5e2,5e2]);  % about 1.8 GB = 1e3*5e2*5e2*8/2^30
    out = permute(out, [3 2 1]);
end

  • I then ran the function simply as:

    %clear a
a = mtest();

    and watched the memory usage; It went from 1.8 gigs in use, and rose to 5.2 then quickly down to 3.6 gigs. This confirms that a copy was created.

I also repeated the test under perfmon.exe which showed the same pattern:

perfmon

you can see how at its peak the function reached twice as much memory usage as when it returned.

While this is not exactly the best way to profile memory usage (better use a proper memory profiler, something like Intel Inspector XE), it does show to some degree that permute is indeed not working in-place.

Amro
  • 123,847
  • 25
  • 243
  • 454
  • 1
    Brilliant! I was starting to wonder if MATLAB was cheating on me, and indeed it was! It's good to know that this copy actually happens. – Ander Biguri Mar 17 '16 at 19:45
  • 2
    Great answer! I guess the programmers of `permute` preferred speed over memory efficiency – Luis Mendo Mar 17 '16 at 21:14
3

This is only a guess, as I don't really know what permute does under the hood.

  1. Permuting of dimensions can always be done as a sequence of elementary permute operations, where" elementary" means interchanging only two dimensions. For example, permute(x, [4 1 2 3]) is equivalent to this sequence of elementary permute operations (the sequence is not unique):

    permute(..., [4 2 3 1]) %// interchange dims 1 and 4: we have dims [4 2 3 1]
permute(..., [1 4 3 2]) %// interchange dims 2 and 4: we have dims [4 1 3 2]
permute(..., [1 2 4 3]) %// interchange dims 3 and 4: we have dims [4 1 2 3]

  2. Each of these elementary operations (interchanging two dimensions) is essentially a transpose along a given plane of the multidimensional array, performed repeatedly along all other dimensions.

  3. Transposition can be done inline, requiring only a fixed amount of extra memory, independent of array size, or growing very slowly with array size.

Putting these three facts together shows that it is possible to do it without a significant amount of extra memory. This may not be the approach actually used by Matlab, though.

Luis Mendo
  • 110,752
  • 13
  • 76
  • 147
  • Permute is way faster than transpose. I'm betting it doesn't touch the array data at all and just changes the order that indexes are evaluated in. If you want to transpose a 2D real matrix, then instead of doing `numrows*colindex+rowindex` to figure out the index into your 1D backing array, you can simply switch to using `numcols*rowIndex+colindex`. That will have the appearance of transposing the matrix without changing the data. An array that specifies the order to traverse dimensions could easily be associated with each array instead of relying on an implicit [1 2 3 4... N] design. – KitsuneYMG Mar 17 '16 at 15:56
  • 1
    @KitsuneYMG I know what you mean, but this logic has a defect: Indexing an array with that "index switch" is incredibly costly doe to memory read cache. If exactly what you say happens (just the way its indexed changes), then using the matrix later in other operations would have a huge performance drop, just because it has been transposed. And this effect can not be seen in MATLAB. My guess is that transpose is faster because it uses another algorithm. – Ander Biguri Mar 17 '16 at 16:03
  • 1
    Seeing @Amros answer one wonders if a function `mempermute` can be created to make a memory aware permute – Ander Biguri Mar 17 '16 at 19:49
  • @AnderBiguri: In my opinion the permute function is quite complicated as it is, so it would be challenging to code it to work inplace – Amro Mar 17 '16 at 19:53
  • @Amro yes, and probably it will be a slow permute, but the wikipedia page Luis liked suggest that it *can* be done. It would be that a bad idea to have, now the use of permute limits the memory a lot. Twice the memory is a lot. – Ander Biguri Mar 17 '16 at 19:54
  • 1
    @AnderBiguri I say this because I recently needed to do a similar permutation operation on the C++ side in a MEX function (convert general ND-arrays between column-major and row-major orders), but I just gave up and used `mexCallMATLAB` to call `permute` in MATLAB instead :) It's a general function that accepts any order permutation, not just simple transposing.. – Amro Mar 17 '16 at 19:56
  • @Amro You tell me.... : https://stackoverflow.com/questions/36034322/time-performance-when-permuting-and-casting-double-to-float :P I totally know what you mean – Ander Biguri Mar 17 '16 at 19:57
  • 1
    I see.. Then you might be interested to check out how we do it in [mexopencv](https://github.com/kyamagu/mexopencv) to convert between OpenCV's `cv::Mat`/`cv::MatND` and MATLAB's `mxArray` for all possible cases (multi-channels and/or multi-dimensions): https://github.com/kyamagu/mexopencv/blob/master/src/MxArray.cpp#L529 (see `toMat` and `toMatND` methods). – Amro Mar 17 '16 at 20:07
  • @Amro Fantastic! Ill have a look to that, but I see, calling MATLAB is actually a better thing than acctually triying to implement it one self. Also, as a complete side note: http://undocumentedmatlab.com/blog/better-mex-error-messages this migth help – Ander Biguri Mar 17 '16 at 20:17