How to write fast code
Writing fast code requires some experience and it's hardly possible to stick to a general scheme. Nevertheless I'll provide some advice here. There are only two rules which always work and which can be considered reliable:
The golden rule of optimization
One cannot emphasize this enough. When in doubt, measure. When not in doubt, measure anyway. It's impossible to predict where a bottleneck will occur. If you think you're a smartass and can, you're wrong. Measuring, on the other hand, is fast and doesn't lie. So: Measure!
The silver rule of optimization
Optimization usually results in a decrease of portability and code readability.
Tiny little 0.5% optimizations usually aren't worth doing.
Many people write
xor eax, eax instead of the more readable
mov eax, 0 for "performance reasons", even in cases where it hardly matters.
On the other hand, if you can cut the speed by half somehow, do it!
(To figure out how apply the golden rule.)
Here are some tips. Before you use them, apply both the golden and the silver rule of optimization!
Optimize the innermost loop.
Should be obvious, nevertheless sometimes forgotten. The innermost loop will probably be executed many many many many times, so a single instruction can sum up to several minutes of computing time.
Avoid the innermost loop.
This may seem strange, but it's one of the best things you can do: Figure out when you can skip the innermost loop. Do some quick testing and then try to skip the rest of the calculations, because e.g. it doesn't contribute anything to the result. It's possible to cut computation time by a factor of two or more using this.
Avoid fancy algorithms.
Fancy algorithms may have decent time complexities, but they tend to have large constants. Don't use fancy algorithms unless the golden rule indicates so. Nice example:
while(a > b) a -= b;
This is much faster than
a % bif
aisn't much larger than
b. But don't use this as a rule. Use the golden rule.
Avoid assembly. Don't ever use inline assembly.
Writing assembly is tiresome and bugprone. Assembly usually hardly reduces computation time. Inline assembly is even worse considering maintainability and it's superfluous anyway.
Avoid specific rules.
Avoid rules like "don't use this, use that" (e.g. the
xor eax, eaxexample listed above). People strictly following these rules usually make worse, more subtle mistakes which lead to bad performance, while the rules drastically reduce the readability of the code.