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.