Optimization (computer science)

From Wikipedia, the free encyclopedia

In computing, optimization is the process of modifying a system to make some aspect of it work more efficiently or use fewer resources. For instance, a computer program may be optimized so that it executes more rapidly, or is capable of operating with less memory storage or other resources, or draw less power. The system may 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. The optimized system will typically only be optimal in one application or for one audience. One might reduce the amount of time that a program takes to perform some task at the price of making it consume more memory. In an application where memory space is at a premium, one might deliberately choose a slower algorithm in order to use less memory. Often there is no “one size fits all” design which works well in all cases, so engineers make trade-offs to optimize the attributes of greatest interest. Additionally, the effort required to make a piece of software completely optimal—incapable of any further improvement—is almost always more than is reasonable for the benefits that would be accrued; so the process of optimization may be halted before a completely optimal solution has been reached. Fortunately, it is often the case that the greatest improvements come early in the process.

Optimization can occur at a number of levels. At the highest level, the design may be optimized to make best use of the available resources. The implementation of this design will benefit from the use of efficient algorithms and the implementation of these algorithms will benefit from writing good quality code. Use of an optimizing compiler tends to ensure that the executable program is optimized. At the lowest level, it is possible to bypass the compiler completely and write assembly code directly. With modern optimizing compilers and the greater complexity of recent CPUs, it is most often difficult to write code that is optimized further than what the compiler generates, and few projects need resort to this ultimate optimization step. However, a large amount of code written today is still compiled with the intent to run on the greatest percentage of machines possible. As a result, programmers and compilers don't always take advantage of the more efficient instructions provided by newer CPUs. Since optimization often relies on making use of special cases and performing complex trade-offs, a fully optimized program is usually more difficult for humans to comprehend and hence tends to contain more faults than unoptimized versions.

1 Basics
2 Trade-off
3 Different fields
4 Bottlenecks
5 When to optimize
- 5.1 Macros
6 Automated and manual optimization
7 Time taken for optimization
8 Categories
9 Quotes
10 See also
11 References
12 External links

[edit] Basics

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

Optimization is not always an obvious or intuitive process. In the example above, the ‘optimized’ version might actually be slower than the original software if N were sufficiently small and the computer were much faster at performing addition and looping operations than multiplications and divisions.

[edit] Trade-off

Optimization will generally focus on improving just one or two aspects of performance: execution time, memory usage, disk space, bandwidth, power consumption or some other resource. This will usually require a trade-off: where one factor 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 trade-offs include code clarity and conciseness.

There are cases where the programmer doing the optimization must decide to make the software more optimal for some operations but at the price of making other operations less efficient. These trade-offs may often be of a non-technical nature - such as when a competitor has published a benchmark result that must be beaten in order to improve commercial success but perhaps at the price of making normal usage of the software less efficient. Such changes are sometimes jokingly referred to as pessimizations.

[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. As a rule of thumb, improving 20% of the code is responsible for 80% of the results (see also Pareto principle).

The Pareto principle (also known as the 80-20 rule, the law of the vital few and the principle of factor sparsity) states that for many phenomena, 80% of the consequences stem from 20% of the causes. The idea has rule-of-thumb application in many places, but it is commonly misused. For example, it is a misuse to state that a solution to a problem "fits the 80-20 rule" just because it fits 80% of the cases. In computer science, the Pareto principle can be applied to resource optimization by observing that 80% of the resources are typically used by 20% of the operations. In software engineering, it is often a better approximation that 90% of the execution time of a computer program is spent executing 10% of the code (known as the 90/10 law in this context).

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.

In some cases, adding more memory can help to make a program run faster. 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.

Donald Knuth said, paraphrasing Hoare^[1]

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." (Knuth, Donald. Structured Programming with go to Statements, ACM Journal Computing Surveys, Vol 6, No. 4, Dec. 1974. p.268.)

"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] Macros

Optimization during code development using macros takes on different forms in different languages. In some procedural languages, such as C and 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

Main article: Compiler 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. 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 find the sections of the program that are taking the most resources—the bottleneck. Programmers usually think they have a clear idea of where the bottleneck is, but intuition is frequently wrong. Optimizing an unimportant piece of code will typically do little to help the overall performance.

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 if it overloads the CPU cache), data types as small as possible can be used, integer arithmetic can be used instead of floating-point, 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 putting intellectual effort into optimizing just a small part of the program can have a huge effect on the overall speed if the correct part(s) can be located.

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.

Grid computing or distributed computing aims to optimize the whole system, by moving tasks from computers with high usage to computers with idle time.

[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] 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%.”^[2] - Knuth, paraphrasing Hoare^{[citation needed]}
“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