Code Complete by Steve McConnell : Chapter 29

The author differentiates between code-tuning and redesign of data structures. The author discusses several code-tuning techniques:

1. Loops:
• Unswitching: If there is a decision inside a loop that doesn't change, the decision can be put outside the loop. This saves around 20% of the time.
• Jamming: This refers to combining two loops to make it one and saves 2-4% of execution time.
• Unrolling: This reduces the amount of time spent on loop housekeeping, i.e. changing and comparison of index that makes the loop. The performance improves by 20-28%.
  
• Minimize work inside loop: Complicated pointer expression used inside a loop can be assigned to a variable to reduce execution time.
• Sentinel Values: Multiple compound tests are reduced to a simple test in a loop increasing the performance.
• Putting the busiest loop on the inside.
• Strength Reduction: This involves replacing an expensive operation with a cheaper one.
2. Logic
• Short circuit: Stop processing once the answer is known both in if control statement and loop.
  
• Order tests by frequency: The test that is the fastest and more likely to be true is done first.
• Substitute complicated expressions with table lookup.
• Use lazy evaluation.
3. Data transformations
• Use integers rather than floating point numbers.
• Use the fewest array dimensions: Reducing array dimension from two or three to one increases performance.
• Minimize array references: Moving unnecessary array references out of loops increase performance.
  
• Use supplementary indexes: This means adding related data that makes accessing a particular data structure more efficient.
• String length index: Keeping length of the string instead of checking for NULL in C may improve performance in certain cases.
• Index for a singly linked list pointers:
• Independent parallel index structures:
• Use caching: Caching is a mechanism to retrieve most commonly used values more easily than the less commonly used values.
4. Expressions
• Exploit algebraic identities
• Use strength reduction
• Initialize at compile time
• Be wary of system routines: System routines are designed for general purpose and have a high accuracy. If you don't need it, an approximate routine can be designed to improve performance.
• Use the correct type of constants: Use named variables and literals that are the same type as the variables they are assigned to otherwise compiler will need to do type conversion to assign constant to a variable.
• Precompute results: This works more like caching.
• Eliminate common sub-expressions:
5. Routines
• Rewrite routines in line: This improves performance if the amount of time spent to make a routine call is significant compared to the time spent in routine itself, i.e. routine is small in size.
  
• Recode in assembler