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.