Why is reshape so fast? (Spoiler: Copy-on-Write)

by

Explanation of the good performance

Matlab uses copy-on-write whenever possible. If you write expressions like B=A, MATLAB does not copy A, instead both variables A and B are references to the same data structure. Only if one of the two variables will be modified, MATLAB will create a copy.

Now to the special case of reshape. Here it looks like A and B are not the same, but in memory they are. The underlying array which holds the data is unaffected by the reshape operation, nothing has to be moved: all(A(:)==B(:)). Everything MATLAB has to do when calling reshape is to create a new reference and annotate it with the new dimensions of the matrix. Reshaping a matrix is nothing more than creating a new reference to the input data, which is annotated with the new dimensions. The runtime of reshape is less than 1µs or roughly the time two simple assignments like B=A require. For all practical applications a zero time operation.

>> tic;for i=1:1000;B=reshape(A,1024,128,1024);end;toc
Elapsed time is 0.000724 seconds.
>> tic;for i=1:1000;B=A;end;toc
Elapsed time is 0.000307 seconds.

It is unknown how large such a reference really is, but we can assume it to be within a few bytes.

Other zero cost operations

Functions known to have practically zero cost (both runtime and memory):

  • B=reshape(A,sz)
  • B=A(:)
  • B=A.' – only for Vectors
  • B=A' – only for Vectors of real numbers, without the attribute complex. Use .' instead.
  • B=permute(A,p) – only for the cases where all(A(:)==B(:)).1
  • B=ipermute(A,p) – only for the cases where all(A(:)==B(:)).1
  • B=squeeze(A) 1
  • shiftdim – only for the cases where all(A(:)==B(:)), which are:1
    • used to remove leading singleton dimensions.
    • used with negative second input
    • used without second input argument.

Functions which are “expensive”, regardless of the fact that they don’t touch the representation in memory (all(A(:)==B(:)) is true)

  • Left sided indexing: B(1:numel(A))=A; 2
  • Right sided indexing other than (:), including B=A(1:end); and B=A(:,:,:); 2

1 Significantly slower runtime than reshape between 1µs and 1ms. Probably because of some constant computation overhead. Memory consumption is practically zero and the runtime is independent from the input size. Operations without this annotation have a runtime below 1µs and roughly equivalent to reshape.

2 Zero cost in OCTAVE

Originally used MATLAB 2013b when writing this post. Confirmed the numbers with MATLAB 2019b.

More Related Contents:

  1. Why is MATLAB so fast in matrix multiplication?
  2. Efficiently compute pairwise squared Euclidean distance in Matlab
  3. Comparing BSXFUN and REPMAT
  4. bsxfun implementation in matrix multiplication
  5. Mapping 2 vectors – help to vectorize
  6. Faster way to initialize arrays via empty matrix multiplication? (Matlab)
  7. Bin elements per row – Vectorized 2D Bincount for NumPy
  8. MATLAB parfor is slower than for — what is wrong?
  9. Run-length decoding in MATLAB
  10. Create a zero-filled 2D array with ones at positions indexed by a vector
  11. Speed-efficient classification in Matlab
  12. How can I apply a function to every row/column of a matrix in MATLAB?
  13. Cellfun versus Simple Matlab Loop performance
  14. timing code in matlab
  15. Multiply a 3D matrix with a 2D matrix
  16. Why is vectorization, faster in general, than loops?
  17. How do I compare all elements of two arrays?
  18. How can I sort a 2-D array in MATLAB with respect to one column?
  19. Is indexing vectors in MATLAB inefficient?
  20. Is MATLAB faster than Python?
  21. Vector norm of an array of vectors in MATLAB
  22. MATLAB: Subtracting matrix subsets by specific rows
  23. Efficiently compute a 3D matrix of outer products – MATLAB
  24. Performance optimization strategies of last resort [closed]
  25. How are x86 uops scheduled, exactly?
  26. How do you concatenate the rows of a matrix into a vector?
  27. Creating Indicator Matrix
  28. How can I divide each row of a matrix by a fixed row?
  29. Octave/Matlab: Adding new elements to a vector
  30. How do I remove elements at a set of indices in a vector in MATLAB?

Leave a Comment