# Optimizing Code for Speed/Outline

This work is licensed under the:
* The Creative Commons' Attribution License version 2.5 - or at your option any higher version.
* 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

* 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
** Using different libraries or your own self-coded routines.
** 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.