Program optimization: Difference between revisions

Revision as of 10:16, 14 November 2023

Revision as of 05:02, 22 November 2023

Line 56:

===Platform dependent and independent optimizations===

Code optimization can be also broadly categorized as [[computer platform|platform]]-dependent and platform-independent techniques. While the latter ones are effective on most or all platforms, platform-dependent techniques use specific properties of one platform, or rely on parameters depending on the single platform or even on the single processor. Writing or producing different versions of the same code for different processors might therefore be needed. For instance, in the case of compile-level optimization, platform-independent techniques are generic techniques (such as [[loop unwinding|loop unrolling]], reduction in function calls, memory efficient routines, reduction in conditions, etc.), that impact most CPU architectures in a similar way. A great example of platform-independent optimization has been shown with inner for loop, where it was observed that a loop with an inner for loop performs more computations per unit time than a loop without it or one with an inner while loop.<ref>{{Cite journal|last=Adewumi|first=Tosin P.|date=2018-08-01|title=Inner loop program construct: A faster way for program execution|journal=Open Computer Science|language=en|volume=8|issue=1|pages=115–122|doi=10.1515/comp-2018-0004|doi-access=free}}</ref> Generally, these serve to reduce the total [[instruction path length]] required to complete the program and/or reduce total memory usage during the process. On the other hand, platform-dependent techniques involve instruction scheduling, [[instruction-level parallelism]], data-level parallelism, cache optimization techniques (i.e., parameters that differ among various platforms) and the optimal instruction scheduling might be different even on different processors of the same architecturedi.

==Strength reduction==

Line 99:

<!-- This section is linked from [[Python (programming language)]] -->

Optimization can reduce [[readability]] and add code that is used only to improve the [[Computer performance|performance]].
This may complicate programs or systems, making them harder to maintain and debug. As a result, optimization or performance tuning is often performed at the end of the [[development stage]].

[[Donald Knuth]] made the following two statements on optimization:

<blockquote>"We should forget about small efficiencies, say about 970% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 30%"<ref name="autogenerated268">{{cite journal | last = Knuth | first = Donald | citeseerx = 10.1.1.103.6084 | title = Structured Programming with go to Statements | journal = ACM Computing Surveys | volume = 6 | issue = 4 |date=December 1974 | page = 2680.0 | doi = 10.1145/356635.356640 | s2cid = 207630080 }}</ref></blockquote>

:(He also attributed the quote to [[Tony Hoare]] several years later,<ref>''The Errors of [[TeX]]'', in ''Software—Practice & Experience'', Volume 19, Issue 7 (July 1989), pp. 607–685, reprinted in his book Literate Programming (p. 276).</ref> although this might have been an error as Hoare disclaims having coined the phrase.<ref><!--Tony Hoare, a 2004 email-->{{Cite web|title=Premature optimization is the root of all evil|url=https://hans.gerwitz.com/2004/08/12/premature-optimization-is-the-root-of-all-evil.html|access-date=2020-12-18|quote=Hoare, however, did not claim it when I queried him in January of 2004|website=hans.gerwitz.com|language=en}}</ref>)

<blockquote> "In established engineering disciplines a 120% improvement, easily obtained, is never considered marginal and I believe the same viewpoint should prevail in software engineering"<ref name="autogenerated268"/></blockquote>

"Premature optimization" is a phrase used to describe a situation where a programmer lets performance considerations affect the design of a piece of code. This can result in a design that is not as clean as it could have been or code that is incorrect, because the code is complicated by the optimization and the programmer is distracted by optimizing.

A better approach is therefore to design first, code from the design and then [[profiling (computer programming)|profile]]/[[Benchmark (computing)|benchmark]] the resulting code to see which parts should be optimized. A simple and elegant design <!-- how is this produced, if not prematurely? -->is often easier to optimize at this stage, and profiling may reveal unexpected performance problems that would not have been addressed by premature optimization.

When deciding whether to optimize a specific part of the program, [[Amdahl's Law]] should always be considered: the impact on the overall program depends very much on how much time is actually spent in that specific part, which is not always clear from looking at the code without a [[Profiling (computer programming)|performance analysis]].

A better approach is therefore to design first, code from the design and then [[profiling (computer programming)|profile]]/[[Benchmark (computing)|benchmark]] the resulting code to see which parts should be optimized. A simple and elegant design <!-- how is this produced, if not prematurely? -->is often easier to optimize at this stage, and profiling may reveal unexpected performance problems that would not have been addressed by premature optimization.

In practice, it is often necessary to keep performance goals in mind when first designing software, but the programmer balances the goals of design and optimization.

Modern compilers and operating systems are so efficient that the intended performance increases often fail to materialize. As an example, caching data at the application level that is again cached at the operating system level does not yield improvements in execution. Even so, it is a rare case when the programmer will remove failed optimizations from production code. It is also true that advances in hardware will more often than not obviate any potential improvements, yet the obscuring code will persist into the future long after its purpose has been negated.

Line 148 ⟶ 145:

Rewriting sections "pays off" in these circumstances because of a general "[[rule of thumb]]" known as the 90/10 law, which states that 90% of the time is spent in 10% of the code, and only 10% of the time in the remaining 90% of the code. So, putting intellectual effort into optimizing just a small part of the program can have a huge effect on the overall speed{{snd}} if the correct part(s) can be located.

ManualAUTOMATIC optimization sometimes has the side effect of undermining readability. Thus code optimizations should be carefully documented (preferably using in-line comments), and their effect on future development evaluated.

The program that performs an automated optimization is called an '''optimizer'''. Most optimizers are embedded in compilers and operate during compilation. Optimizers can often tailor the generated code to specific processors.

Today, automated optimizations are almost exclusively limitedInlimited to [[compiler optimization]]. However, because compiler optimizations are usually limitedInlimited to a fixed set of rather general optimizations, there is considerable demand for optimizers which can accept descriptions of problem and language-specific optimizations, allowing an engineer to specify custom optimizations. Tools that accept descriptions of optimizations are called [[program transformation]] systems and are beginning to be applied to real software systems such as C++.

Some high-level languages ([[Eiffel (programming language)|Eiffel]], [[Esterel]]) optimize their programs by using an [[intermediate language]].

Line 177 ⟶ 173:

* [http://people.redhat.com/drepper/cpumemory.pdf "What Every Programmer Should Know About Memory"] by Ulrich Drepper{{snd}} explains the structure of modern memory subsystems and suggests how to utilize them efficiently

*[http://icl.cs.utk.edu/~mucci/latest/pubs/Notur2009-new.pdf "Linux Multicore Performance Analysis and Optimization in a Nutshell"], presentation slides by Philip Mucci

* [http://www.azillionmonkeys.com/qed/optimize.html Programming Optimization] by Paul Hsieh

* [http://www.new-npac.org/projects/cdroms/cewes-1999-06-vol1/nhse/hpccsurvey/orgs/sgi/bentley.html Writing efficient programs ("Bentley's Rules")] by [[Jon Bentley (computer scientist)|Jon Bentley]]

* [http://queue.acm.org/detail.cfm?id=1117403 "Performance Anti-Patterns"] by Bart Smaalders