What are some common algorithm optimization opportunities - mathematical or otherwise

Question

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 { (a_j-b_j)²*c_j + log(1/c_j) }

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 { (a_j-b_j)²*c_j + log(1/c_j) } =

∑_j { (a_j-b_j)²*c_j } + ∑_j { log(1.0/c_j) } =

∑_j { (a_j-b_j)²*c_j } + log(1.0/(Π_jc_j))

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.