Matlab Performance Question (Nested for loops vs inbuilt functions (cellfun, circshift))

I am using R2017b. I am trying to do the same thing 3 different ways. (1)using 2 nested for loops (2) replacing inner for loop with an inbuilt function and (3) replacing both for loops with an implicit expansion and a sub-function. The code and cputimes (in the same order) are listed below

tic;
c=1;
for i = 1:length(t)
    n = length(t{i});
    for j = 1:n
        e(1,c) = t{i}(j);
        e(2,c) = t{i}(max(1, mod(j+1,n+1)));
        c = c + 1;
    end
end
toc;

tic;
e = [];
for i = 1:length(t)
    e = [e, [t{i};circshift(t{i}, -1)] ];
end
toc;

tic;
e = cellfun(@cshiftCell, t, 'UniformOutput', false); 
toc;

function em = cshiftCell(ec)
  em = [ec; circshift(ec,-1)];
end

Elapsed time is 0.077777 seconds.
Elapsed time is 0.177772 seconds.
Elapsed time is 0.525799 seconds.

This is a bit counter-intuitive to me because I have always heard nesting for-loops always lead to worst performance (except in certain languages like Julia) and was expecting the cputimes to be in exact reverse order. Does anyone have an explanation as to what is going on? I am developing a relatively large scale code and understanding such performance aspects of matlab is critical to me. I am happy to read any articles/documentation you point me to as well. Thanks!

Edit: Solved! Best explanation was provided by Walter . A superior approach was shown by Cedric.

[Cedric]

If you attach a MAT-File with the data that we need to run these tests, some of us may give it a try.

[Ashwin Renganathan]

Sure. see attached.

[Cedric]

I won't have time until possibly the end of the week end, but one thing that should improve the performance of solution 1 is to prealloc e:

 e = zeros(2, sum(cellfun('length', t))) ;

Answer 1

[Cedric]

Well, I got a few minutes at the airport. Try this in your comparison:

tic ;
s = cellfun('length', t) ;
v = cumsum(s) ;
e_cw = double([t{:}]) ;
e_cw = [e_cw; e_cw(2:end),0] ;
e_cw(2,v) = e_cw(1,[0,v(1:end-1)]+1) ;
toc

(your move, Andrei ;) )

[Ashwin Renganathan]

This approach was 3-5x faster than my fastest approach! The main difference being you got rid of circshit (?)

Based on the answers I got so far and my own experience, it appears like (i) certain matlab built-ins may not be highly optimized so writing one's own code could outperform them and (ii) creating extra variables (s,v in your approach; c, n in myapproach-1) is not necessarily bad coding.

[Cedric]

You can see it this way:

• CELLFUN, ARRAYFUN, etc are hidden loops. They may introduce some overhead but they bring a lot of conciseness. This is very valuable in contexts where you are not running after some micro-seconds, because you can code a full loop + prealloc with a one-liner. This has value because it often reduces the code and makes the general approach more understandable: "on this line we get all sizes of internal arrays, on the next we .." is more readable than "these five lines extract sizes, and the next 7 do ..".
• MATLAB functions are generally cascades of tests that pick the most efficient method given the inputs. This introduces some overhead but the gain can be astronomical when you are dealing with large and complex problems. The implementation of the backslash operator (LINSOLVE) for example is ~120,000 lines of code that encompasse best methods for most types of inputs. In some cases, however, like repeating a lot of time calls passing small/simple inputs, it is detrimental because the overhead can be much greater than the gain, especially if you know exactly the type of inputs and the best method already.
• Preallocating memory before loops is always key to improving efficiency (it avoids repeating malloc/realloc/etc at each iteration), hence my comment under your main question. Test it against your first method and you should see some improvement.
• My solution relies on calling efficient functions or doing operations that introduce little overhead, and on avoiding loops and hidden loops (like in CELLFUN) unless absolutely necessary. Also, when calling CELLFUN, I pass a function name instead of a handle (some functions are supported this way) and MATLAB can use compiled versions instead of calling them through a handle mechanism. If you replace 'length' by @length, you should observe a degradation of the performance. You can see Jan mentioning the same thing here in his comment under Andrei's answer.

I didn't have time to comment, but my solution does manually a single CIRCSHIFT of the whole content, to get all elements of e(2,:) correctly except for those that correspond to the right-most elements of each sub-set (that should be the former left-most elements), and then updates these elements only (getting correct values from e(1,:)).

[Ashwin Renganathan]

Awesome. Thank you!

Answer 2

[Walter Roberson]

I do not know if it is still the case, but cellfun() at least used to be implemented as pure MATLAB, and so (at least then) could never be faster then coding the calls yourself.

Calling an anonymous function has a surprising amount of overhead. If you call them a large number of times, that can really add up.

Built-in functions are really divided into two cases: those implemented as MATLAB, and those implemented as compiled code. The ones implemented as MATLAB can never be faster than doing the work yourself, and are often slower because of the error checking and parsing that is done on every call. If you "which" a function name and it says "built-in" then at least the top layer of it is compiled code and there is the potential for being faster than doing the work yourself.

For loops are typically slower than vectorization -- but only if the equivalent work is being done. It is not uncommon that in order to vectorize, you end up creating non-trivial internal arrays, and vectorization is often unable to take advantage of known stopping conditions. For example, code of the form

   for K = 1 : 1e7
      if vectorizable_operation(K) == key_value
        break;
      end
   end

can be faster than

find( vectorizable_operation(1:1e7) == key_value, 1, 'first')

because the cost of doing the calculations on the values that will turn out to be unused can be a fair bit. Even in cases where the cost of a particular vectorized operation is quite low, usually less than the "for" overhead, if you are low on memory then looping might turn out to be faster, as it can avoid pushing your memory use to the point where you are swapping.

[Ashwin Renganathan]

Thanks! I just checked and cellfun in 2017b is builtin and I am not using an anonymous function either. Your explanation makes sense to me, but I do not have any conditional statements in my code, so I am having some difficulty relating your explanation directly to my case. But I will think more about it...

[Walter Roberson]

@cshiftCell is an anonymous function for this purpose.