Question to MATLAB profiler and speed of code (spline calculation during optimization)

Hello dear MATLAB community,

I have a question concerning this piece of code

This will calculate a piecewise cubic spline for my parametrized function. It is calles so often because it´s inside an optimization routine (fmincon). My first question is: Is there a way to speed up this code? And the second question: Why is the runtime of line 11 and 13 and 12 and 14 so different? Both lines are doing the same operation but the the calculation time differs around 30%?

Thanks for your help,

David

[Sean de Wolski]

What optimizer are you using with what settings?

[David]

I´m using fmincon with the following settings:

 iter = 100000;
 opts = optimset('fmincon');
 opts.Display = 'iter';
 opts.Algorithm = 'interior-point';
 opts.MaxSQPIter = iter;
 opts.MaxIter = iter;
 opts.MaxFunEvals = 150000;

[y(:,1),fval(1,1)] = fmincon(@myfun, x0,A,b,[],[],lb,[],[], opts);

I already tried to use other algorithms then interior-point but none of them were as good as the interior-point algorithm.

[Sean de Wolski]

Interior point is usually the best. I question of the spline calculations are highly unstable (a trait of splines) that could be causing the optimizer to have trouble.

Answer 1

[Stephen23]

Two questions... two answers.

1) Probably. But this depends mostly on the two functions griddedInterpolant and F1 / F3, about which you have not provided us with any information. For example it might be possible to call these functions only once each, if griddedInterpolant can accept a matrix for its second input. It might also be faster to interpolate the data directly, without creating the intermediate functions F1 / F3.

2) MATLAB is an interpreted language with some sophisticated memory and data management. I am certainly no expert on this topic (someone from MATLAB could help you), but this apparently includes optimization of functions when they are first called, allocating memory and checking if the data changes during the code. These first steps add a little time when code is first run, or a function is first called. Those times look fine.

[David]

Thank you for your answer Stephen,

to your first answer:

Yes your right. As griddedInterpolant is a MATLAB internal function I should probably have a look at it or maybe somone else has a hint for this?

To your second answer: I also thought of this possibility that functions need more time when they are first called, but I also figured out, that there are functions that need more time when they are called the second or third time.

Again this two lines are doing exactly the same but the second line takes 50% longer to execute. I don´t know why but this makes no sense to me.

David

[Stephen23]

With such a short time intervals, it is likely that those times are not very repeatable. If you run the code a few times or on a different computer, or run some other programs on the same computer, those times could easily change.

You could try different interpolation functions, and compare their computation times. Note that all(?) MATLAB interpolation functions accept matrices too!

[David]

Also tried different interpolation functions but couldn´t find a better/faster solution.

Does anybody probably has another hint?

[Sean de Wolski]

The profiler introduces some variation in computation times. If you want very explicit computation times, use tic/toc.

[David]

Yes I also did this. But even with tic/toc the same computation task takes sometimes twice as long as before. First example two times the same calculation:

Elapsed time is 0.000101 seconds.
Elapsed time is 0.000068 seconds.

Second example four times the same calculation for another piece of code:

Elapsed time is 0.000019 seconds.
Elapsed time is 0.000018 seconds.
Elapsed time is 0.000009 seconds.
Elapsed time is 0.000007 seconds.

[Sean de Wolski]

How many times do you have to run this? I mean at 0.000019s it'll have to run 52000x to take a second.

[David]

As this is a call during an optimization routine it is sometimes called more than 100.000 times. So even small optimizations of less than 1ms can have a big influence to the total computation time.

Answer 2

[Marco]

EDIT: Please ignore this answer, I realized that my answer wasn´t a good answer, because lines 11 and 13 actually do not differ in respect to row and column access.

The answer was: About the difference in calculation speed in lines 11 and 13, I would expect that this has to do with the way how MATLAB stores the data in the memory of the hardware. It is said for MATLAB, that data stored in columns can consecutively be accessed faster by the hardware than the harware could consecutively access data being stored in rows. This is how The Mathworks implemented MATLAB. For other software this could be the opposite round. It depends on the specific low level implementation of the software. Here is a link to some MATLAB information about this: programming-patterns-maximizing-code-performance-by-optimizing-memory-access

Answer 3

[Sean de Wolski]

You can do this with one call to griddedInterpolant or interp1 (which builds a griddedInterpolant under the hood). Build it once and evaluate it on [x2 x2]. Since splines are calculated in one dimension anyway.

The call to interp1 would look like this:

% Simulated data
xges = cumsum(rand(10,2));
xi = 1:10; % index
xq = 1:0.1:10; % query

% x2 is first column, y2 is second
x2y2 = interp1(xi.',xges,xq.'); % interp

[David]

The calculation of the spline with one call to interp1 is still slower than the two calls with griddedInterpolant. How could I do the spline interpolation with one call to griddedInterpolant?

[Sean de Wolski]

Swap out its values after using it the first time:

x2 = F(xq)
F.Values = xges(:,2)
y2 = F(xq)

This at least doesn't require rebuilding all of it.

[David]

Okay this works!

But an interesting fact is...that this is also slower than the 2 calls to griddedInterpolant :D

13.3s %with with your code

12.1s %with the original code on the top

(This is the total time for the optimization. During this optimization the code ran 40.000 times)

[Sean de Wolski]

Run each a few more times. Is there anything stochastic about the system/objective function/etc.?

[David]

The result of the optimization is always the same. The duration of both stays always nearly the same (+- 0.2s). The original code is always faster than your proposed solution (always around 1s).

Answer 4

[Philip Borghesani]

Your attempted pre-allocation by calling zeros for xj and yj is not doing anything useful and may be costing a small amount of time try just a simple assignment and removing the calls to zeros:

 xj=F1(x2);
 yj=F3(x2);

There is never a benefit to preallocating something if a following assignment is going to write into the entire variable.

[David]

Thank you Philip for your answer.

I also thought of this possibility to save this computing time, but actually it doesn´t change anything. What I could figure out is that the pre-allocation needs time but only when profiling it. Measuring the whole optimization process with tic/toc leads to this times:

Elapsed time is 11.189407 seconds. %With pre-allocation
Elapsed time is 11.185134 seconds. %Without pre-allocation

This is actually the same time for both calculations.

But indeed your right the pre-allocation doesn´t give any benefit.

Small EDIT on this point:

After rerunning the optimization a lot of times you could see a small speed up without the pre-allocation (around 0.05s)

Answer 5

[Sean de Wolski]

Interior point is usually the best algorithm (hence why we made it the default!).

I question if the spline calculations are highly unstable (a trait of splines) and that this could be causing the optimizer to have trouble. This being the reason for the huge number of function evaluations.

Also, it wouldn't surprise me at all if the actual display iter setting is causing much of the time as printing to the command line is slower than computation. Try turning that off and rerunning.

[David]

If i take a closer look into all calculations that the optimizer has done, then it seems like the spline calculation is pretty stable. The picture shows all calculated lines during the optimization and the red line is the optimum.

I also tried to turn off the display settings but there was no speed up. I achieve (sometimes) a significant speedup when setting the parameter

opts.TolFun = 0.05;

to a higher value then the default one. But this is very risky because of course sometimes the results gets very bad. I try to set up a logic in front of this parameter to set it dynamically.

[David]

Actually I think there is no possibility to speed up the calculation of a cubic spline in MATLAB. The function griddedInterpolant is way the fastest function to calculate the spline (as far as I have found).

Nevertheless I could speed up my code around 30%! I made another calculating condition for fmincon which leads to the same results but without looping 100.000 times.

Thanks to all who helped me!