Software optimization

Optimization of software makes it use less resources to do the same thing. This saves money, providing that the code does something useful.

Typically, programmers minimize the amount of memory, disk-space or time that a program uses.

Optimization is related to refactoring (which makes software do the same thing more readably and maintainably). In many cases, simplified code runs faster and takes less space.

Some other forms of optimization minimize the work of the software design team. For example, safety-critical software requires validation, and the validation can be most of the expense of development.

Often, optimization of one form can cause waste of some other resource. The process of trading-off conflicting advantages is usually done by estimating their costs.

Optimization can be performed at any step of the programming project, from design to runtime usage. Programmers can optimize the design, perhaps (most pwoerfully) by finding a better algorithm. They may use automatic optimization features of compilers. They may choose to write selected parts of the code in assembler. They may select those parts by analyzing their code with tools like profilers and debuggers.

Some optimization techniques follow, each big enough to deserve its own Wikipedia article:

don't optimize if you can help it!
if code never runs, don't optize it. For example, do not optimize error code. A famous, interesting example, was the group at Burroughs that optimized the most frequently executed piece of code in the operating system, the idle loop of the multitasker.
- If a piece of code has not been tested thoroughly, don't optimize. Donald Knuth once stated that "Premature optimization is the root of all evil."
- If optimization can improve performance significantly, optimize.
- If optimization can save a significant amount of battery power on a mobile target system, optimize.
- Otherwise, don't.
profile to find critical parts of the software (and then optimize those)
measure attempted optimizations to see if they actually improved matters
use a better algorithm or data structure to reduce time, space, or both
use a better compiler on your code, or supply different optimization flags to your compiler
rewrite code in a lower-level language (C or assembly language are common choices) to reduce both time and space
use packed bit-fields or packed bytes to reduce memory usage
Check alignment; multi-byte integers run substantially faster on some computers if they are aligned with the data bus (usually on addresses that are multiples of two, four or eight). On some computers, memory banks are interleaved, and accessing these on a multiple of the bank nuumber slows the access to the speed of a single bank.
use data instead of code to reduce memory usage
use overlays or virtual memory to reduce memory usage
parallelize
use specialized fast-path code to handle common cases
normalize or denormalize data
reorganize data to reduce false sharing, improve packing, improve locality of reference (by rearranging fields in a record or by moving some fields to other records.)
perform lazy evaluation (only evaluate enough of a data structure to accomplish the needed task)
- Eliminate common (shared) subexpressions
- precomputate, memorize, cache, or use hints to reduce time
Use speculation and prefetching
reduce overhead by batching
- Unroll loops

The compiler optimization page lists techniques employed by compilers. Some of these are too difficult for humans to employ directly, but sometimes a programmer passes the code through an optimizing compiler, and then tweaks the generated assembly language code by hand.

General issues

Need for optimization

Often, programmers begin to optimize all of their code at the design stage, or wherever they see fit afterwards.

While performance is crucial, optimizations made too early may damage a system in other ways, such as portability or expandability.

Optimizations may make the code more difficult to understand, and hence to maintain. Therefore, optimize only where needed.

bottlenecks have the greatest influence on software performance. For example, when John Carmack was developing Quake, he noted the gameplay was slow. Using a profiler, he discovered that the built-in scripting language, QuakeC was being interpreted too slowly. He then re-wrote the QuakeC execution code using a technique called Just In Time (JIT) instead. This solved the performance problems more thoroughly than if he optimized the graphical engine (which would also have been more difficult).

General techniques

The general concept of optimization is taking one piece of code and re-writing it in a better (quicker, smaller, more stable) way. The flesh and blood of software are algorithms and data structures - and it is often possible to change one type of them to another and to improve performance considerably. For example, rather than using the less efficient (but simpler) bubble sort algorithm, a programmer may wish to use merge sort, quicksort, or heapsort. Similarly, finding whether a number exists in a certain list takes less time when using a binary tree than a linked list.

However, there's a price for almost all of these choices. Thus, in some scenarios the quicksort is even slower that bubble sort (due to the overhead), merge sort is inefficient for small lists, and binary trees take up more space in the memory and demand special runtime maintenance (balancing). Among both data and structures, there's often some sort of a tradeoff between performance, memory requirements and complexity that makes good optimization an issue demanding much attention and understanding of the inner works of the computer.

If algorithms and data structures are the flesh of a program, use of system resources is its bones. Most programs rely heavily on functionality provided by operating systems. While most modern operating systems provide a relatively orthogonal interface that tries to minimize the number of ways in which any one task can be performed, it is sometimes possible to devise a strategy that would minimize overall system resource use. A simplistic example of such a strategy under the MS-DOS operating system would be to buffer the output rather than producing it one byte at a time. Often, the code libraries that come with programming languages include such optimizations out of the box.

References: