How can I precisely profile /benchmark algorithms in MATLAB?

Question

The algorithm repeats the same thing again-and-again. I expected to get the same time in each trial but I got very unexpected times for the four identical trials

in which I expected the curves to be identical but they act totally differently. The reason is probably in the tic/toc precision.

• What kind of profiling/timing tools should I use in Matlab?
• What am I doing wrong in the below code? How reliable is the tic/toc profiling?
• Anyway to guarantee consistent results?

Algorithm

A=[];
for ii=1:25
    tic;
    timerval=tic;
    AlgoCalculatesTheSameThing();    
    tElapsed=toc(timerval);
    A=[A,tElapsed];   
end

Answer 1

You should try timeit.

Have a look at this related question:

How to benchmark Matlab processes?

A snippet from Sam Roberts answer to the other question:

It handles many subtle issues related to benchmarking MATLAB code for you, such as:

• ensuring that JIT compilation is used by wrapping the benchmarked code in a function
• warming up the code
• running the code several times and averaging

Have a look at this question for discussion regarding warm up:

Why does Matlab run faster after a script is "warmed up"?

Update:

Since timeit was first submitted at the fileexchange, the source code is available here and can be studied and analyzed (as opposed to most other MATLAB functions). From the header of timeit.m:

%   TIMEIT handles automatically the usual benchmarking procedures of "warming
%   up" F, figuring out how many times to repeat F in a timing loop, etc.
%   TIMEIT also compensates for the estimated time-measurement overhead
%   associated with tic/toc and with calling function handles.  TIMEIT returns
%   the median of several repeated measurements.

You can go through the function step-by-step. The comments are very good and descriptive in my opinion. It is of course possible that Mathworks has changed parts of the code, but the overall functionality is there.

For instance, to account for the time it takes to run tic/toc:

function t = tictocTimeExperiment
% Call tic/toc 100 times and return the average time required.

It is later substracted from the total time.

The following is said regarding number of computations:

function t = roughEstimate(f, num_f_outputs)
%   Return rough estimate of time required for one execution of
%   f().  Basic warmups are done, but no fancy looping, medians,
%   etc.

This rough estimate is used to determine how many times the computations should run.

If you want to change the number of computation times, you can modify the timeit function yourself, as it is available. I would recommend you to save it as my_timeit, or something else, so that you avoid overwriting the built-in version.

Answer 2

Qualitatively there are large differences between the same runs. I did the same four trials as in the question and tested them with the methods suggested so far and I created my own version of the timeit timeitH because the timeit has too large standard deviation between different trials. The timeitH returns far more robust results to other methods because it warm ups the code similarly to the timeit and then it has increased the amount of outer loops in the original timeit from 11 to 50.

The below has the four trials done with the three different methods. The closer the curves are to each other, the better.

TimeitH: results pretty good!

Some observations.

1. timeit: result smoothed but bumps
2. tic/toc: easy to adjust for larger cases to get the standard deviation smaller in computation times but no warming up
3. timeitH: download the code and change 60th line to num_outer_iterations = 50; to get smoother results

In summarum

I think the timeitH is the best candidate here, yet only tested in evaluating sparse polynomials. The timeit and tic/toc like 500 times do not result into robust results.

Timeit

500 trials and average with tic/toc

Algorithm for the 500 trials with tic/toc

for ii=1:25
    numTrials = 500;
    tic;
    for ii=1:numTrials
        AlgoCalculatesTheSameThing();   
    end
    tTotal = toc;  
    tElapsed = tTotal/numTrials;
    A=[A,tElapsed];   
end

Answer 3

Is the time for AlgoCalculatesTheSameThing() relatively short (fractions of sec or a few sec) or long (multi-minutes or hours)? If the former I would suggest doing it more like this: move your timing functions outside your loop, then compute averages:

A=[];
numTrials = 25; 
tic;
for ii=1:numTrials
    AlgoCalculatesTheSameThing();     
end
tTotal = toc;
tAvg = tTotal/numTrials;

If the event is short enough (fraction of sec) then you should also increase the value of numTrials to 100s or even 1000s.

You have to consider that with any timing function there will be error bars (like in any other measurement). If the event your timing is short enough, the uncertainties in your measurement can be relatively big, keeping in mind that the resolution of tic and toc also has some finite value.

More discussion on the accuracy of tic and toc can be found here.

You need to work out these uncertainties for your specific application, so do experiments: perform averages over a number of trials and then compute the standard deviation to get a sense of the "scatter" or uncertainly in your results.