{"id":781,"date":"2013-09-22T08:30:43","date_gmt":"2013-09-22T13:30:43","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=781"},"modified":"2017-08-28T20:16:57","modified_gmt":"2017-08-29T01:16:57","slug":"timing-code","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2013\/09\/22\/timing-code\/","title":{"rendered":"Timing Code"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p><i><b>and Revisiting Fibonacci Festival from 2006<\/b><\/i><\/p><p>I originally wrote about <a href=\"https:\/\/blogs.mathworks.com\/loren\/2006\/05\/17\/fibonacci-and-filter\/\">Fibonacci numbers<\/a> in 2006.  Today, along with Sarah Wait Zaranek, we'd like to discuss some of those same ideas, but focus only on execution time.  In R2013b, MATLAB includes a new timing function, <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/timeit.html\"><tt>timeit<\/tt>, one that I mentioned in some earlier posts when it was only available on the MATLAB File Exchange.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#2050a9f3-05d7-4ca7-81fe-ada76e846cef\">Using timeit<\/a><\/li><li><a href=\"#56691409-bcef-47cc-84db-1e0339c2b1b5\">Four Algorithms<\/a><\/li><li><a href=\"#bd4a00b7-57d5-4505-a1e3-6c20cf256b6d\">Straightforward for-loop<\/a><\/li><li><a href=\"#d5721e01-4cc2-4ac6-af7f-61122984bd6d\">for-loop with Preallocation<\/a><\/li><li><a href=\"#cdcae62b-fda8-41c3-9a51-8debc256ef70\">Recursive Function<\/a><\/li><li><a href=\"#c954dab5-6b28-4056-9006-88df897abed5\">Use filter to Calculate the Sequence<\/a><\/li><li><a href=\"#929e7cce-620d-47ae-9faf-ef5ed2d6997d\">Compare Computation Times<\/a><\/li><li><a href=\"#24c6891e-bae9-4259-95f1-0588809ea19c\">Do You Do Lots of Timing?<\/a><\/li><\/ul><\/div><h4>Using timeit<a name=\"2050a9f3-05d7-4ca7-81fe-ada76e846cef\"><\/a><\/h4><p>To use <tt>timeit<\/tt>, you simply pass in a <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/function-handles.html\">function handle<\/a> that requires no inputs.  If your function requires input values, you can pass them in by creating an anonymous function, where the values are captured from the current workspace. You can learn more about function handles in the MATLAB documentation, and find examples and discussions <a href=\"https:\/\/blogs.mathworks.com\/loren\/category\/function-handles\/\">on this blog<\/a>.<\/p><p><tt>timeit<\/tt> runs the code several times to ensure that any first-run timing effects do not affect the results - and returns the median time.  If you wish to time your function in the situation where it returns more than 0 or 1 output values, you can specify that as one of the inputs to <tt>timeit<\/tt>.<\/p><h4>Four Algorithms<a name=\"56691409-bcef-47cc-84db-1e0339c2b1b5\"><\/a><\/h4><p>In the earlier Fibonacci post, I introduce and times four algorithms. Today we will use the same algorithms, coded as separate programs, in conjunction with <tt>timeit<\/tt>.  Since we have four algorithms, we will initialize a vector for collecting the timing information.<\/p><pre class=\"codeinput\">fibTimes = zeros(1,4);\r\n<\/pre><h4>Straightforward for-loop<a name=\"bd4a00b7-57d5-4505-a1e3-6c20cf256b6d\"><\/a><\/h4><p>Let's calculate 102 Fibonacci values (since the first 2 are known already, <tt>[1, 1]<\/tt>).<\/p><pre class=\"codeinput\">nf = 102;\r\ntype <span class=\"string\">fibloop<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction fibs = fibloop(nf)\r\nfibs(1) = 1;\r\nfibs(2) = 1;\r\nfor n = 3:nf\r\n    fibs(n) = fibs(n-1)+fibs(n-2);\r\nend\r\n<\/pre><p>To use <tt>timeit<\/tt>, we simply give it a function handle to the function we wish to time.<\/p><pre class=\"codeinput\">fibTimes(1) = timeit(@()fibloop(nf));\r\n<\/pre><h4>for-loop with Preallocation<a name=\"d5721e01-4cc2-4ac6-af7f-61122984bd6d\"><\/a><\/h4><p>You've all heard it before.  One reason the former calculation took so much time is at least alleged to be because of growing the array <tt>fibf<\/tt> each time through the loop.  So now let's use the same loop, but preallocate the output array so it doesn't need to grow during the calculation.<\/p><pre class=\"codeinput\">type <span class=\"string\">fibloopPrealloc<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction fibs = fibloopPrealloc(nf)\r\nfibs = ones(1,nf);\r\nfor n = 3:nf\r\n    fibs(n) = fibs(n-1) + fibs(n-2);\r\nend\r\n\r\n\r\n<\/pre><p>Now time it.<\/p><pre class=\"codeinput\">fibTimes(2) = timeit(@()fibloopPrealloc(nf));\r\n<\/pre><h4>Recursive Function<a name=\"cdcae62b-fda8-41c3-9a51-8debc256ef70\"><\/a><\/h4><p>We can use recursion to calculate successive terms, as I showed in that earlier post.  Here's the code.<\/p><pre class=\"codeinput\">type <span class=\"string\">fibRecursive<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction fibs = fibRecursive(n)\r\nif n == 1,\r\n    fibs = 1;   % First element is 1.\r\n    return;\r\nelseif n == 2\r\n    fibs = [1 1];  % First two elements are 1.\r\nelse\r\n    % Call fibrec with previous result and compute next one from it.\r\n    fm1 = fibRecursive(n-1); \r\n    fibs = [fm1 fm1(end)+fm1(end-1)];\r\nend\r\n<\/pre><p>And now let's use it to calculate the first chunk of Fibonacci numbers.<\/p><pre class=\"codeinput\">fibTimes(3) = timeit(@()fibRecursive(nf));\r\n<\/pre><h4>Use filter to Calculate the Sequence<a name=\"c954dab5-6b28-4056-9006-88df897abed5\"><\/a><\/h4><p>I also explained in the earlier Fibonacci post how to use <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/filter.html\"><tt>filter<\/tt><\/a> to calculate the sequence as well.  Here's the code.<\/p><pre class=\"codeinput\">type <span class=\"string\">fibFilter<\/span>\r\nfibTimes(4) = timeit(@()fibFilter(nf));\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction fibf = fibFilter(n)\r\nx = [1 zeros(1,n-1)];\r\na = [1 -1 -1];\r\nb = 1;\r\nfibf = filter(b, a, x);\r\n<\/pre><h4>Compare Computation Times<a name=\"929e7cce-620d-47ae-9faf-ef5ed2d6997d\"><\/a><\/h4><p>It's time to see how quickly the various methods performed. We have multiplied the times by 1000 to make reading the numbers easier.<\/p><pre class=\"codeinput\">fprintf(<span class=\"string\">'%s\\n\\n'<\/span>,<span class=\"string\">'Compare Times (in milliseconds)'<\/span>)\r\nmeths = [<span class=\"string\">'loop           '<\/span>,<span class=\"keyword\">...<\/span>\r\n         <span class=\"string\">'prealloc       '<\/span>,<span class=\"keyword\">...<\/span>\r\n         <span class=\"string\">'recursive      '<\/span>,<span class=\"keyword\">...<\/span>\r\n         <span class=\"string\">'filter         '<\/span>];\r\nfprintf(<span class=\"string\">'%s\\n\\n'<\/span>,meths)\r\nfprintf(<span class=\"string\">'%2.9f    '<\/span>, fibTimes*1000), fprintf(<span class=\"string\">'\\n'<\/span>)\r\n<\/pre><pre class=\"codeoutput\">Compare Times (in milliseconds)\r\n\r\nloop           prealloc       recursive      filter         \r\n\r\n0.040766819    0.010003257    0.517234655    0.010549081    \r\n<\/pre><h4>Do You Do Lots of Timing?<a name=\"24c6891e-bae9-4259-95f1-0588809ea19c\"><\/a><\/h4><p>Do you do lots of timing?  How do you do it? <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/matlab_prog\/profiling-for-improving-performance.html#f9-17126\">Profiler<\/a>?  Will <tt>timeit<\/tt> help?  Let us know <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=781#respond\">here<\/a>.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_71c4e7314a9840f0ae2878900c8754c1() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='71c4e7314a9840f0ae2878900c8754c1 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 71c4e7314a9840f0ae2878900c8754c1';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2013 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_71c4e7314a9840f0ae2878900c8754c1()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2013b<br><\/p><p class=\"footer\"><br>\r\n      Published with MATLAB&reg; R2013b<br><\/p><\/div><!--\r\n71c4e7314a9840f0ae2878900c8754c1 ##### SOURCE BEGIN #####\r\n%% Timing Code\r\n%\r\n% _*and Revisiting Fibonacci Festival from 2006*_\r\n%\r\n% I originally wrote about\r\n% <https:\/\/blogs.mathworks.com\/loren\/2006\/05\/17\/fibonacci-and-filter\/\r\n% Fibonacci numbers> in 2006.  Today, along with Sarah Wait Zaranek, we'd\r\n% like to discuss some of those same ideas, but focus only on execution\r\n% time.  In R2013b, MATLAB includes a new timing function,\r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/timeit.html |timeit|>, one that\r\n% I mentioned in some earlier posts when it was only available on the\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/18798-timeit-benchmarking-function\r\n% MATLAB File Exchange>.\r\n%% Using timeit\r\n% To use |timeit|, you simply pass in a\r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/function_handle.html function\r\n% handle> that requires no inputs.  If your function requires input\r\n% values, you can pass them in by creating an anonymous function, where the\r\n% values are captured from the current workspace. You can learn more\r\n% about function handles in the MATLAB documentation, and find examples and\r\n% discussions <https:\/\/blogs.mathworks.com\/loren\/category\/function-handles\/\r\n% on this blog>.\r\n%\r\n% |timeit| runs the code several times to ensure that any first-run timing\r\n% effects do not affect the results - and returns the median time.  If you\r\n% wish to time your function in the situation where it returns more than 0\r\n% or 1 output values, you can specify that as one of the inputs to\r\n% |timeit|.\r\n\r\n%% Four Algorithms\r\n% In the earlier Fibonacci post, I introduce and times four algorithms.\r\n% Today we will use the same algorithms, coded as separate programs, in\r\n% conjunction with |timeit|.  Since we have four algorithms, we will\r\n% initialize a vector for collecting the timing information.\r\nfibTimes = zeros(1,4);\r\n%% Straightforward for-loop\r\n% Let's calculate 102 Fibonacci values (since the first 2 are known\r\n% already, |[1, 1]|).\r\nnf = 102;\r\ntype fibloop\r\n%%\r\n% To use |timeit|, we simply give it a function handle to the function we\r\n% wish to time.\r\nfibTimes(1) = timeit(@()fibloop(nf));\r\n\r\n%% for-loop with Preallocation\r\n% You've all heard it before.  One reason the former calculation took so\r\n% much time is at least alleged to be because of growing the array |fibf|\r\n% each time through the loop.  So now let's use the same loop, but\r\n% preallocate the output array so it doesn't need to grow during the\r\n% calculation.  \r\ntype fibloopPrealloc\r\n%%\r\n% Now time it.\r\nfibTimes(2) = timeit(@()fibloopPrealloc(nf));\r\n\r\n%% Recursive Function\r\n% We can use recursion to calculate successive terms, as I showed in that\r\n% earlier post.  Here's the code.\r\ntype fibRecursive\r\n%%\r\n% And now let's use it to calculate the first chunk of Fibonacci numbers.\r\nfibTimes(3) = timeit(@()fibRecursive(nf));\r\n\r\n%% Use filter to Calculate the Sequence\r\n% I also explained in the earlier Fibonacci post how to use\r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/filter.html |filter|> to\r\n% calculate the sequence as well.  Here's the code.\r\ntype fibFilter\r\nfibTimes(4) = timeit(@()fibFilter(nf));\r\n\r\n%% Compare Computation Times\r\n% It's time to see how quickly the various methods performed.\r\n% We have multiplied the times by 1000 to make reading the numbers easier.\r\nfprintf('%s\\n\\n','Compare Times (in milliseconds)')\r\nmeths = ['loop           ',...\r\n         'prealloc       ',...\r\n         'recursive      ',...\r\n         'filter         '];\r\nfprintf('%s\\n\\n',meths)\r\nfprintf('%2.9f    ', fibTimes*1000), fprintf('\\n')\r\n%% Do You Do Lots of Timing?\r\n% Do you do lots of timing?  How do you do it?\r\n% <https:\/\/www.mathworks.com\/help\/matlab\/matlab_prog\/profiling-for-improving-performance.html#f9-17126\r\n% Profiler>?  Will |timeit| help?  Let us know\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=781#respond here>.\r\n\r\n\r\n##### SOURCE END ##### 71c4e7314a9840f0ae2878900c8754c1\r\n-->","protected":false},"excerpt":{"rendered":"<!--introduction--><p><i><b>and Revisiting Fibonacci Festival from 2006<\/b><\/i>... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2013\/09\/22\/timing-code\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[16,6,58],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/781"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=781"}],"version-history":[{"count":7,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/781\/revisions"}],"predecessor-version":[{"id":2407,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/781\/revisions\/2407"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=781"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=781"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=781"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}