Software optimization

Optimization of software is making it use less time or space to do the same thing. (Note that this means that it's related to refactoring, which is making software do the same thing more readably and maintainably.) It's a very large topic; some aspects of optimization follow, each big enough to deserve its own Wikipedia article:

• don't optimize if you can help it!
• 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
• using CPU instructions with complex offsets to do math
• 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
• strength reduction
• reduction of cache collisions (e.g. by disrupting alignment within a page)

References:

• SGI's optimization guide for Origin2000 and Onyx2: http://techpubs.sgi.com:80/library/tpl/cgi-bin/browse.cgi?coll=0650&db=bks&cmd=toc&pth=/SGI_Developer/OrOn2_PfTune
• Java Optimization page: http://www-2.cs.cmu.edu/~jch/java/optimization.html
• Paul H. J. Kelly teaches a course that includes material about compiler optimizations: http://www.doc.ic.ac.uk/~phjk/CompilersIICourse/Lectures/Chapter1/IntroToCompilationIssuesForSophisticatedArchsV1-article.html
• Jon Bentley wrote the book (Writing Efficient Programs) on optimizing code; it's out of print now, but the summary rules from it are on the Web at http://www.programmingpearls.com/apprules.html (or were recently, perhaps soon will be again.)