A summary of code optimization methods
A summary of various code optimization methods
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 :) ).
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 parsed 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
Data Allocation
Binary Formats
Arithmetic Operations
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.
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 gcd computation 78 , fast factorials/binomials 20, 21 , fast fourier transform 57 , fast fibonacci numbers 76 , 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. An alternative approach to "dead-code elimination" is "live-code inclusion" or "tree-shaking" techniques.
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 or even hardcoding results directly.
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 , Newton's Method 73,74 , etc.. 75 ). 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, 77
Loop Optimizations
Perhaps the most important code optimization techniques are the ones involving loops.
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
}
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;
}
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;
}
}
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
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
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
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
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.