Using a function instead of inlining increases the time it takes to run

I use 64-bit Matlab R2014b.

I have a large matrix in which I iteratively change one element and I have another operation in which I sort a smaller matrix. I have two minimal working examples and I would like to know why one approach takes longer than the other. The first example uses a direct approach, whereas the second approach uses a function to perform the task.

Minimal working example 1

   n_iter = 1e7;

   A = zeros(n_iter,1);
   B = sort(rand(1e3,1));

   for i = 1:n_iter

       A(i) = 1;

       B = sort([ B(2:end); B(1) ]);

   end

Minimal working example 2

   function deallocating_large_matrices_function

   n_iter = 1e7;

   A = zeros(n_iter,1);
   B = sort(rand(1e3,1));

   for i = 1:n_iter

       A(i) = 1;

       B = sortB(B(2:end),B(1));

   end

   end

   function B = sortB(B,new_entry)

       B = sort([ B ; new_entry ]);

   end

Results

Below a table showing the time it took to run both examples as a function of n_iter, using the profiler.

   n_iter | time MWE 1 (sec) | time MWE 2 (sec)
   --------------------------------------------
   1e4    | 0.13             | 0.21
   1e5    | 1.38             | 1.98
   1e6    | 13.5             | 19.7
   1e7    | 137              | 196

The time it takes to run both MWE 1 and MWE2 increases linearly. Running MWE 2 takes approximately 46% more time. What is the cause of this increase?

[Adam]

I did read something concerning this not that long ago though I can't remember in what context.

A function has to be located in your path in order to be run so that will account for some overhead, although that is generally a first-time overhead and is faster on subsequent runs. It also shouldn't scale up with size.

I suspect it has something to do with a function having to create its own workspace which has an overhead, but again I'm not sure why this would scale up with data size other than that the data has to be copied by value to the function whereas inline this does not need to happen.

Adding this as a comment rather than an answer because it is not anything concrete, just musings based on my understanding of functions, but I don't have a deep understanding of exactly what goes on in Matlab with respect to function calls.

[Jori]

Thanks Adam for your comment. Just for clarity, MWE 2 is just one .m-file.

With regards to your third paragraph, I was thinking that it indeed had something to do with that. I assume that the function sortB stores it arguments (B and new_entry) in a separate slot in memory, since these are local variables to the function sortB. Is it possible that at the end of every iteration, Matlab needs to deallocate the memory that the function sortB uses? This then also explains the increase of 46% for every number of iterations.

[Adam]

As far as I am aware it will recreate the function's workspace every call, although I don't know what kind of optimisations of the code take place at runtime - it may be clever enough to optimise that away.

I think new_entry in your above code will not take up any new memory, but B will, in your subfunction. This is because even though Matlab passes data by value rather than by reference, it is clever enough to not take a physical copy of data until or unless that data changes in your sub-function. At that point it will allocate memory and copy the data into it since it can't refer to the original any more.

If a variable is just input to a function, but remains unchanged in that function I am fairly sure no new memory is allocated to it and it just refers to the original in memory. I may be wrong there though and someone will hopefully correct me if I am.

Answer 1

[Amit]

The issue is in subfunction

     function B = sortB(B,new_entry)
         B = sort([ B ; new_entry ]);
     end

You are passing a vector of size 'n-1' as B and the returning the same variable B but with size 'n'. This requires rewriting and reallocating memory, in other words more time!

Try this: function deallocating_large_matrices_function

   n_iter = 1e7;

   A = zeros(n_iter,1);
   B = sort(rand(1e3,1));

   for i = 1:n_iter

       A(i) = 1;

       B = sortB([B(2:end);B(1)]);

   end

   end

     function B = sortB(B)
         B = sort(B);
     end

This will result in more comparable time.

[Jori]

This shaved the time down to a mere 7% increase. Thank you for your answer.