Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What are some common algorithmic optimization opportunities that everyone should be aware of? I have recently be revising/reviewing some code from an application, and noticed that it appeared to be running considerably slower than it could. The following loop turned out to be the culprit,

...
    float s1 = 0.0;
    for (int j = 0; j < size; ++j) {
        float diff = a[j] - b[j]; 
        s1 += (diff*diff * c[j]) + log(1.0/c[j]);
    }
...

This is equivalent to,

j { (aj-bj)2*cj + log(1/cj) }

Each time the program is run, this loop is called perhaps over 100k times, thus the repeated calls to log and divide result in a very large performance hit. A quick look at the sigma representation makes it pretty clear that there is a trivial fix - assuming you remember your logarithm identities well enough to spot it,

j { (aj-bj)2*cj + log(1/cj) } =

j { (aj-bj)2*cj } + ∑j { log(1.0/cj) } =

j { (aj-bj)2*cj } + log(1.0/(Πjcj))

and leads to a much more efficient snippet,

...
    float s1 = 0.0;
    float s2 = 1.0;
    for (int j = 0; j < size; ++j) {
        float diff = a[j] - b[j]; 
        s2 *= c[j];
        s1 += (diff*diff * c[j]);
    }
    s1 += log(1.0/s2);
...

this lead to a very large speed-up, and should have made its way into the original implementation. I assume it did not because the original developer(s) either weren't aware, or weren't 'actively aware' of this simple improvement.

This made me wonder, what other, similar, common opportunities and I missing out on or overlooking, and how can I learn to better spot them? I'm not so much interested in complex edge cases for particular algorithms, but rather examples like the one above that involve what you might think of as 'obvious' concepts that crop up frequently, but that others may not.

share|improve this question

migrated from stackoverflow.com Jul 9 '11 at 13:18

This question came from our site for professional and enthusiast programmers.

1  
you've sped it up, but you may have altered the accuracy, depending on the size of the Cj –  Mitch Wheat Jul 9 '11 at 2:27
    
Might be a disasterous optimization. If "size" is a big number, and c[j]>1, you might have introduced the opportunity for an overflow in " s2*=c[j]" where there was none before. If c[j]<1, you might have reduced the value of s2 to zero, causing an overflow at "s1+=log(1.0/s2)". –  Ira Baxter Jul 9 '11 at 9:54
1  
Did you write unit tests to compare the results? –  Job Jul 9 '11 at 16:17
    
log(1.0 / s2) equals -log(s2), optimizing away the division –  tiwo Jul 22 '12 at 9:03
add comment

4 Answers

The Implementation May Cheat, but it Must Not Get Caught

After profiling an application to determine where the time is being spent, the next step is determining exactly what the rest of the program expects out of the problem code. Since inner loops are often the culprit the amount of code is often small but the difference between the important work and the extraneous work may be very subtle. Once you know what the callers are relying on you can brainstorm new ways to produce the same result.

For example, your profiling run turns up strlen() at the head of the list. It is being called many, many times. You examine strlen() and you see it finds the length of the string by counting all of the bytes. Now, what part of that is important? How can we cheat? Does the caller actually care that we touch every byte? Probably not. Does it even care if we dereference any part of the string memory? Maybe not. Perhaps we can memoize the results. Will we get caught? Now you have to make sure your cached results are invalidated if the string changes. How else can we cheat? If you examine the callers you may find they are doing strlen(s) > 10. Now stop counting at 11 and you will do less work and not get caught.

The example in the question is a subtle one, as others have pointed out. You cheat by hoisting a math operation out of a loop. Will you get caught? Better think about the precision issues involved and how the intermediate floating point values will affect the results.

In one real-world example I discovered that a mirrored database startup was very slow. The code ensured database integrity by picking one of the copies, ensuring it was the most recent, and then loading all of the remaining N copies to compare against the first. This could not be readily parallelized because there wasn't enough memory to read all N copies in simultaneously. How can we cheat? Well, what is the actual goal? The code doesn't actually care about reading and comparing at all. What it cares about is having every copy be the same as the chosen one. What if instead of reading all the other copies we instead overwrite them all with the known good copy? Now we can do a lot of parallel IO and the operation goes many times faster. How can we get caught? Well, our write can be interrupted partway through. Or only some of our writes can be interrupted. Dealing with these corner cases was the bulk of the work. The fast, parallel write was worth the effort, though.

share|improve this answer
    
+1: Nice perspective, well explained. –  Ira Baxter Jul 9 '11 at 3:46
    
+1 I agree with Ira. I would put it as "find out why the time is being spent". What you want to find is time being spent for poor reasons. That's where the money is. –  Mike Dunlavey Jul 11 '11 at 16:21
add comment

My 2 cents:

  1. If possible, change the data structure of the program could be very helpful, even if the change was trivial. Once I changed a sparse matrix's presentation from adjacency table to a typical sparse matrix representation, and the average running time halved for my program.

  2. Get rid of recursion. This is hard to do but could be beneficial. However, if done improperly, this could lead to serious problems, and the non-recursive code is generally not as intuitive as the recursive version.

  3. Cache some of the frequently used values. Although this looks like cheating, it could be very beneficial - all the contest programmers should already know this. Also see memorization, mentioned in James Black's comment.

  4. Use shortcut evaluation properly. This won't lead to much performance boost normally, and can lead to unreadable code. But if the expression being evaluated has some really heavy work to do, this can help quite a bit.

  5. EDIT: If your job is computational-heavy and involves floating point computation (especially when it involves approximation), then sometimes restate your formula (NOT redesign the algorithm, just change the formula to a equivalent one) could speed your program greatly because of the floating point arithmetics the computers use. Many examples could be found in numerical analysis and scientific computing books. For the really interested, What Every Computer Scientist Should Know About Floating-Point Arithmetic is a great paper.

share|improve this answer
    
loop unrolling? All of the above, bar 1, are not really algorithmic optimisations (including loop unroling), more code optimisations –  Mitch Wheat Jul 9 '11 at 2:32
    
+1 - For your (3) memoization could be useful: codebetter.com/matthewpodwysocki/2008/08/01/…, but recursion can be useful, depending on the language. Profile, determine where it is slow, don't just optimize just because you assume that section is slow, it may be slower than optimal but may not overall impact the speed of the program. –  James Black Jul 9 '11 at 2:34
    
Well caching could be viewed as a kind of algorithm if use the Wikipedia definition strictly: an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. The algo here: get the input - find the answer - return. Just minimal:) –  Ziyao Wei Jul 9 '11 at 2:35
    
Your #2 absolutely depends on the used language and is not a general statement. Also depending on the algorithm the iterative implementation may be MUCH more complex (try a cache oblivious matrix multiplication iterative..) and is most certainly harder to parallelize. –  Voo Jul 9 '11 at 2:36
    
@Voo Realized my wording is inaccurate and edited. Thanks! –  Ziyao Wei Jul 9 '11 at 2:37
show 2 more comments

There's an infinite supply of algebraic equivalences, for all the various algebras with which one might compute. I don't think you can write down a useful specific extended list.

Similarly there are lots of algorithm equivalences. These are generally worthwhile, as they can affect the computation time in strongly nonlinear ways.

You'll also found there are variety of optimizations motivated by the computing hardware structures, such as sum trees instead of linear reductions, and caching reusable computation results when you have lots of cache.

Best to just be aware that such equivalences exist (modulo possible accuracy changes and different resource demands), when coding, and when one discovers where the code bottlenecks really are.

share|improve this answer
    
I agree it certainly wouldn't make sense to try and lay out everything; that's what a textbook is for. I do think we can make recommendations though; but perhaps we need more information about the problem domain. In my case I'm working on speech and NLP related problems, so situations like the above are quite common. It is of great practical use to be aware of these simple log identities. Maybe a better way of asking would be to ask about problem domains and things one 'ought to have an inkling of'. –  xhs7is82wl Jul 9 '11 at 2:55
    
@blackkettle: If you specify a problem domains (which often implicitly selects a set of solution methods by virtue of the fact that's the only way we know how work those problems), you might be able to focus on some kinds of optimizations. But even problem domains can have many solutions and there many optimizations; you wouldn't do a lot better if you narrowed this discussion to "scientific computation" and its solution methods. You mean diff eqn solvers? Relaxation systems? Computational fluid dynamics? Protein folding? .... Pick a very narrow solution area and you might have a chance. –  Ira Baxter Jul 9 '11 at 3:44
add comment

Algorithmic optimization opportunities. Here's the way I think about them generally:

Is the algorithm's complexity O(NlogN) or less? If so, it's probbaly good enough.

If not, I start looking for other algorithms.

Ultimately with very large data sets, changing the constant of proportionally doesn't do much (which is essentially what your posted example does). Only changing the algorithm's complexity will provide speed ups in the asymptotic case.

If you have fixed sized data sets, then maybe the improvements are worth it.

Oh almost forgot!: Make sure you measure before optimising.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.