Software optimization

Optimization of software is making it use less time or space to do the same thing. It's a very large topic and deserves a very large article, which I don't have time to write at present; some large and important aspects of optimization follow:

• 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
• rewriting code in a lower-level language (C or assembly language are common choices) to reduce both time and space
• precomputation, memoization, caching, and hints to reduce time
• 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
• using a compiler, or a better compiler, on your code, or supplying different optimization flags to your compiler
• parallellization
• 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
• speculation and prefetching
• reduction of overhead by batching

Some more specific tricks, many of which can be done either by hand or by a compiler, follow:

• loop unrolling
• loop combining
• loop interchange (swapping inner and outer loops)
• common subexpression elimination
• test reordering
• inlining of procedures
• constant folding and propagation
• instruction scheduling
• dead code elimination
• code-block reordering to reduce conditional branches and improve locality of reference
• factoring out of invariants (moving invariant expressions out of loops, e.g.)
• sentinels
• removing recursion