Software optimization

Optimization of software is making it use less resources to do the same thing. Some resources that are typically targeted for optimization are the amount of memory used while executing, time required to execute and the amount of disk space or other storage required to execute. Optimization is related to refactoring (which is making software do the same thing more readably and maintainably), as in many cases the simplified code allows for shorter and quicker solutions which demand less resources.

Less frequent aims of optimizations are the time required by the software team to design, write and test the software and the time, memory or disk space required to compile the software. It is not unusual for reducing the use of one of these resources to cause another resource's usage to increase. Weighing the pros and cons of different optimizations is important.

Optimization is something that can be performed in all facets of the programming effort, from design to runtime usage. Programmers can implement certain optimizations at the time of the project's design and writing; they may use automatic optimization features of tools used for building the project, like compilers; and they may analyze their code using specialized tools like profilers and debuggers after it was written in order to improve existing code.

It's a very large topic; some optimization techniques follow, each big enough to deserve its own Wikipedia article:

• don't optimize if you can help it!
  • 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.
• profiling to find critical parts of the software (and then optimizing those)
• measuring attempted optimizations to see if they actually improved matters
• using a better algorithm or data structure to reduce time, space, or both
• using a better compiler on your code, or supplying different optimization flags to your compiler
• rewriting code in a lower-level language (C or assembly language are common choices) to reduce both time and space
• using packed bit-fields or packed bytes to reduce memory usage
• alignment
• using data instead of code to reduce memory usage
• using overlays or virtual memory to reduce memory usage
• parallelization
• specialized fast-path code to handle common cases
• normalization or denormalization of data
• reorganization of 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.)
• lazy evaluation
  • common subexpression elimination
  • precomputation, memoization, caching, and hints to reduce time
• speculation and prefetching
• reduction of overhead by batching
  • loop unrolling

The compiler optimization page lists a variety of techniques which are usually employed by compilers. Some of these techniques are too difficult for humans to employ directly, but sometimes a programmer will use high-level optimization on a piece of code, pass the code through an optimizing compiler, and then tweak 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 a crucial aspect of software engineering, optimizations made too early may severely impact the designed system's other aspects, such as portability or expandability. As a general rule, optimizations make the code more difficult to understand, and hence to maintain. Therefore, optimization is a process that needs to be started with a clear idea of what and how to optimize.

A very important thing to understand is the fact that bottlenecks have the greatest influence on software performance, and not most other pieces of code. Thus, when John Carmack was developing Quake, he noted the gameplay was extremely slow. Using a profiler, he discovered that the built-in scripting language, QuakeC was being interpreted too slowly to match game speed. He then re-wrote the QuakeC execution code using a technique called Just In Time (JIT) instead. This immediately solved all of the performance problems in a way which would not be possible if he optimized e.g. the graphical engine (doing which would also be much 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:

• SGI's optimization guide for Origin2000 and Onyx2
• Java Optimization page
• Paul H. J. Kelly teaches a course that includes material about compiler optimizations
• Summary of Jon Bentley's book Writing Efficient Programs (currently out of print) on optimizing code