How to reduce execution time in nested for loops and struc. arrays

I have the following code, it is part of a much larger one. The total execution time for the whole code is around 50 sec. I am trying to reduce this figure to few secs. So the first thing is I started to look for for loops to reduce.

The following part of the code is taking 33 sec. (more than half the total time) and I am only creating strucs. arrays

NOC=100;                        
NOBS=2;                         
NORB_PER_BS=5;                  
NOU=200 ;                       
    for k=1:NOU                  
        U1(k).SINR_MAX=0;       
        U1(k).SINR_F_AVG=0;     
        U1(k).v=[];             
        U1(k).w=[];             
        U1(k).SINR_IND={};      
        U1(k).ASSIGNED=0;       
        U1(k).SINR_MAX_CANDIDATES=[];
        for n=1:NORB_PER_BS     
            for b=1:NOBS       
                for v=1:NOU     
                    U(k,n,b).Q_LIST=[];         
                    U(k,n,b).Q_LIST1=[];        
                    U(k,n,b).Q_LIST_MEMBERS=[]; 
                    U(k,n,b).Q_MIN_MEMBERS=[];  
                    U(k,n,b).Q_MIN=[];
                    SINR(k,n,b)=0;              
                end
            end
        end
    end

[Walter Roberson]

why are you for v when the code being executed does not depend on v?

[Guillaume]

In addition to Walter's comment, is the structure array preinitialised? Or is it resized at each step of the loops (a major cause of slow-down)?

Does your real code just assign the same value for each element? In that case, why use a loop when you could just repmat a constant scalar structure?

Oh, and just notice that NOC is never used.

[Mohammed Hadi]

@walter

Thanks for pointing that out. I kept editing the code and forgot to remove this part.

-------------------------------------------------------

@Gulliaume

The struc. array is not pre-initialized. I am using these loops to initialize it and make sure all are zeros.

The size of

U(k,n,b).Q_LIST=[];

U(k,n,b).Q_LIST1=[];

U(k,n,b).Q_LIST_MEMBERS=[];

U(k,n,b).Q_MIN_MEMBERS=[];

U(k,n,b).Q_MIN=[];

changes in the steps folllowing this part

Sorry for the NOC, yes you are corrent it is not used here but used in the following steps.

Answer 1

[Guillaume]

Your current code is equivalent to:

U = struct('SINR_MAX', num2cell(zeros(1, NOU)), 'SINR_F_AVG', 0, 'v', [], 'w', [], 'SINR_IND', {{[]}}, 'ASSIGNED', 0, 'SINR_MAX_CANDIDATES', []);
U1 = struct('Q_LIST', cell(NOU, NORB_PER_BS, NOBS), 'Q_LIST1',[], 'Q_LIST_MEMBERS', [], 'Q_MIN_MEMBERS', [], 'Q_MIN', []);
SINR = zeros(NOU, NORB_PER_BS, NOBS);

[Mohammed Hadi]

Dear Guillaume,

Many thanks for the help.

I tried this code and it just required swapping the U and U1.

The execution time is now 0.03 sec. for this part (was 33 sec).

the total execution time is now (17 sec) was (50 sec).

I still need to verify if the assignment mechanisim still accurate. However, I am very grateful for the help.

I wonder if you can please provide some links on such techniques ? I still have to lower this time down to few seconds.

[Guillaume]

I should have said "is the structure array preallocated?" instead of preinitialised. That's probably the biggest killer in performance.

If you do this (demonstrating with an array of double as it is simpler):

%array A does not exist prior to this. It is not preallocated
for row = 1:M
    for col = 1:N
        A(row, col) = something;
    end
end

What happens is:

• on the first step of the loop, matlab sees that A does not exists. Since you want to assign to A(1, 1), matlab creates A as a 1x1 array and puts something into it
• on the next step, matlab sees that A exists and is 1x1. Since you want to assign to A(1, 2), matlab sees it is too small. At this point, what it does is create a new 1x2 array, copy the first value into it, discard the old array and set the last element to something.
• And so on, each time the array is too small, so matlab creates a new one, copy the old content, and discard the old array.

Growing an array in a loop is extremely inefficient. The simplest way to avoid that is by preallocating the array. For double, it's trivially done by adding just one line before the loop:

A = zeros(M, N);  %preallocation
for row = 1:M
    for col = 1:N
        A(row, col) = something;
    end
end

Then the loop just fills the existing array.

For structure arrays, preallocation is done with struct. Since you're putting the same value in each element of the structure array, you can preallocate the structure directly with the right values as I have done, thus avoiding the loops entirely.

[Mohammed Hadi]

Dr.Guillaume

Many thanks for the explanation that really helped alot.

I have another set of for loops (nested) to allocate wireless channels to users. and used those strucs for that purpose.

Now., the overall time to serve 200 users is around 17 sec. (was 50)

Wonder if you can highlight other techniques that one can use to reduce this time even further?

Thanks again.

[Guillaume]

That really depends on what is going on in the loops. Sometimes, there's no way to gain any speed other than completely changing the algorithm.

[Walter Roberson]

And sometimes it is several centuries of research to find a better algorithm. Or to prove that no better algorithm exists (only implementation details.)