Optimization (computer science)

In computing, optimization modifies 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 Internet.

Note that although the word "optimization" shares the same root as "optimal," economical optimizations can rarely find a truly optimal system.

Table of contents

1 Basis
2 Tradeoff
3 Different fields
4 Bottleneck
5 When to do optimization?
6 Automated and manual optimization
7 Techniques
8 Subpages
9 References
10 Related terms
11 External links

Basis

Tasks carried out in the computer or in the system often can be done more efficiently. For example,

int i, sum = 0; for (i = 1; i <= 10; i++)

 sum += i;

printf ("sum: %d\\n", sum);

This code can be rewritten using a mathematic formula like:

sum = (10 * 11) / 2; printf ("sum: %d\\n", sum);

Usually, the term "optimization" presumes that the system retains the same functionality. However, often a crucial optimization is to solve only the actual problem, removing useless code. For example, if you could assume the program does not need to handle more than 100 items of input, then you can use fixed static memory allocation, avoiding dynamic memory allocation.

Tradeoff

The optimization might be to reduce the maximum execution time, memory use, bandwidth, or some other resource. Most of the time, those objectives can be mutually exclusive, and require a tradeoff. The use of cache is a good example. Increasing the size of cache improves the runtime performance, at least somehow if not linearly, but increase the memory consumption.

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.

Bottleneck

The effective optimization requires finding a bottleneck a narrow place that slows down the entire system effectively. It was often told that improving about 20% of code is responsibly for 80% of the results.

The architectural design of a system can overwhelmingly affect its performance.

The choice of algorithm affects efficiency more than any other item of the design. Usually, more complex algorithms and data structures perform well with many items while simple algorithms are more suitable to small amounts of data. For small sets of data, the set-up and initialization time of the more complex algorithm can outweigh the benefit of the better algorithm.

Usually, the more memory the program uses, the faster program runs. Take a filtering program. The common practice in such a program is read each line and filter and output that line in the same time. The memory is only needed for one line, but typically the performance is poor. To improve the performance, read the entire file then output the filtered result. This typically improve the peformance dramatically but causes heaviy memory use. Caching the result is also effective though requiring some or huge memory use.

When to do optimization?

It is well told that optimization often undermines readibility and adds code that is used only to improve the performance. This may complicate programs or systems, making hard to maintain and debug. Compiler optimization, for example, may introduce weird behavior because of compiler bugs. Because of that, it is preferable that optimization or performance tuning is done in the end of development stage. In other words, often systems or programs perform poorly in middle of developing.

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. Perhaps 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 efficiencies, it is far more expensive than automated optimizations.

Code 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, yelding 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 maximum efficiency of a processor cache memory), data types as small as possible can be used, an integer arithmetic can be used instead of a floating-point one, hash tables can replace linear vectors, and so on.

Performance bottlenecks can be due to the language rather than algorithms or data structures used in the program. Sometimes, a critical part of the program can be re-written in a different, faster programming language. For example, it is common for very high-level languages like Python to have modules written in C, for a greater speed. Programs already written in C can have modules written in assembly. See subpages for each language-specific optimization:

Rewriting pays off because of a law 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.

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.