Optimization Patterns

This section gathers together a few general techniques for improving performance that are so useful that they deserve specific mention. The reader may recognize some of these patterns as the core of familiar data structures, C++ language features, or hardware innovations:

  • Precomputation — Remove computation from the hot part of the program by performing it before execution arrives at the hot code — earlier in the program, at link time, compile time, or design time.

  • Lazy computation — Remove computation from some code paths by performing the computation closer to the point where it is needed.

  • Batching — Perform computation on several items together rather than one item at a time.

  • Caching — Reduce computation by saving and reusing the results of an expensive computation rather than recomputing them.

  • Sepcialization — Reduce computation by removing generality that is not used.

  • Hinting — Reduce computation by providing a hint the might improve permanence.

  • Optimizing the expected path — Test for inputs or events at run time in decreasing order of expected frequency.

  • Hashing — Compute a compact numerical summary (the hash) of a larger data structure such as a variable-length character string. The hash can stand in for the data structure in comparisons to improve performance.

  • Double-checking — Reduce computation by performing an inexpensive check, followed only if necessary by an expensive check.

Read More »