Programming for Performance

Product Family: Any
Target CPU: Any
Language: Any
Host: Any

The material presented in this article was originally part of a presentation called Achieving Required Performance in the Real World, by David A. Syiek at the Seventh Annual ASEET Symposium held at the Naval Postgraduate School, Monterey, CA on 14 January, 1993.

The Task, The Mandate, The Problem
Developers are often assigned a programming task similar to the following:

"Produce an implementation of a given algorithm that, when compiled and run on the target hardware, meets the stated performance requirements and all other requirements. The work must be completed on schedule, despite limited manpower, general overheads, and other handicaps."

In the interest of reducing costs and increasing reliability, a mandate is given:

"The entire system shall be written in a high-level language. Modern software engineering practices and principles shall be employed. The code must be easy to read, and easy to maintain."

Even though the developers are careful to follow all of the advice given in the most modern textbooks, at some point they discover that their application is not running fast enough; help is needed. Consider the following recommendations the next time you need to improve the performance of the application you are developing.

Read the documentation
Failure to read the documentation prevents many developers from learning about the information and support that are available to them from the hardware and compiler vendors. Call your vendor's customer support line and ask for help or advice if necessary.

Think Cost versus Benefit
Before implementing any performance improvement, consider the cost of the implementation versus the benefit of the improvement. Making a routine run twice as fast as the stated requirement may be a bad decision if there is an alternative solution that would barely meet the speed requirement, but takes half the time to implement and is easier to maintain.

Do not re-invent the wheel
Most algorithms have already been implemented in some computer language and used in some production system. Check repositories and electronic bulletin boards. Ask around, network newsgroups are a good place to start. Also, remember that it is usually cheaper to buy than to build. If the only available implementation is in the wrong language, interface or do a literal translation.

Attempt the straightforward implementation first
Correctness takes precedence over speed. The algorithm must run correctly before making any attempt to tune for speed. It is best done with an obvious implementation.

Write tests to prove that the implementation runs correctly, and re-run the tests often as you tune for speed to verify that the implementation is still correct.

You may be surprised to find that the obvious implementation runs with the required performance. (The compiler is getting smarter all the time.)

Big improvements can be made without changing source
Memory hierarchy/bus structure often makes linking very important. Experiment with the available compiler and hardware options. Also, it is sometimes less expensive to change to faster hardware than to performance-tune a large software system.

Locate the hot spots
Remember, 90% of execution time is spent in 10% of the code. Never attempt to tune code until you have located that 10% of the code that contains the problem areas. Use profiling tools, timing loops, logic analyzers and oscilloscopes to measure the actual distribution of time.

Tune a small amount of code, a little at a time
Try to minimize the distance from the straightforward implementation. Do not make big changes if small ones will achieve the desired goal.

Small changes allow you to isolate the effects. Measure improvement and verify correctness after each change.

Use common sense and a little imagination
The compiler cannot always save you from yourself; most big improvements are purely algorithmic. Code review sessions are often useful for finding this type of improvement.

A big advantage to using a high-level language is the ability to try dozens of variations in a short period of time. Try many (imaginative) variations of an algorithm to see which yields the best result.

You may wish to attempt reverse engineering, given the desired assembly code.

Understand the pitfalls and strengths of the language/compiler/target
High-level languages contain powerful abstractions that can be applied to solving many generalized problems. However, the cost of a general solution may be too high for your specific need. On the other hand, many constructs in a high-level language provide for better translation to high-performance code.

Experiment to discover which constructs best suit your needs. Documentation may also provide a few clues.

There is no such thing as a dirty trick
Try all of the acceptable solutions first, but if you have exhausted the list of commonly accepted techniques, anything that you find that works is "good" by definition.

The price of non-standard coding is paid in maintenance. Learn to write readable comments.