Huge overhead in fsolve due to fsolve>createExitMsg()

Is it just me or is the fancy exit messaging in fsolve creating huge overhead?I imagine this might impact other optim toolbox functions but I have only tested with fsolve so far. The profiler shows approx. 35% of the fsolve run time spent in a call to fsolve>createExitMsg. Replacing the two relevant lines with something like the below resulted in about 30% overall speedup in my problem (calling fsolve many times in a loop):

if EXITFLAG > 0 % if we think we converged:
  % Call createExitMsg with appended additional information on the closeness
  % to a root.
  if Resnorm > sqrtTolFunValue
      msgData = internalFlagForExitMessage(algorithmflag == 2,msgData,EXITFLAG);
      EXITFLAG = -2;
  end  
  %OUTPUT.message = createExitMsg(msgData{:},Resnorm,optionFeedback.TolFunValue,sqrtTolFunValue);
  OUTPUT.message = msgData;
else
  %OUTPUT.message = createExitMsg(msgData{:});
  OUTPUT.message = msgData;
end

In the above I commented out the offending calls and replaced with just saving the msgData cell.

Questions:

1. Is anyone else seeing this behavior
2. Is my replacement likely to break something in unexpected ways?
3. Since we're talking optimization, the optimget function is another overhead hog, taking about 10% of the remaining run time! But maybe I'll start a separate thread for that one.

Answer 1

[Steve Grikschat]

An update:

This was changed in all solvers in R2018a. Now, the message is not made if it is not requested, i.e. if

• options.Display is set to 'off' or 'none' and
• the output structure is not included in the list of outputs

The changes above improve performance on small, fast-to-solve problems.

Additionally, if no options are given, the calls to optimget are essentially bypassed. This also improves performance in cases like the above.

Here is some timing data I got from running R2018b on my machine:

opts = optimoptions(@fsolve);
n=10; A=rand(n); b = rand(n,1); x0=rand(n,1);

% Run once for JIT effect
fsolve(@(x) A*x - b, x0,opts);

% Time baseline - with options and display on
tic
for k = 1:20
    fsolve(@(x) A*x - b, x0,opts);
end
tBase = toc;

opts.Display = 'none';

tic
for k = 1:20
    fsolve(@(x) A*x - b, x0,opts); 
end
tNoDisplay = toc;

tic
for k = 1:20
    fsolve(@(x) A*x - b, x0); 
end
tNoOpts = toc;
tBase, tNoDisplay, tNoOpts

With output

tBase =

    0.0926


tNoDisplay =

    0.0578


tNoOpts =

    0.0770

Answer 2

[Matt J]

You must have a really small problem size for createExitMsg to make such a large percentage contribution. In something like the following, for example, I see negligible contribution from createExitMsg in the profiler (R2017a)

    opts1=optimoptions(@fsolve,'algorithm','levenberg-marquardt');

    n=200; A=rand(n); x0=rand(n,1); 

    tic; fsolve(@(x) norm(A*x)^2, x0,opts1); toc;

It is interesting, though, that the exit message is always created, even when the 'Display' option is set to 'none' and the 4th output argument is not requested.

[Naor Movshovitz]

@Matt, yes I noticed too that the exit message is created but left unused in many cases. After commenting out unnecessary (in my case) calls to createExitMsg the profiler shows 10% of the remaining cost of fsolve is in calls to optimget :)

A use case that leads to this overhead being an issue is a small problem size, e.g. a system of 4 non-linear equations in 4 unknowns, with coefficients that are dynamically recalculated many times in the overall problem. So fsolve is called in a loop to operate on a small vector.

[Steve Grikschat]

Hi Naor,

Thanks for reporting this. We're taking a look at fixing it systematically now.

Your change shouldn't break anything unless you want the "message" field of the "output" structure from the solver. My guess is that you don't need it, so you should be ok.

About optimget, we're also looking at that as well. If you are not passing any options to fsolve, one possible speedup is to create a default* options set 1x and pass it each time.

• You can use either

options = optimoptions('fsolve');
% or
options = optimset('fsolve');

[Wade Hilts]

Any progress on this update? It's even worse for using quadprog() because it calls the getExitMsg.p file which cannot be edited :(

Very inefficient code!

[Steve Grikschat]

@Wade: see the update in the Answer below.