Wikibooks

Optimizing Code for Speed/Outline

< Optimizing Code for Speed
This page may need to be reviewed for quality.

This work is licensed under the:

  1. The Creative Commons' Attribution License version 2.5 - or at your option any higher version.
  2. The GNU Free Documentation License version 1.2 - or at your option any higher version.

Please keep it this way. If you don't like either or both licenses - feel free to fork it and have a different derived license. (While properly accepting the terms of either license as starting points).

Authors: User:Shlomif.

Optimizing Code for Speed - Outline

edit
  • 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

edit
Retrieved from "https://en.wikibooks.org/wiki/Optimizing_Code_for_Speed/Outline"