A specific line of a .m file slows down the speed (potential bottleneck?)

Hello there,

I have encountered an unexpected problem, while i am trying to implement an AC-3 algorithm in MATLAB. It's an AI algorithm, to achieve local consistency for networks of binary constraints.

Well, firstly, let me explain this to you. In general, what i am trying to do here, is check whether an "arc" (xi,xj) of variables already exists or not in a FIFO queue called Q. If yes, i do nothing. If it does not already exists, i have to insert the arc into the Q(into the back, FIFO-style) and use break to exit the if statement. I hope that it is pretty much clear until now.

To add this arc (xi,xj) to the Q, i use a replicated matrix Q2, just like Q, which holds all the arcs of type (xi,xj) the whole time, while the initial Q is making some deletions of arcs through the iterations of a for loop, following the theory of the AC-3 algorithm.

There is the code the problem is located:

for m=1:length(Q2)
       alreadyExists = any(cellfun(@(x) isequal(x, Q2{m}), Q)); 
         if alreadyExists==0;     
            fprintf('\nRe-entering in Q arc(x%d,x%d)...\n',Q2{m}(1),Q2{m}(2));
            Q{end+1}=[Q2{m}];
            re_enteringQ_cntr=re_enteringQ_cntr+1; 
            break;
         end
end

So what i am doing in line:

   alreadyExists = any(cellfun(@(x) isequal(x, Q2{m}), Q));

Is just to compare every arc (xi,xj) stored in Q2 with x, a variable returned by another function, which is also another arc.

And here is the problem, using profile viewer on MATLAB:

It is really weird. About ~70 million calls this specific code in nearly 12 minutes of "real" time?! I did Ctrl+C to stop the program, as it seemed it would be executed for a really long time.This cannot be right of course, it is a kind of bottleneck and I can not find any solution until now.

To catch you up guys, in every function and .m file of my whole algorithm i do preallocations for all the matrices, cell arrays and vectors i use, in order to boost up the speed.

Any ideas, any thoughts and/or feedback would be really appreciated.

Thank you in advance for your time.

Answer 1

[Stephen23]

Idea 1: remove cellfun and use a loop: this is usually faster. cellfun makes tidy code, but is slow.

Idea 2: ditch the cell array completely. From a speed point of view cell arrays should really only be used only when data cannot be stored together numeric/char/.. arrays, as accessing them will always be much slower. If you replace the cell array with the appropriately sized numeric then testing if an "arc" exists will be very quick as you can take advantage of scalar comparison, as long as the number of values in each arc is known beforehand (yours seem to have two elements):

any(x==X) && any(y==Y)

will be much faster than using cellfun and isqual. Store the data in a simple two-column numeric array and use the appropriate indexing. If you really are attempting to write for speed then avoid cell arrays and vectorize code where you can.

[Nik hat]

Thank you for the reply, i may try to implement your second idea.

Answer 2

[Steven Lord]

Realize that about 70 million calls in about 12 minutes boils down to about 100,000 calls per second.

Rather than checking each item one at a time and adding them one at a time, consider using the set functions (SETDIFF) to check ALL of the items at once, then adding any of the items that need to be added once.