Optimizing Code for Speed/Outline

Optimizing Code for Speed - Outline

• Introduction
  • In what kind of programs is optimization required?
  • When to optimize?
  • When not to optimize?
• Guidelines to Optimization
  • Make sure you have automated tests with good coverage. (So nothing gets broken in the process, and to give fodder for the profiler).
  • Make sure your code is modular enough.
  • Profile using a Profiler.
  • Code review.
• Order of Complexity Optimizations
  • Explanation
  • What is order of complexity?
  • Reducing order of complexity
    • Examples
      • Lookup should be considerably less than O(n)
      • A Balanced Binary Tree instead of a sorted array.
      • A hash instead of a balanced binary tree
      • Counting Sort/Radix Sort
      • Joel on Software's Back to Basics' Shlemiel's the Painter syndrome - O(n^2) instead of O(n)
    • Showing that the algorithm is of the lowest complexity.
  • Reverse Order of Complexity Optimizations - sometimes lower complexity algorithms would have a larger factor
    • The Median O(N) algorithm - usually a O(N*log(N)) sort would be preferable.
    • Counting sort for large objects.
• Factor Optimizations
  • What are factor optimizations?
  • The Motivation for Factor Optimizations
  • Examples:
    • Using Pointers to structs instead of an array of structs
    • Reducing the memory consumption.
      • Note about the Memory/Speed trade-off "myth".
    • Parallelization:
      • Note about Amdahl's Law.
    • Putting the most commonly used variables in the struct's beginning. (Linux kernel)
    • Copy-on-write
    • Caching
    • Avoiding copying altogether
    • Inline Functions
    • Schwartzian Transform
  • Call for a catalog of optimizations
• Changing the Dependencies
  1. Using different libraries or your own self-coded routines.
  2. Switching to a faster language (or optimizing critical code in a different one). Languages hierarchy:
     • Assembler > C >= O'Caml > Java, .NET >> Perl, PHP > Python, Ruby, Tcl
• Optimizing by Reducing Feature-Set:
  • Less code -> less memory consumption -> faster code.
  • Less features -> less if's and stuff -> faster code.
    • Violating the "0, 1, Infinity" Law.
  • By compromising on security:
    • less sanity checks, input checks, etc. lead to faster code.
      • code that does not contain a lot of checking for malloc() failure, etc. will run faster because it does not have a lot error handling.
        • "Here be dragons".
• Conclusion

Resources to consider adding

• Eric Sink - Why is Git so Fast?
• How to Write Fast Code? (by doing less)
• Ulrich Drepper - "What every programmer should know about memory" - Part 1 with links to the other parts.
  • PDF Version
• "Shavin' Another Second" - Optimizing the File-Find-Object Perl Module
• Devel::NYTProf Screencast - overviews effective profiling.