Optimization (computer science)

From Wikipedia, the free encyclopedia

In computing, optimization is the process of modifying a system to improve its efficiency. The system can be a single computer program, a collection of computers or even an entire network such as the Internet.

Although the word "optimization" shares the same root as "optimal," it is rare for the process of optimization to produce a truly optimal system for all purposes. There will always be tradeoffs.

Optimization must be approached with caution. Tony Hoare first said, and Donald Knuth famously repeated, "Premature optimization is the root of all evil." It is important to have sound algorithms and a working prototype first.

1 Basis
2 Tradeoff
3 Different fields
4 Bottlenecks
5 When to optimize
- 5.1 Interpreted languages
- 5.2 Macros
6 Automated and manual optimization
7 Time taken for optimization
8 Techniques
9 Categories
10 Quotes
11 See also
12 References
13 External links

[edit] Basis

Computational tasks are often performed in several manners with varying efficiency. For example, consider the following C code snippet to sum all integers from 1 to N:

int i, sum = 0;
for (i = 1; i <= N; i++)
  sum += i;
printf ("sum: %d\n", sum);

This code can (assuming no overflow) be rewritten using a mathematical formula like:

int sum = (N * (N+1)) / 2;
printf ("sum: %d\n", sum);

The optimization, often done automatically, is therefore to pick a method that is more computationally efficient while retaining the same functionality. However, a significant improvement in performance can often be achieved by solving only the actual problem and removing extraneous functionality. For example, if it were reasonable to assume the program does not need to handle more than (say) 100 items of input, one could use static rather than dynamic memory allocation.

[edit] Tradeoff

Optimization will generally focus on one or two of execution time, memory usage, disk space, bandwidth or some other resource. This will usually require a tradeoff — where one is optimized at the expense of others. For example, increasing the size of cache improves runtime performance, but also increases the memory consumption. Other common tradeoffs include code clarity and conciseness.

[edit] Different fields

In operations research, optimization is the problem of determining the inputs of a function that minimize or maximize its value. Sometimes constraints are imposed on the values that the inputs can take; this problem is known as constrained optimization.

In computer programming, optimization usually specifically means to modify code and its compilation settings on a given computer architecture to produce more efficient software.

Typical problems have such a large number of possibilities that a programming organization can only afford a "good enough" solution.

[edit] Bottlenecks

Optimization requires finding a bottleneck: the critical part of the code that is the primary consumer of the needed resource. Improving about 20% of code is often responsible for 80% of the results (see also Pareto principle).

The architectural design of a system overwhelmingly affects its performance. The choice of algorithm affects efficiency more than any other item of the design. More complex algorithms and data structures perform well with many items, while simple algorithms are more suitable for small amounts of data — the setup and initialization time of the more complex algorithm can outweigh the benefit.

The more memory the program uses, the faster it will generally run. For example, a filtering program will commonly read each line and filter and output that line immediately. This only uses enough memory for one line, but performance is typically poor. Performance can be greatly improved by reading the entire file then writing the filtered result, though this uses much more memory. Caching the result is similarly effective, though also requiring larger memory use.

[edit] When to optimize

Optimization can reduce readability and add code that is used only to improve the 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.

"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.

An alternative approach is to design first, code from the design and then profile/benchmark the resulting code to see what should be optimized. A simple and elegant design 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.

[edit] Interpreted languages

In interpreted languages (especially that that are executed repeatedly with low latency expectations such as PHP and JavaScript) some programmers remove comments, whitespace, and unused method or function definitions before deploying.

If the programmer discards the original commented and formatted code, maintainability is sacrificed. It becomes harder for a human to read, debug and subsequently modify or extend the code once it has been optimized.

This anti-pattern can be avoided by keeping a copy of the original code, and by working from the original code when making changes to optimized software.

[edit] Macros

Optimization during code development using macros takes on different forms in different languages. In high-level languages such as C, macros are implemented using textual substitution, and so their benefit is mostly limited to avoiding function-call overhead.

In many functional programming languages, however, macros are implemented using compile-time evaluation and substitution of non-textual, compiled code. Because of this difference, it is possible to perform complex compile-time computations, moving some work out of the resulting program. Lisp originated this style of macro, and such macros are often called "Lisp-like macros".

As with any optimization, however, it is often difficult to predict where such tools will have the most impact before a project is complete.

[edit] Automated and manual optimization

Optimization can be automated by compilers or performed by programmers. Gains are usually limited for local optimization, and larger for global optimizations. Usually, the most powerful optimization is to find a superior algorithm.

Optimizing a whole system is usually done by human beings because the system is too complex for automated optimizers. Grid computing or distributed computing aims to optimize the whole system, by moving tasks from computers with high usage to computers with idle time.

In this technique, programmers or system administrators explicitly change code so that the system performs better. Although it can produce better efficiency, it is far more expensive than automated optimizations.

First of all, it is extremely important to use a profiler to locate the bottleneck. Programmers usually think they have a clear idea of where the bottleneck is, but they are frequently completely wrong. Optimizing an unimportant piece of code will not help the overall program speed.

When the bottleneck is localized, optimization usually starts with a rethinking of the algorithm used in the program: more often than not, a particular algorithm can be specifically tailored to a particular problem, yielding better performance than a generic algorithm. For example, the task of sorting a huge list of items is usually done with a quicksort routine, which is one of the most efficient generic algorithms. But if some characteristic of the items is exploitable (for example, they are already arranged in some particular order), a different method can be used, or even a custom-made sort routine.

After one is reasonably sure that the best algorithm is selected, code optimization can start: loops can be unrolled (for lower loop overhead, although this can often lead to lower speed, due to overloading the processor's instruction cache), data types as small as possible can be used, integer arithmetic can be used instead of a floating-point one, and so on.

Performance bottlenecks can be due to language limitations rather than algorithms or data structures used in the program. Sometimes, a critical part of the program can be re-written in a different programming language that gives more direct access to the underlying machine. For example, it is common for very high-level languages like Python to have modules written in C for greater speed. Programs already written in C can have modules written in assembly. Programs written in D can use the inline assembler.

Rewriting pays off because of a general rule 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 optimizing just a small part of the program can have a huge effect on the overall speed.

Manual optimization often has the side-effect of undermining readability. Thus code optimizations should be carefully documented and their effect on future development evaluated.

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

Today, automated optimizations are almost exclusively limited to compiler optimization.

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

[edit] Time taken for optimization

On some occasions, the time taken for optimization in itself may be an issue.

In a software project, optimizing code usually does not add a new feature, and worse, it might break existing functionalities. Because optimized code has lesser readability than a straightforward code, optimization may well hurt the maintainability of the program as well. In short, optimization becomes a cost and it is important to be sure that the investment pays off.

The optimizer (a program that does optimization) may have to be optimized as well. The compilation with the optimizer being turned on usually takes more time, though this is only a problem when the program is significantly large. In particular, for just-in-time compilers the performance of the optimizer is a key in improving execution speed. Usually spending more time can yield better code, but it is also the precious computer time that we want to save; thus in practice tuning the performance requires the trade-off between the time taken for optimization and the reduction in the execution time gained by optimizing code.

[edit] Techniques

Load balancing spreads the load over a large number of servers. Often load balancing is done transparently (i.e., without users noticing it), using a so-called layer 4 router.

Caching stores intermediate products of computation to avoid duplicate computations.

[edit] Categories

Code optimization can be broadly categorized as platform dependent and platform independent techniques. Platform independent techniques are generic techniques and are effective for most of digital signal processors (DSP) platforms. Such as loop unrolling. Reduction in function calls. Memory efficient routines. Reduction in conditions etc. Platform dependent techniques involve instruction level parallelism, data level parallelism, cache optimization techniques i.e. parameters that differ among various platforms.

[edit] Quotes

"The order in which the operations shall be performed in every particular case is a very interesting and curious question, on which our space does not permit us fully to enter. In almost every computation a great variety of arrangements for the succession of the processes is possible, and various considerations must influence the selection amongst them for the purposes of a Calculating Engine. One essential object is to choose that arrangement which shall tend to reduce to a minimum the time necessary for completing the calculation." - Ada Byron's notes on the analytical engine 1842.
"More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason - including blind stupidity." - W.A. Wulf
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%." ^[1] - Knuth, paraphrasing Hoare
"Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you have proven that's where the bottleneck is." - Rob Pike
"The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet." - Michael A. Jackson