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