× {{alert.msg}} Never ask again
Get notified about new tutorials RECEIVE NEW TUTORIALS

Improve performance by extracting repeated calculations outside of loop bodies

Michael Safyan
Mar 27, 2016
<p>You may have learned in your algorithms course that first order constants do not affect the asymptotic runtime complexity of an algorithm. While this is true, this may have led to the false impression that first order constants don't matter. Once you have selected the algorithm with the best asymptotic runtime complexity, improving first order constants can be the difference between smooth, 60 frames-per-second animations and jank; it can be the difference between your calculation completing quickly enough to be responsive to users and your calculation being perceptibly slow. For this reason, it is important to not only understand how to select a better algorithm, but also how to perform micro-optimizations, as well.</p> <p>When improving first order constants, loops are the best places to look, as any performance issues are magnified by the number of times the loop is executed. One common inefficiency in loops is to repeat calculations unnecessarily:</p> <pre><code class="language-java">for (Employee e : company.getEmployees()) { employeeToCompanyName.put(e, company.getName()); }</code></pre> <p>In the loop above, even if "company.getName()" is relatively efficient, it still involves the extra overhead of invoking a function. We can speed up this calculation simply by doing the calculation only once and saving the result locally:</p> <pre><code class="language-java">String companyName = company.getName(); for (Employee e : company.getEmployees()) { employeeToCompanyName.put(e, companyName); }</code></pre> <p>The savings of this operation are magnified, the slower and more inefficient the operation; however, even when the calculation is relatively efficient (e.g., simply returning a literal or returning a member variable, vs doing a more signficant calculation), the effort to extract calculations out of loops is small enough that it is worth getting into the habit of doing when writing code in the first place. This also shields the code from becoming impacted heavily by relatively small increases in the complexity of the functions that are being used repeatedly (since they are now called only once).</p> <p>Although the examples above use Java, this principle applies to other languages, as well. </p>
comments powered by Disqus