How to speed up a nested for loop code in Matlab

Question

I was trying to speedup the following code:

xdim=5560;
ydim=6945;
zdim=7;
Nexi=270250785;
Neyi=270260480;

kne=1;
for i=1:xdim
    tic
    for j=1:ydim
        for k=1:zdim
            if j<ydim
                map_ey(j+(k-1)*(ydim-1)+(i-1)*(ydim-1)*zdim+Nexi)=kne;
                kne=kne+1;
            end
        end
    end
    for j=1:ydim
        for k=1:zdim
            if k<zdim
                map_ez(j+(k-1)*ydim+(i-1)*ydim*(zdim-1)+Nexi+Neyi)=kne;
                kne=kne+1;
            end
        end
    end
    for j=1:ydim
         for k=1:zdim
            if i<xdim
                map_ex(j+(k-1)*ydim+(i-1)*ydim*zdim)=kne;
                kne=kne+1;
            end
        end
    end
    toc
end

As seen from the above code, I have used tic toc, i find each loop iteration for each i value as follows:

Elapsed time is 0.378693 seconds.
Elapsed time is 0.378163 seconds.
Elapsed time is 0.380865 seconds.
Elapsed time is 0.378316 seconds.
Elapsed time is 0.377940 seconds.
Elapsed time is 0.379100 seconds.
Elapsed time is 0.378394 seconds.
Elapsed time is 0.383894 seconds.
Elapsed time is 0.397466 seconds.
Elapsed time is 0.415835 seconds.

Can it be possible more fast? Please help. thanks in advance.

What are you actually trying to do? Aren't you trying to achieve `map_ex=reshape(permute(reshape((1:xdim*ydim*zdim)+2*xdim*ydim*zdim,[xdim ydim zdim]),[2 3 1]),[],1)` or something similar (lot of off-by-one errors, etc., but you catch my drift)? Your code, unfortunately, is as slow as it can get. I'd rather not tell you how to speed it up: you should rewrite it with efficient MATLAB code. For that, you have to tell us what you wish to achieve. Also: `map_ey` and `map_ez` seem to contain a lot of emptiness: are you sure? (Maybe I'm mistaken, though) — Andras Deak -- Слава Україні, Jan 09 '16 at 21:50
OK, just *one* important hint: pre-allocate your variables instead of inflating them step by step: `map_ey=zeros(ydim-1+(zdim-1)*(ydim-1)+(xdim-1)*(ydim-1)*zdim+Nexi,1)` etc. This alone should give considerable speed-up, but I stand by my earlier comment. — Andras Deak -- Слава Україні, Jan 09 '16 at 21:57
Hey buddy, i just want to make it vectorize form as you have shown reshape() command, is it possible? — Jacks, Jan 10 '16 at 06:29
What I meant that your above code is very hard to decypher. Surely you have some formula or concept which you programmed with this beast. If you tell us what you actually want to ahieve, i.e. exactly how `map_ex` etc. should look like (in simple terms), we could help. — Andras Deak -- Слава Україні, Jan 10 '16 at 10:38

score 2 · Answer 1 · answered Jan 09 '16 at 22:01

As you've found out, for loops (the way that you have implemented them) are relatively slow in MATLAB. Sometimes they are not avoidable, but we can do a few simple things to try to optimize them.

The first is to look at the mlint warnings for help (the orange underlines within the MATLAB editor). If you'll notice, you are expanding the size of map_ex, map_ey, and map_ez every time you go through the loop. This causes MATLAB to continually reallocate the memory used to store those variables which causes the program to get slower and slower as the size of those arrays grow. To avoid this pitfall, pre-allocate the arrays (i.e. create an empty array at the beginning that is as big as you expect the array to get).

In your case this seems to be the following

map_ex = zeros(1, (xdim - 1) * ydim * zdim);
map_ey = zeros(1, (xdim * (ydim - 1) * zdim) + Nexi);
map_ez = zeros(1, (xdim * ydim * (zdim - 1)) + Nexi + Neyi);

Then you could perform your for loops the same way as you currently have written and you should notice an immediate performance bump.

Another thing that I notice while looking at your code is that you have this motif repeated throughout

for k=1:zdim
    if k < zdim
        % Do something
    end
end

The issue here is that you're comparing k to zdim every time through the loop when you can really just loop through the only necessary values of k

for k = 1:(zdim - 1)
    % Do something
end

This removes an unnecessary if statement that gets evaluated every single time through the loop.

As I am sure you're aware, the preferred way to do things in MATLAB is via vectorization rather than for loops. It is difficult how to vectorize your code in a clear and concise way without seeing what exactly you're trying to implement here. I can vectorize what you have so far, but I have a feeling that there may be better ways to do it. If you can provide some more information on the problem you're trying to solve, maybe I can provide a little more assistance.

Additionally, if you really need performance and can't avoid using for loops, MATLAB does provide the mex library so you can implement this type of code in C/C++ and still call it from within MATLAB.

I'd also suggest removing those dirty magic numbers `Nexi`, `Neyi`. Turns out `map_ey` has `length` `2*Neyi`. — Andras Deak -- Слава Україні, Jan 09 '16 at 22:07
@AndrasDeak I agree that the magic numbers are extra troublesome. I left them in there because I wasn't sure that the relationship between `xdim`, `ydim`, `zdim`, and `Nexi` and `Neyi` was known (hence why magic numbers are awful — Suever, Jan 09 '16 at 22:09
I think your code and approach is great as it is, I just meant to add that OP should probably say `Neyi=xdim * (ydim - 1) * zdim`. Clearer and safer. It was clear that you and I are on the same page regarding the subject:) — Andras Deak -- Слава Україні, Jan 09 '16 at 22:11
Yeah, @Andras, that's the Neyi, you are right! my total unknowns are around 0.8 billions and these loops are taking a long time.. that's why i asked the question here, thanks bud! — Jacks, Jan 10 '16 at 06:25
BTW, i used the preallocation, here, "if" is unnecessary, you are right. — Jacks, Jan 10 '16 at 06:27

score 2 · Accepted Answer · edited May 23 '17 at 11:54

Luckily for you, I considered this a programming puzzle, and deconvolved your code despite your reluctance to explain in clear terms what you wish to achieve. Here's a short solution, with a smaller test size:

xdim = 4;
ydim = 5;
zdim = 3;

% avoid magic numbers
Nexi = (xdim-1)*ydim*zdim;
Neyi = xdim*(ydim-1)*zdim;
Nezi = xdim*ydim*(zdim-1);

% preallocate
map_ex2 = zeros(1,Nexi);
map_ey2 = zeros(1,Nexi+Neyi);
map_ez2 = zeros(1,Nexi+Neyi+Nezi);


% index jump between blocks of the same variable
dN = ydim*zdim + (ydim-1)*zdim + (zdim-1)*ydim;

%construct matrices
map_ey2(Nexi+1:Nexi+Neyi) = ...
      permute(reshape(bsxfun(@plus,(1:xdim*zdim).',(0:ydim-2)*dN),...             %'
                      [zdim,xdim,ydim-1]),...
              [2 1 3]);
map_ez2(Nexi+Neyi+1:Nexi+Neyi+Nezi) = ...
      permute(reshape(bsxfun(@plus,(1:(zdim-1)*ydim).'+xdim*zdim,(0:xdim-1)*dN),...    %'
                      [zdim-1,ydim,xdim]),...
              [2 1 3]);
map_ex2(1:Nexi) = ...
      permute(reshape(bsxfun(@plus,(1:(xdim-1)*ydim).'+xdim*zdim+(zdim-1)*ydim,...    %'
                             (0:zdim-1)*dN),...
                      [xdim-1,ydim,zdim]),...
              [2 1 3]);

Running your original looping version and checking

isequal(map_ex,map_ex2)
isequal(map_ey,map_ey2)
isequal(map_ez,map_ez2)

tells me that this should do the same as what you're doing, only without any loops.

As you can see, I defined dynamic variables Nexi, Neyi, Nezi to avoid the use of magic numbers. I suggest that you adopt this behaviour.

The above solution is admittedly messy, but so was your original triple loop. There's a chance that @Divakar will come this way and give you a much more elegant/efficient solution;)

Yeah the question code looked like over-complicated for a comparatively simpler output. So, there might be a better way, but then OP has to simplify things to start off, as you have mentioned too in your comments. Great work though with `bsxfun`! — Divakar, Jan 10 '16 at 16:33

How to speed up a nested for loop code in Matlab

2 Answers2