Latest commit e39d03c Jan 30, 2017 @foo123 update
Permalink
Failed to load latest commit information.
README.md update Jan 30, 2017
zen-circle.jpg clean upload Aug 25, 2014

README.md

Code Optimization Methods

A summary of various code optimization methods

Contents

A note on the relation between Computational Complexity of Algorithms and Code Optimization Techniques

Both computational complexity theory 2 and code optimization techniques 1 , have the common goal of efficient problem solution. While they are related to each other and share some concepts, the difference lies in what is emphasized at each time.

Computational complexity theory, studies the performance with respect to input data size. Trying to design algorithmic solutions that have the least / fastest dependence on data size, regardless of underlying architecture. Code optimization techniques, on the other hand, focus on the architecture and the specific constants which enter those computational complexity estimations.

Systems that operate in Real-Time are examples where both factors can be critical (eg. Real-time Image Processing in JavaScript , yeah i know i am the author :) ).

General Principles

  • Keep it DRY and Cache : The general concept of caching involves avoiding re-computation/re-loading of a result if not necessary. This can be seen as a variation of Dont Repeat Yourself principle 3 . Even dynamic programming can be seen as a variation of caching, in the sense that it stores intermediate results saving re-computation time and resources.

  • KISS it, simpler can be faster : Keep it simple 4 , makes various other techniques easier to apply and modify. ( A plethora of Software Engineering methods can help in this 34, 35, 55, 56 )

  • Sosi ample free orginizd, So simple if re-organized : Dont hesitate to re-organize if needed. Many times sth can be re-organized, re-structured in a much simpler / faster way while retaining its original functionality (concept of isomorphism 22 , change of representation 23, 24, 36 ), yet providing other advantages. For example, the expression (10+5*2)^2 is the simple constant 400, another example is the transformation from infix expression notation to prefix (Polish) notation which can be evaluated faster in one pass.

  • Divide into subproblems and Conquer the solution : Subproblems (or smaller, trivial, special cases) can be easier/faster to solve and combine for the global solution. Sorting algorithms are great examples of that 5, sorting algorithms

  • More helping hands are always welcome : Spread the work load, subdivide, share, parallelize if possible 6, 54, 68, 69, 70 .

  • United we Stand and Deliver : Having data together in a contiguous chunk, instead of scattered around here and there, makes it faster to load and process as a single block, instead of (fetching and) accessing many smaller chunks (eg. cache memory, vector/pipeline machines, database queries) 51, 52, 53 .

  • A little Laziness never hurt anyone : So true, each time a program is executed, only some of its data and functionality are used. Delaying to load and initialize (being lazy) all the data and functionality untill needed, can go a long way 7 .

Further Notes

Before trying to optimize, one has to measure and identify what needs to be optimized, if any. Blind "optimization" can be as good as no optimization at all, if not worse.

That being said, one should always try to optimize and produce efficient solutions. A non-efficient "solution" can be as good as no solution at all, if not worse.

Pre-optimisation is perfectly valid given pre-knowledge. For example that instantiating a whole class or array is slower than just returning an integer with the appropriate information.

Some of the optimization techniques can be automated (eg in compilers), while others are better handled manually.

Some times there is a trade-off between space/time resources. Increasing speed might result in increasing space/memory requirements (caching is a classic example of that).

The 90-10 (or 80-20 or other variations) rule of thumb, states that 90 percent of the time is spent on 10 percent of the code (eg a loop). Optimizing this part of the code can result in great benefits. (see for example Knuth 8 )

One optimization technique (eg simplification) can lead to the application of another optimization technique (eg constant substitution) and this in turn can lead back to the further application of the first optimization technique (or others). Doors can open.

References: 9, 11, 12, 46, 47, 48, 49, 50

Low-level

Generalities 44, 45

Data Allocation

  • Disk access is slow
  • Main Memory access is faster than disk
  • CPU Cache Memory (if exists) is faster than main memory
  • CPU Registers are fastest

Binary Formats

  • Double precision arithmetic is slow
  • Floating point arithmetic is faster than double precision
  • Long integer arithmetic is faster than floating-point
  • Short Integer, fixed-point arithmetic is faster than long arithmetic
  • Bitwise arithmetic is fastest

Arithmetic Operations

  • Exponentiation is slow
  • Division is faster than exponentiation
  • Multiplication is faster than division
  • Addition/Subtraction is faster than multiplication
  • Bitwise operations are fastest

Methods

  • Register allocation : Since register memory is fastest way to access heavily used data, it is desirable (eg compilers, real-time systems) to allocate some data in an optimum sense in the cpu registers during a heavy-load operation. There are various algorithms (based on the graph coloring problem) which provide an automated way for this kind of optimization. Other times a programmer can explicitly declare a variable that is allocated in the cpu registers during some part of an operation 10

  • Single Atom Optimizations : This involves various operations which optimize one cpu instruction (atom) at a time. For example some operands in an instruction, can be constants, so their values can be replaced instead of the variables. Another example is replacing exponentiation with a power of 2 with a multiplication, etc..

  • Optimizations over a group of Atoms : Similar to previous, this kind of optimization, involves examining the control flow over a group of cpu instructions and re-arranging so that the functionality is retained, while using simpler/fewer instructions. For example a complex IF THEN logic, depending on parameters, can be simplified to a single Jump statement, and so on.

Language-dependent optimization

  • Check carefuly the documentation and manual for the underlying mechanisms the language is using to implement specific features and operations and use them to estimate the cost of a certain code and the alternatives provided.

Language-independent optimization

  • Re-arranging Expressions : More efficient code for the evaluation of an expression (or the computation of a process) can often be produced if the operations occuring in the expression are evaluated in a different order. This works because by re-arranging expression/operations, what gets added or multiplied to what, gets changed, including the relative number of additions and multiplications, and thus the (overall) relative (computational) costs of each operation. In fact, this is not restricted to arithmetic operations, but any operations whatsoever using symmetries (eg commutative laws, associative laws and distributive laws, when they indeed hold, are actualy examples of arithmetic operator symmetries) of the process/operators and re-arrange to produce same result while having other advantages. That is it, so simple. Classic examples are Horner's Rule 13 , Karatsuba Multiplication 14 , fast complex multiplication 15 , fast matrix multiplication 18, 19 , fast exponentiation 16, 17 , fast factorials/binomials 20, 21 , fast fourier transform 57 , sorting by merging 25 , sorting by powers 26 .

  • Constant Substitution/Propagation : Many times an expression is under all cases evaluated to a single constant, the constant value can be replaced instead of the more complex and slower expression (sometimes compilers do that).

  • Inline Function/Routine Calls : Calling a function or routine, involves many operations from the part of the cpu, it has to push onto the stack the current program state and branch to another location, and then do the reverse procedure. This can be slow when used inside heavy-load operations, inlining the function body can be much faster without all this overhead. Sometimes compilers do that, other times a programmer can declare or annotate a function as inline explicitly. 27

  • Combining Flow Transfers : IF/THEN instructions and logic are, in essence, cpu branch instructions. Branch instructions involve changing the program pointer and going to a new location. This can be slower if many jump instructions are used. However re-arranging the IF/THEN statements (factorizing common code, using De Morgan's rules for logic simplification etc..) can result in isomorphic functionality with fewer and more efficient logic and as a result fewer and more efficient branch instructions

  • Dead Code Elimination : Most times compilers can identify code that is never accessed and remove it from the compiled program. However not all cases can be identified. Using previous simplification schemes, the programmer can more easily identify "dead code" (never accessed) and remove it.

  • Common Subexpressions : This optimization involves identifying subexpressions which are common in various parts of the code and evaluating them only once and use the value in all subsequent places (sometimes compilers do that).

  • Common Code Factorisation : Many times the same block of code is present in different branches, for example the program has to do some common functionality and then something else depending on some parameter. This common code can be factored out of the branches and thus eliminate unneeded redundancy , latency and size.

  • Strength Reduction : This involves transforming an operation (eg an expression) into an equivalent one which is faster. Common cases involve replacing exponentiation with multiplication and multiplication with addition (eg inside a loop). This technique can result in great efficiency stemming from the fact that simpler but equivalent operations are several cpu cycles faster (usually implemented in hardware) than their more complex equivalents (usually implemented in software) 28

  • Handling Trivial/Special Cases : Sometimes a complex computation has some trivial or special cases which can be handled much more efficiently by a reduced/simplified version of the computation (eg computing a^b, can handle the special cases for a,b=0,1,2 by a simpler method). Trivial cases occur with some frequency in applications, so simplified special case code can be quite useful. 42, 43 . Similar to this, is the handling of common/frequent computations (depending on application) with fine-tuned or faster code.

  • Exploiting Mathematical Theorems/Relations : Some times a computation can be performed in an equivalent but more efficient way by using some mathematical theorem, transformation, symmetry 24 or knowledge (eg. Gauss method of solving Systems of Linear equations 58 , Euclidean Algorithm 71 (or both 72 ), Fast Fourier Transforms 57 , Fermat's Little Theorem 59 , Taylor-Mclaurin Series Expasions, Trigonometric Identities 60 , etc..). This can go a long way. It is good to refresh your mathematical knowledge every now and then.

  • Using Efficient Data Structures : Data structures are the counterpart of algorithms (in the space domain), each efficient algorithm needs an associated efficient data structure for the specific task. In many cases using an appropriate data structure (representation) can make all the difference (eg. database designers and search engine developers know this very well) 36, 37, 23, 62, 63, 64, 65, 68, 69, 70

Loop Optimizations

Perhaps the most important code optimization techniques are the ones involving loops.

  • Code Motion / Loop Invariants : Sometimes code inside a loop is independent of the loop index, can be moved out of the loop and computed only once (it is a loop invariant). This results in the loop doing fewer operations (sometimes compilers do that) 29, 30

example:

// this can be transformed
for (i=0; i<1000; i++)
{
    invariant = 100*b[0]+15; // this is a loop invariant, not depending on the loop index etc..
    a[i] = invariant+10*i;
}

// into this
invariant = 100*b[0]+15; // now this is out of the loop
for (i=0; i<1000; i++)
{
    a[i] = invariant+10*i; // loop executes fewer operations now
}
  • Loop Fusion : Sometimes two or more loops can be combined into a single loop, thus reducing the number of test and increment instructions executed.

example:

// 2 loops here
for (i=0; i<1000; i++)
{
    a[i] = i;
}
for (i=0; i<1000; i++)
{
    b[i] = i+5;
}


// one fused loop here
for (i=0; i<1000; i++)
{
    a[i] = i;
    b[i] = i+5;
}
  • Unswitching : Some times a loop can be split into two or more loops, of which only one needs be executed at any time.

example:

// either one of the cases will be executing in each time
for (i=0; i<1000; i++)
{
    if (X>Y)  // this is executed every time inside the loop
        a[i] = i;
    else
        b[i] = i+10;
}

// loop split in two here
if (X>Y)  // now executed only once
{
    for (i=0; i<1000; i++)
    {
        a[i] = i;
    }
}
else
{
    for (i=0; i<1000; i++)
    {
        b[i] = i+10;
    }
}
  • Array Linearization : This involves handling a multi-dimensional array in a loop, as if it was a (simpler) one-dimensional array. Most times multi-dimensional arrays (eg 2D arrays NxM) use a linearization scheme, when stored in memory. Same scheme can be used to access the array data as if it is one big 1-dimensional array. This results in using a single loop instead of multiple nested loops 31, 32, 61

example:

// nested loop
// N = M = 20
// total size = NxM = 400
for (i=0; i<20; i+=1)
{
    for (j=0; j<20; j+=1)
    {
        // usually a[i, j] means a[i + j*N] or some other equivalent indexing scheme, 
        // in most cases linearization is straight-forward
        a[i, j] = 0;
    }
}

// array linearized single loop
for (i=0; i<400; i++)
    a[i] = 0;  // equivalent to previous with just a single loop

  • Loop Unrolling : Loop unrolling involves reducing the number of executions of a loop by performing the computations corresponding to two (or more) loop iterations in a single loop iteration. This is partial loop unrolling, full loop unrolling involves eliminating the loop completely and doing all the iterations explicitly in the code (for example for small loops where the number of iterations is fixed). Loop unrolling results in the loop (and as a consequence all the overhead associated with each loop iteration) executing fewer times. In processors which allow pipelining or parallel computations, loop unroling can have an additional benefit, the next unrolled iteration can start while the previous unrolled iteration is being computed or loaded without waiting to finish. Thus loop speed can increase even more 33

example:

// "rolled" usual loop
for (i=0; i<1000; i++)
{
    a[i] = b[i]*c[i];
}    

// partially unrolled loop (half iterations)
for (i=0; i<1000; i+=2)
{
    a[i] = b[i]*c[i];
    // unroled the next iteration into the current one and increased the loop iteration step to 2
    a[i+1] = b[i+1]*c[i+1];
}

// sometimes special care is needed to handle cases
// where the number of iterations is NOT an exact multiple of the number of unrolled steps
// this can be solved by adding the remaining iterations explicitly in the code, after or before the main unrolled loop

Databases

Generalities

Database Access can be expensive, this means it is usually better to fetch the needed data using as few DB connections and calls as possible

Methods

  • Lazy Load : Avoiding the DB access unless necessary can be efficient, provided that during the application life-cycle there is a frequency of cases where the extra data are not needed or requested

  • Caching : Re-using previous fetched data-results for same query, if not critical and if a slight-delayed update is tolerable

  • Using Efficient Queries : For Relational DBs, the most efficient query is by using an index (or a set of indexes) by which data are uniquely indexed in the DB 66, 67 .

  • Exploiting Redundancy : Adding more helping hands(DBs) to handle the load instead of just one. In effect this means copying (creating redundancy) of data in multiple places, which can subdivide the total load and handle it independantly

Web

  • Minimal Transactions : Data over the internet (and generally data over a network), take some time to be transmitted. More so if the data are large, therefore it is best to transmit only the necessary data, and even these in a compact form. That is one reason why JSON replaced the verbose XML for encoding of arbitrary data on the web.

  • Minimum Number of Requests : This can be seen as a variaton of the previous principle. It means that not only each request should transmit only necessary data in a compact form, but also that the number of requests should be minimized. This can include, minifying .css files into one .css file (even embedding images if needed), minifying .js files into one .js file, etc.. This can sometimes generate large data (files), however coupled with the next tip, can result in better performance.

  • Cache, cache and then cache some more : This can include everything, from whole pages to .css files, .js files, images etc.. Cache in the server, cache in the client, cache in-between, cache everywhere..

  • Exploiting Redundancy : For web applications, this is usually implemented by exploiting some cloud architecture in order to store (static) files, which can be loaded (through the cloud) from more than one location. Other approaches include, Load balancing ( having redundancy not only for static files, but also for servers ).

  • Make application code faster/lighter : This draws from the previous principles about code optimization in general. Efficient application code can save both server and user resources. There is a reason why Facebook created HipHop VM ..

  • Minimalism is an art form : Having web pages and applications with tons of html, images, (not to mention a ton of advertisements) etc, etc.. is not necessarily better design, and of course makes page load time slower. Therefore having minimal pages and doing updates in small chunks using AJAX and JSON (that is what web 2.0 was all about), instead of reloading a whole page each time, can go a long way. This is one reason why Template Engines and MVC Frameworks were created. Minimalism does not need to sacrifice the artistic dimension, Minimalism IS an art form.

το λακωνίζειν εστί φιλοσοφείν (i.e to be laconic in speech and deeds, simple and to the point, is the art of philosophy)

Zen Circle

References

  1. Code optimization, wikipedia
  2. Computational complexity theory, wikipedia
  3. DRY principle, wikipedia
  4. KISS principle, wikipedia
  5. Divide and conquer algorithm, wikipedia
  6. Parallel computation, wikipedia
  7. Lazy load, wikipedia
  8. An empirical study of Fortran programs
  9. Compiler optimizations, wikipedia
  10. Register allocation, wikipedia
  11. Compiler Design Theory
  12. The art of compiler design - Theory and Practice
  13. Horner rule, wikipedia
  14. Karatsuba algorithm, wikipedia
  15. Fast multiplication of complex numbers
  16. Exponentiation by squaring, wikipedia
  17. Fast Exponentiation
  18. Strassen algorithm, wikipedia
  19. Coppersmith-Winograd algorithm, wikipedia
  20. Comments on Factorial Programs
  21. Fast Factorial Functions
  22. Isomorphism, wikipedia
  23. Representation, wikipedia
  24. Symmetry, wikipedia
  25. Merge sort, wikipedia
  26. Radix sort, wikipedia
  27. Function inlining, wikipedia
  28. Strength reduction, wikipedia
  29. Loop invariant, wikipedia
  30. Loop-invariant code motion, wikipedia
  31. Array linearisation, wikipedia
  32. Vectorization, wikipedia
  33. Loop unrolling, wikipedia
  34. Software development philosophies, wikipedia
  35. 97 Things every programmer should know
  36. Data structure, wikipedia
  37. List of data structures, wikipedia
  38. Cloud computing, wikipedia
  39. Load balancing, wikipedia
  40. Model-view-controller, wikipedia
  41. Template engine, wikipedia
  42. Three optimization tips for C
  43. Three optimization tips for C, slides
  44. What Every Programmer Should Know About Floating-Point Arithmetic
  45. What Every Computer Scientist Should Know About Floating-Point Arithmetic
  46. Optimisation techniques
  47. Notes on C Optimisation
  48. Optimising C++
  49. Programming Optimization
  50. CODE OPTIMIZATION - USER TECHNIQUES
  51. Locality of reference, wikipedia
  52. Memory access pattern, wikipedia
  53. Memory hierarchy, wikipedia
  54. Heterogeneous computing, wikipedia
  55. Stream processing, wikipedia
  56. Dataflow programming, wikipedia
  57. Fast Fourier transform, wikipedia
  58. Gaussian elimination, wikipedia
  59. Fermat's little theorem, wikipedia
  60. Trigonometric identities, wikipedia
  61. The NumPy array: a structure for efficient numerical computation
  62. Dancing links algorithm
  63. Data Interface + Algorithms = Efficient Programs
  64. Systems Should Automatically Specialize Code and Data
  65. New Paradigms in Data Structure Design: Word-Level Parallelism and Self-Adjustment
  66. 10 tips for optimising Mysql queries
  67. Mysql Optimisation
  68. A Practical Wait-Free Simulation for Lock-Free Data Structures
  69. A Highly-Efficient Wait-Free Universal Construction
  70. A Methodology for Creating Fast Wait-Free Data Structures
  71. Euclidean Algorithm
  72. Gröbner basis