MATLAB: Comparing the performance of colon, loop, and cell indexing

cell arrayscolon indexingindexingloopsMATLABperformance

I will first state the problem and then ask my question.
PROBLEM
I have this code where repeatedly multiply a vector by a square matrix and store the resulting vector. The vector has a dimension dim and it is multiplied by the matrix numSteps times.
I wrote three variations of this code. First, I store the vector using colon indexing. Second, I store the vector using loop indexing. Third, I store the vector in a cell array using cell indexing.
The three functions are the following. They are identical except for the way the data is stored.
Colon indexing:
function output = funcColon(dim,numSteps)
%FUNCCOLON Function that stores vectors using colon indexing
% Initialize the output and the vector


output = zeros(numSteps,dim);
vec0 = ones(dim,1);
% Choose a matrix


mat = rand(dim); mat = mat./sum(mat,1);
% Do repeated matrix multiplications


for k=1:numSteps
    vec = mat*vec0;
    vec0 = vec;
    output(k,:) = vec; % Use colon indexing to store the results
end
end
Loop indexing:
function output = funcLoop(dim,numSteps)
%FUNCLOOP Function that stores vectors using a loop
% Initialize the output and the vector
output = zeros(numSteps,dim);
vec0 = ones(dim,1);
% Choose a matrix
mat = rand(dim); mat = mat./sum(mat,1);
% Do repeated matrix multiplications
for k=1:numSteps
    vec = mat*vec0;
    vec0 = vec;
    for j=1:dim
        output(k,j) = vec(j); % Use a loop to store the results
    end
end
end
Cell indexing:
function output = funcCell(dim,numSteps)
%FUNCCELL Function that stores vectors using a cell array
% Initialize the output and the vector
output = cell(numSteps,1);
vec0 = ones(dim,1);
% Choose a matrix
mat = rand(dim); mat = mat./sum(mat,1);
% Do repeated matrix multiplications
for k=1:numSteps
    vec = mat*vec0;
    vec0 = vec;
    output{k} = vec; % Store the vector in a cell array
end
end
I first set numSteps=100. I then ran each function for various values of dim and I timed them. I did this multiple times to accumulate statistics on the average runtime.
The results are shown in the attached figure. I take the average runtime of the colon indexing as a point of reference, i.e., the two curves show the ratio of the average runtimes of funcLoop and funcCell to the average runtime of funcColon.
There are basically two regimes.
First, there is the regime dim > 1. There, we have the hierarchy:
runtime loop < runtime cell < runtime colon
Second, there is the regime dim < 1. There, we have the hierarchy:
runtime loop < runtime colon < runtime cell
Note that in the limit of large dim, all functions tend to the same runtime because the runtime becomes limited by the matrix multiplication. But for small dim, the runtime is limited by the indexing. I checked that it is indeed the case with the Run & Time feature.
QUESTION
I'm quite confused by this result. I would have assumed that colon indexing would always be faster because it is a syntax designed specifically for matlab arrays. What is colon indexing doing that is taking so much additional runtime? Even cell array indexing is more efficient than colon indexing for dim > 1.
This seems to imply that I could rewrite an overloaded custom colon indexing function using a for loop and have it be more performant than MATLAB's native colon indexing.
Am I missing something? What are your suggestions for best practices with a code like that?

Best Answer

"Am I missing something?"
1- accessing data in non-contiguous locations is slow. Consider your indexing output(k,:): because MATLAB stores arrays in column-major order, your indexing refers to lots of separate locations spread out through the entire array. Carefully going through the array, finding those locations, splitting up the input array and copying the parts to each separate location... is not efficient, and gets slower for larger arrays. You data design forces MATLAB to be slow.
If you access only contiguous blocks of memory you would find the code would be much faster: output(:,k)
2- MATLAB (probably) does not actually copy those arrays, so although you write that it "stores" the input array in a cell:
output{k} = vec; % Store the vector in a cell array
actually MATLAB (probably) just stores a pointer to the already existing input array, and creating one small pointer does not take much time at all. The original array (probably) does not move or get copied anywhere, until you write to any location in that array, at which point it will finally get copied... and in your code this never happens, so you are comparing apples with oranges here.
Read about copy-on-write:
https://www.mathworks.com/help/matlab/matlab_prog/avoid-unnecessary-copies-of-data.html
Note that even if/when the input array is "copied" to the cell it would still be one contiguous array in memory!
"What are your suggestions for best practices with a code like that?"
  • Consider column-major in your design: if efficiency is important store data in contiguous locations.
  • Consider copy-on-write in your design.
Related Question