I recently read ‘Writing efficient programs’ by Jon Bentley. It’s quite an old book, written in 1982, but it still has many useful tips and tricks to achieving efficiency. I’ve compiled the most relevant and useful tricks in this article.
Sure, computers today are much faster and have bigger memories than when the book was written but that doesn’t mean that we as programmers should take that for granted. Lowering space and time consumption should always be in the back of your mind.
Now this being said, a clean nice to read program is much preferred over a high performance mess no one can understand. So optimize with care.
First things first, Bentley suggests writing a clean correct program before thinking about optimizing. The rules below should also only be applied if:
- It is certain that efficiency is an important problem in the code
- The particular piece of code being modified is a major bottleneck in the overall system performance
- All major speedups achievable by changing the the underlying algorithms and data structures of the program have been incorporated.
So this is not going to be a post about what algorithms and data structure to use when. There are plenty of amazing resources on those out there though.
Alright let’s dive in.
- Code Simplification: Most fast programs are simple, so keep it simple . Sources of harmful complexity includes: A lack of understanding the task and premature optimization.
- Problem Simplification: To increase the efficiency of a program, simplify the problem it solves. Why store all values when you only need a few of them?
- Relentless suspicion: Question the necessity of each instruction in a time critical piece of code and each field in a space critical data structure.
- Early binding: Move work forward in time. So, do work now just once in hope of avoiding doing it many times over later on. This means storing pre-computed results, initializing variables as soon as you can and generally just moving code from places where it is executed many times to places where it is executed just once, if possible.
Reducing the cost of loops:
- Computations outside of loops: Avoid performing computations inside loops that could have been performed outside. This is especially valid for computations involving square roots and other computation heavy math functions.
- Loop fusion: If two loops close to one another operate on the same set of elements, combine their operational parts.
Speeding up the logic
Logic rules often sacrifice clarity and robustness for speed. Use with care and comments.
- Exploit algebraic identities: If an evaluation of a logical expression is costly and can be changed to an algebraically equivalent expression that is cheaper to evaluate, it should be. De Morgans rules can be used to change for example !A || !B into !(A /\ B). This especially holds for math functions, such as square root or logarithms, if they have an algebraically equivalent that is cheaper to compute, use that instead.
- Reordering tests: Test should be arranged so the most inexpensive test and often successful tests precede expensive and rarely successful tests. Used mostly in if-else statements.
- Boolean variable elimination: Remove boolean variables by using an if else statement for the two values of the boolean value (true/false).
Discovering hot spots
Use statistics and analysis tools to determine where the hot spots are in your program. Focus your work on these hot spots.
When the hot spots of a system have been isolated, these are the steps to take:
- Identify the code to be changed
- Choose a rule to apply to it. Find out which of the rules best apply.
Measure the effect of the modification. It might not have made a significant change, or it might potentially have made it worse.
- Document the resulting program. Include a description of the clean code and of the modification made.
When modifying an already correct program, test extensively to ensure that your changes did not introduce bugs. Also every rule can backfire and decrease the efficiency so make sure you didn’t make the run time worse after every optimization.
Be willing to backtrack and try other rules, or if you have to choose between two rules, pick the one with the greatest performance gain. Be careful to not overuse them. If adding more speedups doesn’t yield that much extra performance and mess up the code significantly, get rid of them.
For problem solving, remember that you can stand on the shoulders of many smart people and use their solutions instead of inventing the weel every time. Chances are, the experts have come up with a better solution.
Thank you for reading and feel free to leave a comment down below ❤️