{"id":3521,"date":"2019-12-19T08:43:01","date_gmt":"2019-12-19T13:43:01","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=3521"},"modified":"2019-12-19T08:43:21","modified_gmt":"2019-12-19T13:43:21","slug":"importance-of-implicit-expansion-for-performance","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2019\/12\/19\/importance-of-implicit-expansion-for-performance\/","title":{"rendered":"Importance of Implicit Expansion For Performance"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Sometimes people state that they like using MATLAB because it's easy to express their mathematical thoughts.  Sometimes there's a follow-on that they then switch to another language for performance.  While early in the history of MATLAB, that was sometimes beneficial, it is not so obvious these days.  Let's take the example of <a href=\"https:\/\/blogs.mathworks.com\/loren\/2016\/10\/24\/matlab-arithmetic-expands-in-r2016b\/\">implicit expansion<\/a> (also <a href=\"https:\/\/blogs.mathworks.com\/loren\/2016\/11\/10\/more_thoughts_about_implicit_expansion\/\">here<\/a>).<\/p><p>To maximize the benefits of implicit expansion, it's best if you have a more complicated, computationally expensive expression for MATLAB to work with while minimizing the need for temporary arrays.  MATLAB can then exploit coarse grain parallelism.  But it also depends on your computer and the array sizes you are using.  And it's worth thinking about code maintenance (for the future) and its complexity\/simplicity.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#71fc0fa1-965d-493d-afd6-10b2afe4a0af\">Demonstration<\/a><\/li><li><a href=\"#3af6740f-3f03-4e31-9b40-2842089a6420\">Thoughts<\/a><\/li><li><a href=\"#d15b5f12-409c-453e-a351-ba5388620ed1\">Which Code Do You Prefer, and Why?<\/a><\/li><\/ul><\/div><h4>Demonstration<a name=\"71fc0fa1-965d-493d-afd6-10b2afe4a0af\"><\/a><\/h4><p>Here is demonstration of this simple idea.  I'm testing equivalent numerical algorithms for removing the mean of any array and scaling it. Below are three equivalent implementations in MATLAB, the last one embeds a possible temporary array into one single line to take advantage of the most magic possible.  The first one uses the well-named <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/bsxfun.html\"><tt>bsxfun<\/tt><\/a> function.  The second one uses the same steps as the first, but uses implicit expansion instead.  And the third method combines some of the steps so there are fewer overall statements.  I'm calling this one smart.<\/p><pre class=\"codeinput\">n = [300, 1000, 3000, 10000];\r\nalltimes = zeros(length(n),4);\r\n<span class=\"comment\">%alltimes = table( \"size\", [length(n),4],...<\/span>\r\n<span class=\"comment\">%    \"VariableNames\",[\"n\", \"bsxfun\", \"implicit\",\"smart\"]);<\/span>\r\n<span class=\"keyword\">for<\/span> i = 1:length(n)\r\n   runtimes = testRemoveMeanAndScale(n(i));\r\n   alltimes(i,:) = [n(i), runtimes];\r\n<span class=\"keyword\">end<\/span>\r\nformat <span class=\"string\">short<\/span> <span class=\"string\">g<\/span>\r\nalltimesT = array2table(alltimes,<span class=\"string\">\"VariableNames\"<\/span>,[<span class=\"string\">\"n\"<\/span>, <span class=\"string\">\"bsxfun\"<\/span>, <span class=\"string\">\"implicit\"<\/span>,<span class=\"string\">\"smart\"<\/span>])\r\n<\/pre><pre class=\"codeoutput\">alltimesT =\r\n  4&times;4 table\r\n      n        bsxfun       implicit       smart   \r\n    _____    __________    __________    __________\r\n      300    0.00024632    0.00014821    7.5306e-05\r\n     1000       0.00322     0.0036559     0.0027499\r\n     3000      0.030063      0.036868      0.027908\r\n    10000        0.3469       0.38712       0.33361\r\n<\/pre><h4>Thoughts<a name=\"3af6740f-3f03-4e31-9b40-2842089a6420\"><\/a><\/h4><p>You can see that the timings are not completely consistent. It appears that as the arrays get larger, the smart algorithm consistently outperforms the other ones. Implicit expansion and <tt>bsxfun<\/tt> are generally on par except for small matrix sizes, where perhaps the extra function call costs enough extra to be noticeable.<\/p><h4>Which Code Do You Prefer, and Why?<a name=\"d15b5f12-409c-453e-a351-ba5388620ed1\"><\/a><\/h4><p>I'm wondering which code you'd prefer and I'd love to hear your reasons. Let me know <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=3521#respond\">here<\/a>.<\/p><pre class=\"language-matlab\">\r\n<span class=\"comment\">%% Test Functions<\/span>\r\n<span class=\"keyword\">function<\/span> runtime = testRemoveMeanAndScale(n)\r\n<span class=\"comment\">% This function tests the 3 algorithms we wish to compare w.r.t. speed.<\/span>\r\nrng(0);\r\nX = rand(n);\r\nmu = rand(1,n);\r\nsigma = randi([0 1],1,n);\r\nruntime(1) = timeit(@()bsxfunRemoveMeanAndScale(X, mu, sigma));\r\nruntime(2) = timeit(@()implicitExpansionRemoveMeanAndScale(X, mu, sigma));\r\nruntime(3) = timeit(@()smartRemoveMeanAndScale(X, mu, sigma));\r\n<span class=\"keyword\">end<\/span> <span class=\"comment\">% testRemoveMeanAndScale<\/span>\r\n\r\n<span class=\"keyword\">function<\/span> X = bsxfunRemoveMeanAndScale(X, mu, sigma) \r\n<span class=\"comment\">% Implementation using bsxfun<\/span>\r\nX = bsxfun(@minus, X, mu);\r\nsigma(sigma==0) = 1;\r\nX = bsxfun(@rdivide, X, sigma);\r\n<span class=\"keyword\">end<\/span> <span class=\"comment\">% bsxfunRemoveMeanAndScale<\/span>\r\n \r\n<span class=\"keyword\">function<\/span> X = implicitExpansionRemoveMeanAndScale(X, mu, sigma) \r\n<span class=\"comment\">% Use implicit expansion <\/span>\r\nX = X - mu;\r\nsigma(sigma==0) = 1;\r\nX = X .\/ sigma;\r\n<span class=\"keyword\">end<\/span> <span class=\"comment\">% implicitExpansionRemoveMeanAndScale<\/span>\r\n \r\n<span class=\"keyword\">function<\/span> X = smartRemoveMeanAndScale(X, mu, sigma) \r\n<span class=\"comment\">% Recommended implicit expansion implementation<\/span>\r\nsigma(sigma==0) = 1;\r\nX = (X - mu).\/ sigma;\r\n<span class=\"keyword\">end<\/span> <span class=\"comment\">% smartRemoveMeanAndScale<\/span>\r\n\r\n<\/pre><script language=\"JavaScript\"> <!-- \r\n    function grabCode_719862e8d49d430d97faa6cae2793cd7() {\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='719862e8d49d430d97faa6cae2793cd7 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 719862e8d49d430d97faa6cae2793cd7';\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 2019 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_719862e8d49d430d97faa6cae2793cd7()\"><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; R2019b<br><\/p><\/div><!--\r\n719862e8d49d430d97faa6cae2793cd7 ##### SOURCE BEGIN #####\r\n%% Importance of Implicit Expansion For Performance\r\n% Sometimes people state that they like using MATLAB because it's easy to\r\n% express their mathematical thoughts.  Sometimes there's a follow-on that\r\n% they then switch to another language for performance.  While early in the\r\n% history of MATLAB, that was sometimes beneficial, it is not so obvious\r\n% these days.  Let's take the example of\r\n% <https:\/\/blogs.mathworks.com\/loren\/2016\/10\/24\/matlab-arithmetic-expands-in-r2016b\/\r\n% implicit expansion> (also\r\n% <https:\/\/blogs.mathworks.com\/loren\/2016\/11\/10\/more_thoughts_about_implicit_expansion\/\r\n% here>).\r\n% \r\n% To maximize the benefits of implicit expansion, it's best if you have a\r\n% more complicated, computationally expensive expression for MATLAB to work\r\n% with while minimizing the need for temporary arrays.  MATLAB can then\r\n% exploit coarse grain parallelism.  But it also depends on your computer\r\n% and the array sizes you are using.  And it's worth thinking about code\r\n% maintenance (for the future) and its complexity\/simplicity. \r\n% \r\n%  \r\n%% Demonstration\r\n% Here is demonstration of this simple idea.  I'm testing equivalent\r\n% numerical algorithms for removing the mean of any array and scaling it.\r\n% Below are three equivalent implementations in MATLAB, the last one embeds\r\n% a possible temporary array into one single line to take advantage of the\r\n% most magic possible.  The first one uses the well-named\r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/bsxfun.html |bsxfun|>\r\n% function.  The second one uses the same steps as the first, but uses\r\n% implicit expansion instead.  And the third method combines some of the\r\n% steps so there are fewer overall statements.  I'm calling this one smart.\r\n \r\nn = [300, 1000, 3000, 10000];\r\nalltimes = zeros(length(n),4);\r\n%alltimes = table( \"size\", [length(n),4],...\r\n%    \"VariableNames\",[\"n\", \"bsxfun\", \"implicit\",\"smart\"]);\r\nfor i = 1:length(n)\r\n   runtimes = testRemoveMeanAndScale(n(i));\r\n   alltimes(i,:) = [n(i), runtimes];\r\nend\r\nformat short g\r\nalltimesT = array2table(alltimes,\"VariableNames\",[\"n\", \"bsxfun\", \"implicit\",\"smart\"])\r\n\r\n%% Thoughts\r\n% You can see that the timings are not completely consistent. It appears\r\n% that as the arrays get larger, the smart algorithm consistently\r\n% outperforms the other ones. Implicit expansion and |bsxfun| are generally\r\n% on par except for small matrix sizes, where perhaps the extra function\r\n% call costs enough extra to be noticeable.\r\n%\r\n%% Which Code Do You Prefer, and Why?\r\n% I'm wondering which code you'd prefer and I'd love to hear your reasons.\r\n% Let me know <https:\/\/blogs.mathworks.com\/loren\/?p=3521#respond here>.\r\n%\r\n% <include> testRemoveMeanAndScale.m <\/include>\r\n\r\n\r\n##### SOURCE END ##### 719862e8d49d430d97faa6cae2793cd7\r\n-->","protected":false},"excerpt":{"rendered":"<!--introduction--><p>Sometimes people state that they like using MATLAB because it's easy to express their mathematical thoughts.  Sometimes there's a follow-on that they then switch to another language for performance.  While early in the history of MATLAB, that was sometimes beneficial, it is not so obvious these days.  Let's take the example of <a href=\"https:\/\/blogs.mathworks.com\/loren\/2016\/10\/24\/matlab-arithmetic-expands-in-r2016b\/\">implicit expansion<\/a> (also <a href=\"https:\/\/blogs.mathworks.com\/loren\/2016\/11\/10\/more_thoughts_about_implicit_expansion\/\">here<\/a>).... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2019\/12\/19\/importance-of-implicit-expansion-for-performance\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[7,6,12],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/3521"}],"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=3521"}],"version-history":[{"count":2,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/3521\/revisions"}],"predecessor-version":[{"id":3527,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/3521\/revisions\/3527"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=3521"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=3521"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=3521"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}